Hacker's Delight (2002)

Hacker's Delight is a software algorithm book by Henry S. Warren, Jr. first published in 2002. It presents fast bit-level and low-level arithmetic algorithms for common tasks such as counting bits or improving speed of division by using multiplication.

Background

The author, an IBM researcher working on systems ranging from the IBM 704 to the PowerPC, collected what he called "programming tricks" over the course of his career. These tricks concern efficient low-level manipulation of bit strings and numbers. According to the book's foreword by Guy L. Steele, the target audience includes compiler writers and people writing high-performance code.

Summary

Programming examples are written in C and assembler for a RISC architecture similar, but not identical to PowerPC. Algorithms are given as formulas for any number of bits, the examples usually for 32 bits.

Apart from the introduction, chapters are independent of each other, each focusing on a particular subject. Many algorithms in the book depend on two's complement integer numbers.

The subject matter of the second edition of the book includes algorithms for

Basic algorithms for manipulating individual bits, formulas for identities, inequalities, overflow detection for arithmetic operations and shifts

Rounding up and down to a multiple of a known power of two, the next power of two and for detecting whether an operation crossed a power-of-two boundary

Checking bounds

Counting total, leading and trailing zeros

Searching for bit strings

Permutations of bits and bytes in a word

Software algorithms for multiplication

Integer division

Efficient integer division and calculating of the remainder when the divisor is known

Integer square and cube roots

Unusual number systems, including base −2

Transfer of values between floating-point and integer

Cyclic redundancy checks, error-correcting codes and Gray codes

Hilbert curves, including a discussion of applications

Style

The style is that of an informal mathematical textbook. Formulas are used extensively. Mathematical proofs are given for some non-obvious algorithms, but are not the focus of the book.

Reception

Overall reception has been generally positive.

Publication history

The book was published by Addison-Wesley Professional. The first edition was released in 2002 and the second in 2013.

Japanese language edition of this book was published by SIBaccess Co. Ltd., in 2004.