Hacker's Delightby Henry S. Warren
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/b>/i>
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
- A new chapter on cyclic redundancy checking (CRC), including routines for the commonly used CRC-32 code
- A new chapter on error correcting codes (ECC), including routines for the Hamming code
- More coverage of integer division by constants, including methods using only shifts and adds
- Computing remainders without computing a quotient
- More coverage of population count and counting leading zeros
- Array population count
- New algorithms for compress and expand
- An LRU algorithm
- Floating-point to/from integer conversions
- Approximate floating-point reciprocal square root routine
- A gallery of graphs of discrete functions
- Now with exercises and answers
“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
- Pearson Education
- Publication date:
- Sold by:
- Barnes & Noble
- NOOK Book
- File size:
- 34 MB
- This product may take a few minutes to download.
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's-complement form. Although a 32-bit 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 1-bits 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 high-level language because it is widely known, it allows the straightforward mixture of integer and bit-string operations, and C compilers that produce high-quality object code are available.
Occasionally, machine language is used. It employs a three-address format, mainly for ease of readability. The assembly language used is that of a fictitious machine that is representative of today's RISC computers.
Branch-free 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 instruction-level 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 itself1. 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:
Meet the Author
Henry S. Warren, Jr., has had a fifty-year 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.
Most Helpful Customer Reviews
See all customer reviews