It’s all in the details

Hacker’s Delight by Henry S Warren

There are loads of books out there on the subject of algorithms, but there aren’t many that look in detail at algorithms and tricks which use the magic of 2’s complement arithmetic and the various shift and logic operations that have been supported by processors since the early days.

The arithmetic that is supported by a modern processor is a funny beast. Due to the choice of the most significant bit as a sign bit (which is one when the the value is negative), and the choice of all zeros representing zeros, this leaves more representable numbers that are strictly negative than those that are strictly positive. This leads to the interesting effect of the negation of the most negative number (-2147483648 on a 32 bit machine) being itself. This allows all kinds of interesting tricks in the book.

Chapter one starts with tricks revolving around the representation of a number – finding the rightmost 1 bit, turning off the rightmost 1 bit and identifying the trailing zeros in the bit pattern. There’s also the interesting theorem: “A function mapping words to words can be implemented with word-parallel add, subtract, and, or and not if and only if each bit of the result depends only on bits at and to the right of each input operand.” This chapter also considers the relationship between signed and unsigned comparisons, overflow detection (in the absence of a flags register set by the arithmetic operations), shifting operations and the implementation of multi-word arithmetic. There’s also material that looks at which comparisons can be implemented without needing the use of branch instructions which can cause pipeline stalls on modern architectures, and also considers code sequences to be better when they exhibit instruction level parallelism.

There are then chapters on powers of 2 boundaries (rounding up and down to them), and arithmetic bounds and how they propagate through add, subtract and logical operations. Chapter 5 covers ways of counting bits, and shows off some of tricks to divide and conquer, carrying out calculations in segments of the word and later merging the results. The example below counts the number of 1 bits in the word.

uint x = 0x8007;
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);

The next chapters covers tricks for searching words, for example finding a null byte string terminator in a word of ASCII characters and then algorithms for rearranging the bits of a word (for example reversing it). This is followed by chapters on multiplication and division, which covers in detail the tricks of converting a division by a constant into a multiplication (calculating the high word of the result) followed by a shift and possible adjustment by a constant.  The author proves the validity of the transformation, which is something I’ve not seen before.

This would be enough material, but there are further chapters on implementing the elementary functions (such as integer square and cube root), floating point, unusual number bases, Hilbert’s curve and formulas for the primes.

This book is a really good read. It’s full of interesting and illuminating tricks, and just shows how interesting the field of compiler optimisation can be.

This entry was posted in Computers and Internet. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s