Hacker's Delight

by Henry S. Warren, Jr. Addison Wesley, 2002 ISBN: 0-201-91465-4 Cover Price: US$39.99 306 Pages

(68 K)

Hacker's Delight by Henry S. Warren Jr. is a delight indeed. Despite its title, this volume of mathematical programming tricks has nothing to do with breaking into other people's computers. Warren is a hacker in the original sense of the word: someone who enjoys writing clever code and finding elegant solutions to computing problems. He discovered many of the tricks and methods he presents in the book during a forty-year career working on compilers and computer architecture with IBM's Research Division. His collection of code snippets and equations range from basic arithmetic operations to sophisticated mathematics.

Computer math may not be a subject that appeals to a broad range of readers, but this book is a gold mine of useful methods and information for those who are interested. The engineer writing a compiler, a math library, or any highly optimized code will find the book indispensable. Anyone familiar with assembly language will find the book accessible and interesting. It can be read from front to back, used as a reference, or enjoyed in the manner Guy Steele describes in his foreword to the book: "Devouring these little programming nuggets was like eating peanuts, or rather bonbons -- I just couldn't stop -- and there was a certain richness to them, a certain intellectual depth, elegance, even poetry."

The book begins by giving a set of formulas for simple operations that one might encounter in the course of writing assembly-level programs. For example, the fastest way to determine whether an unsigned integer is a power of 2 is:

x & (x-1)

If x is a power of two, the expression evaluates to zero; for other numbers it is nonzero. This section of the book can take days to finish because, for the reader who enjoys recreational bit-wrangling, it is tempting to take a pencil and test each of Warren's assertions. Like many of Warren's formulas, x & (x-1) is not an obvious solution at first glance, but once you work through it and look at the bits, you can see that it works. In this instance, I tried 8 (a power of 2) and 6 (not a power of 2):

The book goes on to give formulas for counting the 1-bits in a word, isolating the rightmost 1-bit, flipping the rightmost contiguous string of 1-bits, shifting and propagating bits, reversing the order of bits and bytes, transposing a matrix, and so on. More than half the book is a collection of methods for doing basic calculations efficiently. Code examples are given either in C or in a simplified assembly language the book defines for 32-bit RISC machines.