Hacker's Delight.

Henry S. Warren, Jr., Addison-Wesley Publishing Co., Boston, MA (2003). 336 pp. (ISBN 0-201-91465-4).

At some point during his more than four decades with IBM, Hank Warren began to compile a book of secrets. Judging only from the title, one might be concerned that both the writing and reading of this book could be a less than career-enhancing proposition. But in fact a number of readers will find that Hacker's Delight is an enormously useful resource, and they might very well wonder how they ever got along without it.

To begin, we will cite an example from our own experience. If you have no idea what a bit or byte is, then you might want to skip this review. If you at least understand the problem, continue reading. But if you find yourself scratching your head, spending five minutes trying to show that the result can't possibly be right, then jump with delight when you realize that it is, run right out and buy the book.

In order to cut string function simulation time for a machine project, we needed the shortest possible in-line code sequence that determines if a 32-bit word contains at least one O-byte. It is a surprisingly devilish problem, but one that has an elegant solution on page 93 of Hacker's Delight: Define y = f(x) by

y = (x & 0x7F7F7F7F) + 0x7F7F7F7F;

y = ~(y [absolute value of x] 0x7F7F7F7F); Then y is 0 if and only if x has no 0-byte,

This solution uses a slightly delicate mix of logic and arithmetic, one of the themes of the book. I suspect that the vast majority of programmers, even given a whole day, would not be able to come up with it. Moreover, until the publication of Hacker's Delight, they most likely would not even know where to look.

Among the several dozen topics treated by Dr. Warren in the first 12 chapters are sections on overflow, the counting and rearranging of bits and bytes, and multiword arithmetic. Explicit and very efficient code is given to extract bits under mask, to permute bits, and to multiply bit matrices. The longest and most detailed sequence treats signed and unsigned integer division. Many programmers who try to write fast correct code in this area end up wondering if they should start looking for another line of work. Dr. Warren begins with some simple examples and then moves to the general technique of correction after multiplication by "magic" numbers. The mathematics are included, but the reader who just wants to get the job done can go directly to the algorithm and code sections.

The last 60 pages deal with topics in which Dr. Warren just happens to be interested, and they add an eccentric charm to the book. A short discussion of floating point representation leads to the question of how the leading digits of numbers in hex representation are distributed, and then to a concise proof that 30 percent of the decimal numbers arising from natural distributions begin with the digit one. A chapter on Gray Codes shows how to count with them and how to convert to and from binary. There is a treatment of Hilbert curves, along with programs that generate their approximations. Finally, Dr. Warren's account of the enumeration of primes by means of simple functions is written with the suspense of a mathematical mystery. He presents the four formulae of Willans as a prelude to Wormell's formula, which eliminates all use of trigonometric and floor functions and does the job with only simple arithmetic. The reader who does not already know this will be amazed.

Hacker's Delight should be on the shelf of anyone writing compilers, mathematical libraries, code that has to run as fast as possible, or, as in the case of this reviewer, code that has a chance of running in the first place. Our friends in Fort Meade, Maryland, might want to order this book by the truckload.

Proofs are sprinkled throughout the text, but the main purpose is to present many years of algorithm and programming wisdom as clearly and concisely as possible.

The book contains about 60 C programs that implement many of the algorithms. Since copying the longer sequences by hand would likely introduce errors, Dr. Warren has thoughtfully created a Web site, HackersDelight.org, from which these and a hundred more codes can be downloaded. For those who would like to sample the book before purchasing it, Chapter 2 is included in its entirety. Chapter 3 can be found at the publisher's Web site, www.aw.com. Monty M. Denneau IBM Thomas J. Watson Research Center Yorktown, New York

Note--The books reviewed are those the Editor thinks might be of interest to our readers. The reviews express the opinions of the reviewers.