Hacker’s Delight (2/e) (Review)

Hacker's Delight (2/e)

Hacker’s Delight (2/e), by Henry S. Warren Jr., Addison-Wesley, 2012.

Perhaps you’ve seen this trick for swapping two variables without using a temporary:

x = x ^ y
y = y ^ x
x = x ^ y

Or maybe you’d like this code to count the number of 1-bits in a 32-bit word (while avoiding “if” or “while” branches):

x = (x & 0x55555555) + ((x >> 1) & 0x55555555)
x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F)
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF)
x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF)

(This works by counting the bits in 2 bits, then 4 bits, etc. Try it with 8 bits to get the idea.)

If cool bit-twiddling appeals to you at all, you will love this book. Its almost 500 pages touch on binary (and other base) arithmetic, counting bits, efficient division by constants, error-correcting codes, curve-drawing, primes, and more and more. (You would also enjoy HAKMEM, a classic MIT technical report that inspired some of this work.) The math (for proofs or explanations) isn’t outrageously hard, mostly straightforward formulas, sums, and products.

This isn’t a book I’d use much for day-to-day programming. But every technique I worked through left me in awe of the surprise simplicity it revealed.