 Shopping Bag ( 0 items )

All (17) from $37.88

New (12) from $40.85

Used (5) from $37.88
More About This Textbook
Overview
In Hacker’s Delight, Second Edition, Hank Warren once again compiles an irresistible collection of programming hacks: timesaving techniques, algorithms, and tricks that help programmers build more elegant and efficient software, while also gaining deeper insights into their craft. Warren’s hacks are eminently practical, but they’re also intrinsically interesting, and sometimes unexpected, much like the solution to a great puzzle. They are, in a word, a delight to any programmer who is excited by the opportunity to improve.
Extensive additions in this edition include
Editorial Reviews
From the Publisher
“This is the first book that promises to tell the deep, dark secrets of computer arithmetic, and it delivers in spades. It contains every trick I knew plus many, many more. A godsend for library developers, compiler writers, and lovers of elegant hacks, it deserves a spot on your shelf right next to Knuth. In the ten years since the first edition came out, it’s been absolutely invaluable to my work at Sun and Google. I’m thrilled with all of the new material in the second edition.”
— Joshua Bloch
“When I first saw the title, I figured that the book must be either a cookbook for breaking into computers (unlikely) or some sort of compendium of little programming tricks. It’s the latter, but it’s thorough, almost encyclopedic, in its coverage. The second edition covers two new major topics and expands the overall collection with dozens of additional little tricks, including one that I put to use right away in a binary search algorithm: computing the average of two integers without risking overflow. This hacker is indeed delighted!”
— Guy Steele
From The Critics
A computer scientist deeply embedded in IBM has compiled small programming tricks he has come across over his four decades in the field. Most work only on computers that represent integers in two's complement form, and are easily adapted to machines with various register sizes, though a 32bit machine is assumed when the register length is relevant. He gives proofs only when the algorithm is not obvious, and not always then. Annotation c. Book News, Inc., Portland, ORProduct Details
Related Subjects
Meet the Author
Henry S. Warren, Jr., has had a fiftyyear career with IBM, spanning from the IBM 704 to the PowerPC and beyond. He has worked on various military command and control systems and on the SETL (SET Language) project under Jack Schwartz. Since 1973, Hank has been with IBM’s Research Division, focusing on compilers and computer architectures. He currently works on a supercomputer project aimed at an exaflop. Hank received his Ph.D. in computer science from the Courant Institute at New York University.
Read an Excerpt
Caveat Emptor: The cost of software maintenance increases with the square of the programmer's creativity.
First Law of Programmer Creativity, Robert D. Bliss, 1992
This is a collection of small programming tricks that I have come across over many years. Most of them will work only on computers that represent integers in two'scomplement form. Although a 32bit machine is assumed when the register length is relevant, most of the tricks are easily adapted to machines with other register sizes.
This book does not deal with large tricks such as sophisticated sorting and compiler optimization techniques. Rather, it deals with small tricks that usually involve individual computer words or instructions, such as counting the number of 1bits in a word. Such tricks often use a mixture of arithmetic and logical instructions.
It is assumed throughout that integer overflow interrupts have been masked off, so they cannot occur. C, Fortran, and even Java programs run in this environment, but Pascal and ADA users beware!
The presentation is informal. Proofs are given only when the algorithm is not obvious, and sometimes not even then. The methods use computer arithmetic, "floor" functions, mixtures of arithmetic and logical operations, and so on. Proofs in this domain are often difficult and awkward to express.
To reduce typographical errors and oversights, many of the algorithms have been executed. This is why they are given in a real programming language, even though, like every computer language, it has some ugly features. C is used for the highlevel language because it is widely known, it allows the straightforward mixture of integer and bitstring operations, and C compilers that produce highquality object code are available.
Occasionally, machine language is used. It employs a threeaddress format, mainly for ease of readability. The assembly language used is that of a fictitious machine that is representative of today's RISC computers.
Branchfree code is favored. This is because on many computers, branches slow down instruction fetching and inhibit executing instructions in parallel. Another problem with branches is that they may inhibit compiler optimizations such as instruction scheduling, commoning, and register allocation. That is, the compiler may be more effective at these optimizations with a program that consists of a few large basic blocks rather than many small ones.
The code sequences also tend to favor small immediate values, comparisons to zero (rather than to some other number), and instructionlevel parallelism. Although much of the code would become more concise by using table lookups (from memory), this is not often mentioned. This is because loads are becoming more expensive relative to arithmetic instructions, and the table lookup methods are often not very interesting (although they are often practical). But there are exceptional cases.
Finally, I should mention that the term "hacker" in the title is meant in the original sense of an aficionado of computers—someone who enjoys making computers do new things, or do old things in a new and clever way. The hacker is usually quite good at his craft, but may very well not be a professional computer programmer or designer. The hacker's work may be useful or may be just a game. As an example of the latter, more than one determined hacker has written a program which, when executed, writes out an exact copy of itself^{1}. This is the sense in which we use the term "hacker." If you're looking for tips on how to break into someone else's computer, you won't find them here.
H. S. Warren, Jr.
Yorktown, New York February 2002
1. The shortest such program written in C, known to the present author, is by Vlad Taeerov and Rashit Fakhreyev and is 64 characters in length:
main(a){printf(a,34,a="main(a){printf(a,34,a=%c%s%c,34);}",34);}
Table of Contents
Foreword xiii
Preface xv
Chapter 1: Introduction 1
1.1 Notation 1
1.2 Instruction Set and Execution Time Model 5
Chapter 2: Basics 11
2.1 Manipulating Rightmost Bits 11
2.2 Addition Combined with Logical Operations 16
2.3 Inequalities among Logical and Arithmetic Expressions 17
2.4 Absolute Value Function 18
2.5 Average of Two Integers 19
2.6 Sign Extension 19
2.7 Shift Right Signed from Unsigned 20
2.8 Sign Function 20
2.9 ThreeValued Compare Function 21
2.10 Transfer of Sign Function 22
2.11 Decoding a “Zero Means 2**n” Field 22
2.12 Comparison Predicates 23
2.13 Overflow Detection 28
2.14 Condition Code Result of Add, Subtract, and Multiply 36
2.15 Rotate Shifts 37
2.16 DoubleLength Add/Subtract 38
2.17 DoubleLength Shifts 39
2.18 Multibyte Add, Subtract, Absolute Value 40
2.19 Doz, Max, Min 41
2.20 Exchanging Registers 45
2.21 Alternating among Two or More Values 48
2.22 A Boolean Decomposition Formula 51
2.23 Implementing Instructions for all 16 Binary Boolean Operations 53
Chapter 3: Powerof2 Boundaries 59
3.1 Rounding Up/Down to a Multiple of a Known Power of 2 59
3.2 Rounding Up/Down to the Next Power of 2 60
3.3 Detecting a Powerof2 Boundary Crossing 63
Chapter 4: Arithmetic Bounds 67
4.1 Checking Bounds of Integers 67
4.2 Propagating Bounds through Add’s and Subtract’s 70
4.3 Propagating Bounds through Logical Operations 73
Chapter 5: Counting Bits 81
5.1 Counting 1Bits 81
5.2 Parity 96
5.3 Counting Leading 0’s 99
5.4 Counting Trailing 0’s 107
Chapter 6: Searching Words 117
6.1 Find First 0Byte 117
6.2 Find First String of 1Bits of a Given Length 123
6.3 Find Longest String of 1Bits 125
6.4 Find Shortest String of 1Bits 126
Chapter 7: Rearranging Bits And Bytes 129
7.1 Reversing Bits and Bytes 129
7.2 Shuffling Bits 139
7.3 Transposing a Bit Matrix 141
7.4 Compress, or Generalized Extract 150
7.5 Expand, or Generalized Insert 156
7.6 Hardware Algorithms for Compress and Expand 157
7.7 General Permutations, Sheep and Goats Operation 161
7.8 Rearrangements and Index Transformations 165
7.9 An LRU Algorithm 166
Chapter 8: Multiplication 171
8.1 Multiword Multiplication 171
8.2 HighOrder Half of 64Bit Product 173
8.3 HighOrder Product Signed from/to Unsigned 174
8.4 Multiplication by Constants 175
Chapter 9: Integer Division 181
9.1 Preliminaries 181
9.2 Multiword Division 184
9.3 Unsigned Short Division from Signed Division 189
9.4 Unsigned Long Division 192
9.5 Doubleword Division from Long Division 197
Chapter 10: Integer Division By Constants 205
10.1 Signed Division by a Known Power of 2 205
10.2 Signed Remainder from Division by a Known Power of 2 206
10.3 Signed Division and Remainder by NonPowers of 2 207
10.4 Signed Division by Divisors ≥ 2 210
10.5 Signed Division by Divisors ≤ —2 218
10.6 Incorporation into a Compiler 220
10.7 Miscellaneous Topics 223
10.8 Unsigned Division 227
10.9 Unsigned Division by Divisors ≥ 1 230
10.10 Incorporation into a Compiler (Unsigned) 232
10.11 Miscellaneous Topics (Unsigned) 234
10.12 Applicability to Modulus and Floor Division 237
10.13 Similar Methods 237
10.14 Sample Magic Numbers 238
10.15 Simple Code in Python 240
10.16 Exact Division by Constants 240
10.17 Test for Zero Remainder after Division by a Constant 248
10.18 Methods Not Using Multiply High 251
10.19 Remainder by Summing Digits 262
10.20 Remainder by Multiplication and Shifting Right 268
10.21 Converting to Exact Division 274
10.22 A Timing Test 276
10.23 A Circuit for Dividing by 3 276
Chapter 11: Some Elementary Functions 279
11.1 Integer Square Root 279
11.2 Integer Cube Root 287
11.3 Integer Exponentiation 288
11.4 Integer Logarithm 291
Chapter 12: Unusual Bases For Number Systems 299
12.1 Base —2 299
12.2 Base —1 + i 306
12.3 Other Bases 308
12.4 What Is the Most Efficient Base? 309
Chapter 13: Gray Code 311
13.1 Gray Code 311
13.2 Incrementing a GrayCoded Integer 313
13.3 Negabinary Gray Code 315
13.4 Brief History and Applications 315
Chapter 14: Cyclic Redundancy Check 319
14.1 Introduction 319
14.2 Theory 320
14.3 Practice 323
Chapter 15: ErrorCorrecting Codes 331
15.1 Introduction 331
15.2 The Hamming Code 332
15.3 Software for SECDED on 32 Information Bits 337
15.4 Error Correction Considered More Generally 342
Chapter 16: Hilbert's Curve 355
16.1 A Recursive Algorithm for Generating the Hilbert Curve 356
16.2 Coordinates from Distance along the Hilbert Curve 358
16.3 Distance from Coordinates on the Hilbert Curve 366
16.4 Incrementing the Coordinates on the Hilbert Curve 368
16.5 NonRecursive Generating Algorithms 371
16.6 Other SpaceFilling Curves 371
16.7 Applications 372
Chapter 17: FloatingPoint 375
17.1 IEEE Format 375
17.2 FloatingPoint To/From Integer Conversions 377
17.3 Comparing FloatingPoint Numbers Using Integer Operations 381
17.4 An Approximate Reciprocal Square Root Routine 383
17.5 The Distribution of Leading Digits 385
17.6 Table of Miscellaneous Values 387
Chapter 18: Formulas For Primes 391
18.1 Introduction 391
18.2 Willans’s Formulas 393
18.3 Wormell’s Formula 397
18.4 Formulas for Other Difficult Functions 398
Answers To Exercises: 405
Appendix A: Arithmetic Tables For A 4Bit Machine 453
Appendix B: Newton's Method 457
Appendix C: A Gallery Of Graphs Of Discrete Functions 459
C.1 Plots of Logical Operations on Integers 459
C.2 Plots of Addition, Subtraction, and Multiplication 461
C.3 Plots of Functions Involving Division 463
C.4 Plots of the Compress, SAG, and Rotate Left Functions 464
C.5 2D Plots of Some Unary Functions 466
Bibliography 471
Index 481
Preface
Caveat Emptor: The cost of software maintenance
increases with the square of the programmer's creativity. First Law of Programmer Creativity, Robert D. Bliss, 1992
This is a collection of small programming tricks that I have come across over many years. Most of them will work only on computers that represent integers in two'scomplement form. Although a 32bit machine is assumed when the register length is relevant, most of the tricks are easily adapted to machines with other register sizes.
This book does not deal with large tricks such as sophisticated sorting and compiler optimization techniques. Rather, it deals with small tricks that usually involve individual computer words or instructions, such as counting the number of 1bits in a word. Such tricks often use a mixture of arithmetic and logical instructions.
It is assumed throughout that integer overflow interrupts have been masked off, so they cannot occur. C, Fortran, and even Java programs run in this environment, but Pascal and ADA users beware!
The presentation is informal. Proofs are given only when the algorithm is not obvious, and sometimes not even then. The methods use computer arithmetic, "floor" functions, mixtures of arithmetic and logical operations, and so on. Proofs in this domain are often difficult and awkward to express.
To reduce typographical errors and oversights, many of the algorithms have been executed. This is why they are given in a real programming language, even though, like every computer language, it has some ugly features. C is used for the highlevel language because it is widely known, it allows the straightforward mixture of integer and bitstringoperations, and C compilers that produce highquality object code are available.
Occasionally, machine language is used. It employs a threeaddress format, mainly for ease of readability. The assembly language used is that of a fictitious machine that is representative of today's RISC computers.
Branchfree code is favored. This is because on many computers, branches slow down instruction fetching and inhibit executing instructions in parallel. Another problem with branches is that they may inhibit compiler optimizations such as instruction scheduling, commoning, and register allocation. That is, the compiler may be more effective at these optimizations with a program that consists of a few large basic blocks rather than many small ones.
The code sequences also tend to favor small immediate values, comparisons to zero (rather than to some other number), and instructionlevel parallelism. Although much of the code would become more concise by using table lookups (from memory), this is not often mentioned. This is because loads are becoming more expensive relative to arithmetic instructions, and the table lookup methods are often not very interesting (although they are often practical). But there are exceptional cases.
Finally, I should mention that the term "hacker" in the title is meant in the original sense of an aficionado of computerssomeone who enjoys making computers do new things, or do old things in a new and clever way. The hacker is usually quite good at his craft, but may very well not be a professional computer programmer or designer. The hacker's work may be useful or may be just a game. As an example of the latter, more than one determined hacker has written a program which, when executed, writes out an exact copy of itself^{1}. This is the sense in which we use the term "hacker." If you're looking for tips on how to break into someone else's computer, you won't find them here. H. S. Warren, Jr.
Yorktown, New York
February 2002
1. The shortest such program written in C, known to the present author, is by Vlad Taeerov and Rashit Fakhreyev and is 64 characters in length: main(a){printf(a,34,a="main(a){printf(a,34,a=%c%s%c,34);}",34);}