Uhoh, it looks like your Internet Explorer is out of date.
For a better shopping experience, please upgrade now.
Hacker's Delight / Edition 1 available in Hardcover
Hardcover  Rent for
Temporarily Out of Stock Online
Overview
At long last, a collection of shortcuts for the programming trade, organized thematically in one volume!
These are the timesaving techniques relished by computer hackers—those devoted and persistent problemsolvers engrossed in their code who seek elegant and efficient solutions for building better software. The truth is that much of the computer programmer's job involves a healthy mix of arithmetic and logic. In Hacker's Delight, veteran programmer Hank Warren shares the tricks he has collected from his considerable experience in the worlds of application and system programming. Most of these devices are eminently practical, but a few are included just because they are interesting and unexpected. The resulting work is an irresistible collection that will help even the most seasoned programmers better their craft.
Topics covered include:
 A collection useful programming devices the author has collected over the years
 Small algorithms for common tasks
 Powerof2 boundaries and bounds checking
 Rearranging bits and bytes
 Integer division and division by constants
 Some elementary functions on integers
 Gray code
 Hilbert's spacefilling curve
 And even formulas for prime numbers!
This book is for anyone who wants to create efficient code. With the help of Hacker's Delight, you will learn to program at a higher level than is generally taught in schools or training courses, and you will advance substantially more than you would through selfdirected study.
Product Details
ISBN13:  9780201914658 

Publisher:  AddisonWesley 
Publication date:  07/28/2002 
Edition description:  Older Edition 
Pages:  306 
Product dimensions:  6.50(w) x 9.37(h) x 0.81(d) 
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);}
First Chapter
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
1. Introduction.
Instruction Set and Execution Time Model.
2. Basis.
Addition Combined with Logical Operations.
Inequalities among Logical and Arithmetic Expressions.
Absolute Value.
Sign Extension.
Shift Right Signed from Unsigned.
Sign Function.
Threevalued Compare.
Transfer of Sign.
Decoding a “Zero Means 2**n” Field.
Comparison Predicates.
Overflow Detection.
Condition Code Result of Add, Subtract, and Multiply.
Rotate Shifts.
Doublelength Add/subtract.
Doublelength Shifts.
Multibyte Add, Subtract, Absolute Value.
Doz, Max, Min.
Exchanging Registers.
Alternating among Two or More Values.
3. Powerof2 Boundaries.
Rounding up/down to the Next Power of 2.
Detecting a Powerof2 Boundary Crossing.
4. Arithmetic Bounds.
Propagating Bounds through Adds and Subtracts.
Propagating Bounds through Logical Operations.
Signed Bounds.
5. Counting Bits.
Parity.
Counting Leading Zeros.
Counting Trailing Zeros.
6. Searching Words.
Find First String of 1bits of a Given Length.
7. Rearranging Bits and Bytes.
Shuffling Bits.
Transposing a Bit Matrix.
Compress, or Generalized Extract.
General Permutations, Sheep and Goats Operation.
Rearrangements and Index Transformations.
8. Multiplication.
Highorder Half of 64bit Product.
Highorder Product Signed from/to Unsigned.
Multiplication by Constants.
9. Integer Division.
Multiword Division.
Unsigned Short Division from Signed Division.
Unsigned Long Division.
10. Integer Division by Constants.
Signed Remainder from Division by a Known Power of 2.
Signed Division and Remainder by Nonpowers of 2.
Signed Division by Divisors >= 2.
Signed Division by Divisors <= 2.
Incorporation into a compiler.
Miscellaneous Topics.
Unsigned Division.
Unsigned Division by Divisors >= 1.
Incorporation into a Compiler (unsigned).
Miscellaneous Topics (unsigned).
Applicability to Nodulus and floor division.
Similar methods.
Sample Magic Numbers.
Exact Division by constants.
Test for Zero Remainder after Division by a Bonstant.
11. Some Elementary Functions.
Integer Cube Root.
Integer Exponentiation.
Integer Logarithm.
12. Unusual Bases for Number Systems.
Base 1 + i.
Other Bases.
What is the Most Efficient Base?
13. Gray Code.
Incrementing a Gray Coded Integer.
Negabinary Gray Code.
Brief History and Applications.
14. Hilbert's Curve.
Coordinates from Distance along the Hilbert Curve.
Distance from Coordinates on the Hilbert Curve.
Incrementing the Coordinates on the Hilbert Curve.
Nonrecursive Generating Algorithms.
Other Spacefilling Curves.
Applications.
15. FloatingPoint.
Comparing Floatingpoint Numbers Using Integer Operations.
The Distribution of Leading Digits.
Table of Miscellaneous Values.
16. Formulas for Primes.
Willans's Formulas.
Wormell's Formula.
Formulas for Other Difficult Functions.
Appendix A. Arithmetic Tables for a FourBit Machine.
Appendix B. Newton's Method.
References.
Index.
Reading Group Guide
Preface.
1. Introduction.
Instruction Set and Execution Time Model.
2. Basis.
Addition Combined with Logical Operations.
Inequalities among Logical and Arithmetic Expressions.
Absolute Value.
Sign Extension.
Shift Right Signed from Unsigned.
Sign Function.
Threevalued Compare.
Transfer of Sign.
Decoding a “Zero Means 2**n” Field.
Comparison Predicates.
Overflow Detection.
Condition Code Result of Add, Subtract, and Multiply.
Rotate Shifts.
Doublelength Add/subtract.
Doublelength Shifts.
Multibyte Add, Subtract, Absolute Value.
Doz, Max, Min.
Exchanging Registers.
Alternating among Two or More Values.
3. Powerof2 Boundaries.
Rounding up/down to the Next Power of 2.
Detecting a Powerof2 Boundary Crossing.
4. Arithmetic Bounds.
Propagating Bounds through Adds and Subtracts.
Propagating Bounds through Logical Operations.
Signed Bounds.
5. Counting Bits.
Parity.
Counting Leading Zeros.
Counting Trailing Zeros.
6. Searching Words.
Find First String of 1bits of a Given Length.
7. Rearranging Bits and Bytes.
Shuffling Bits.
Transposing a Bit Matrix.
Compress, or Generalized Extract.
General Permutations, Sheep and Goats Operation.
Rearrangements and Index Transformations.
8. Multiplication.
Highorder Half of 64bit Product.
Highorder Product Signed from/to Unsigned.
Multiplication by Constants.
9. Integer Division.
Multiword Division.
Unsigned Short Division from Signed Division.
Unsigned Long Division.
10. Integer Division by Constants.
Signed Remainder from Division by a Known Power of 2.
Signed Division and Remainder by Nonpowers of 2.
Signed Division by Divisors >= 2.
Signed Division by Divisors <= 2.
Incorporation into a compiler.
Miscellaneous Topics.
Unsigned Division.
Unsigned Division by Divisors >= 1.
Incorporation into a Compiler (unsigned).
Miscellaneous Topics (unsigned).
Applicability to Nodulus and floor division.
Similar methods.
Sample Magic Numbers.
Exact Division by constants.
Test for Zero Remainder after Division by a Bonstant.
11. Some Elementary Functions.
Integer Cube Root.
Integer Exponentiation.
Integer Logarithm.
12. Unusual Bases for Number Systems.
Base 1 + i.
Other Bases.
What is the Most Efficient Base?
13. Gray Code.
Incrementing a Gray Coded Integer.
Negabinary Gray Code.
Brief History and Applications.
14. Hilbert's Curve.
Coordinates from Distance along the Hilbert Curve.
Distance from Coordinates on the Hilbert Curve.
Incrementing the Coordinates on the Hilbert Curve.
Nonrecursive Generating Algorithms.
Other Spacefilling Curves.
Applications.
15. FloatingPoint.
Comparing Floatingpoint Numbers Using Integer Operations.
The Distribution of Leading Digits.
Table of Miscellaneous Values.
16. Formulas for Primes.
Willans's Formulas.
Wormell's Formula.
Formulas for Other Difficult Functions.
Appendix A. Arithmetic Tables for a FourBit Machine.
Appendix B. Newton's Method.
References.
Index.
Interviews
Preface.
1. Introduction.
Instruction Set and Execution Time Model.
2. Basis.
Addition Combined with Logical Operations.
Inequalities among Logical and Arithmetic Expressions.
Absolute Value.
Sign Extension.
Shift Right Signed from Unsigned.
Sign Function.
Threevalued Compare.
Transfer of Sign.
Decoding a “Zero Means 2**n” Field.
Comparison Predicates.
Overflow Detection.
Condition Code Result of Add, Subtract, and Multiply.
Rotate Shifts.
Doublelength Add/subtract.
Doublelength Shifts.
Multibyte Add, Subtract, Absolute Value.
Doz, Max, Min.
Exchanging Registers.
Alternating among Two or More Values.
3. Powerof2 Boundaries.
Rounding up/down to the Next Power of 2.
Detecting a Powerof2 Boundary Crossing.
4. Arithmetic Bounds.
Propagating Bounds through Adds and Subtracts.
Propagating Bounds through Logical Operations.
Signed Bounds.
5. Counting Bits.
Parity.
Counting Leading Zeros.
Counting Trailing Zeros.
6. Searching Words.
Find First String of 1bits of a Given Length.
7. Rearranging Bits and Bytes.
Shuffling Bits.
Transposing a Bit Matrix.
Compress, or Generalized Extract.
General Permutations, Sheep and Goats Operation.
Rearrangements and Index Transformations.
8. Multiplication.
Highorder Half of 64bit Product.
Highorder Product Signed from/to Unsigned.
Multiplication by Constants.
9. Integer Division.
Multiword Division.
Unsigned Short Division from Signed Division.
Unsigned Long Division.
10. Integer Division by Constants.
Signed Remainder from Division by a Known Power of 2.
Signed Division and Remainder by Nonpowers of 2.
Signed Division by Divisors >= 2.
Signed Division by Divisors <= 2.
Incorporation into a compiler.
Miscellaneous Topics.
Unsigned Division.
Unsigned Division by Divisors >= 1.
Incorporation into a Compiler (unsigned).
Miscellaneous Topics (unsigned).
Applicability to Nodulus and floor division.
Similar methods.
Sample Magic Numbers.
Exact Division by constants.
Test for Zero Remainder after Division by a Bonstant.
11. Some Elementary Functions.
Integer Cube Root.
Integer Exponentiation.
Integer Logarithm.
12. Unusual Bases for Number Systems.
Base 1 + i.
Other Bases.
What is the Most Efficient Base?
13. Gray Code.
Incrementing a Gray Coded Integer.
Negabinary Gray Code.
Brief History and Applications.
14. Hilbert's Curve.
Coordinates from Distance along the Hilbert Curve.
Distance from Coordinates on the Hilbert Curve.
Incrementing the Coordinates on the Hilbert Curve.
Nonrecursive Generating Algorithms.
Other Spacefilling Curves.
Applications.
15. FloatingPoint.
Comparing Floatingpoint Numbers Using Integer Operations.
The Distribution of Leading Digits.
Table of Miscellaneous Values.
16. Formulas for Primes.
Willans's Formulas.
Wormell's Formula.
Formulas for Other Difficult Functions.
Appendix A. Arithmetic Tables for a FourBit Machine.
Appendix B. Newton's Method.
References.
Index.
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 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 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);}
0201914654P08282002
Recipe
1. Introduction.
Instruction Set and Execution Time Model.
2. Basis.
Addition Combined with Logical Operations.
Inequalities among Logical and Arithmetic Expressions.
Absolute Value.
Sign Extension.
Shift Right Signed from Unsigned.
Sign Function.
Threevalued Compare.
Transfer of Sign.
Decoding a “Zero Means 2**n” Field.
Comparison Predicates.
Overflow Detection.
Condition Code Result of Add, Subtract, and Multiply.
Rotate Shifts.
Doublelength Add/subtract.
Doublelength Shifts.
Multibyte Add, Subtract, Absolute Value.
Doz, Max, Min.
Exchanging Registers.
Alternating among Two or More Values.
3. Powerof2 Boundaries.
Rounding up/down to the Next Power of 2.
Detecting a Powerof2 Boundary Crossing.
4. Arithmetic Bounds.
Propagating Bounds through Adds and Subtracts.
Propagating Bounds through Logical Operations.
Signed Bounds.
5. Counting Bits.
Parity.
Counting Leading Zeros.
Counting Trailing Zeros.
6. Searching Words.
Find First String of 1bits of a Given Length.
7. Rearranging Bits and Bytes.
Shuffling Bits.
Transposing a Bit Matrix.
Compress, or Generalized Extract.
General Permutations, Sheep and Goats Operation.
Rearrangements and Index Transformations.
8. Multiplication.
Highorder Half of 64bit Product.
Highorder Product Signed from/to Unsigned.
Multiplication by Constants.
9. Integer Division.
Multiword Division.
Unsigned Short Division from Signed Division.
Unsigned Long Division.
10. Integer Division by Constants.
Signed Remainder from Division by a Known Power of 2.
Signed Division and Remainder by Nonpowers of 2.
Signed Division by Divisors >= 2.
Signed Division by Divisors <= 2.
Incorporation into a compiler.
Miscellaneous Topics.
Unsigned Division.
Unsigned Division by Divisors >= 1.
Incorporation into a Compiler (unsigned).
Miscellaneous Topics (unsigned).
Applicability to Nodulus and floor division.
Similar methods.
Sample Magic Numbers.
Exact Division by constants.
Test for Zero Remainder after Division by a Bonstant.
11. Some Elementary Functions.
Integer Cube Root.
Integer Exponentiation.
Integer Logarithm.
12. Unusual Bases for Number Systems.
Base 1 + i.
Other Bases.
What is the Most Efficient Base?
13. Gray Code.
Incrementing a Gray Coded Integer.
Negabinary Gray Code.
Brief History and Applications.
14. Hilbert's Curve.
Coordinates from Distance along the Hilbert Curve.
Distance from Coordinates on the Hilbert Curve.
Incrementing the Coordinates on the Hilbert Curve.
Nonrecursive Generating Algorithms.
Other Spacefilling Curves.
Applications.
15. FloatingPoint.
Comparing Floatingpoint Numbers Using Integer Operations.
The Distribution of Leading Digits.
Table of Miscellaneous Values.
16. Formulas for Primes.
Willans's Formulas.
Wormell's Formula.
Formulas for Other Difficult Functions.
Appendix A. Arithmetic Tables for a FourBit Machine.
Appendix B. Newton's Method.
References.
Index.
Customer Reviews
Most Helpful Customer Reviews
At first sight, the book seemed a bit short for $40. But there is quite a bit of information packed in there, and it's certainly much easier to comprehend than picking up one of Knuth's books for the first time. With that said, this really is a book for computer engineers, i.e. people who really like to know what's going on at the bit level. The bit manipulation examples are given in pseudoassembly, which is very applicable. I can't give 5 stars because of the niche target audience, but it is a very concise, interesting read.

