Below is the C code for most of the programs that appear in HD, with test drivers.

To save this code on your machine using Internet Explorer, right-click a line below, click Save Target As..., set directory, delete ".txt" from the file name (optional), and click Save. On Firefox it's the same except click Save Link As... .

Page and figure numbers are for the second edition.

Fig. 2-1. Next higher number with same number of 1-bits.
Fig. 2-2. Determination of overflow of unsigned multiplication.
P. 36. Test for overflow of signed "long division."
---. Determines which of the 256 Boolean functions of three variables can be implemented with three binary Boolean instructions.
Fig. 3-1. Greatest power of 2 less than or equal to x, branch free.
Fig. 3-3. Least power of 2 greater than or equal to x.
Fig. 4-1. Propagating unsigned bounds through addition operations.
Fig. 4-1. Propagating unsigned bounds through subtraction operations.
Fig. 4-2. Propagating signed bounds through an addition operation.
Fig. 4-3. Minimum value of x | y with bounds on x and y.
Fig. 4-4. Maximum value of x | y with bounds on x and y.
Fig. 4-5. Minimum value of x & y with bounds on x and y.
Fig. 4-6. Maximum value of x & y with bounds on x and y.
P. 77. Minimum value of x ^ y with bounds on x and y.
P. 77. Maximum value of x ^ y with bounds on x and y.
P. 78. Minimum value of x | y with bounds on x and y (signed).
P. 78. Maximum value of x | y with bounds on x and y (signed).
P. 82-87. Population count algorithms.
Fig. 5-5. Computes pop(x) − pop(y).
Fig. 5-6. Determines which word has the larger population count.
Fig. 5-5 p. 73 of HD 1st ed. Counting 1-bits in an array.
Figs. 5-7 and 5-9. Counting 1-bits in an array.
P. 95. Indexing a moderately sparse array.
P. 96-97. Various parity algorithms.
P. 99-106. Number of leading zeros algorithms.
P. 107-113. Number of trailing zeros algorithms.
Fig. 5-28. Gosper's loop-detection algorithm.
P. 117-122. Find first 0-byte or first value in a given range.
---. Find rightmost 0-byte.
P. 123 and Fig. 6-5. Find first string of 1-bits of a given length.
Figs. 6-6 and 6-7. Find longest string of 1's in a word.
Fig. 6-8. Find shortest string of 1's in a word (optionally, at least as long as a given integer n).
P. 129-134. Reversing bits. New code here.
P. 138. Incrementing a reversed integer.
P. 140-141. Shuffling bits.
P. 143-145. Transposing an 8x8 bit matrix.
P. 147-150. Transposing a 32x32 bit matrix.
P. 151-153. Compress, or generalized extract.
P. 156. Compress left.
Fig. 7-12. Inverse of the compress (right) function.
P. 162. Permuting by sheep and goats operation, little-endian.
P. 162. Permuting by sheep and goats operation, big-endian.
Fig. 8-1. Multiword integer multiplication, signed.
Fig. 8-1 top portion. Multiword integer multiplication, unsigned.
Fig. 8-2. Multiply high signed.
P. 174. Multiply high unsigned.
---. Multiply, 32x32 ==> 64, signed.
---. Multiply, 32x32 ==> 64, unsigned.
---. Multiply, 64x64 ==> 128, unsigned.
Fig. 9-1. Multiword integer division, unsigned, for a 32-bit machine.
Like Fig. 9-1. Multiword integer division, unsigned, for a 64-bit machine.
Fig. 9-2. Divide long unsigned, shift-and-subtract algorithm.
Fig. 9-3. Divide long unsigned, using fullword division instruction.
Fig. 9-4. Divide long signed, using divide long unsigned.
Fig. 9-5. 64/64 ==> 64 division, unsigned and signed.
Fig. 10-1. Computing the magic number for signed division.
Figs. 10-2 and 10-3. Computing the magic number for unsigned division.
---, Computing the magic number for signed division (Python).
Fig. 10-4, Computing the magic number for unsigned division (Python).
Figs. 10-4 and 10-5. Multiplicative inverse modulo 232.
Figs. 10-7 to 10-15. Unsigned division by constants.
Figs. 10-16 to 10-22. Signed division by constants.
Figs. 10-23 to 10-29 and 10-34 to 10-41. Unsigned remainder of division by constants.
Figs. 10-30 to 10-33 and 10-42 to 10-46. Signed remainder of division by constants.
Figs. 10-47 to 10-49. Exact division method of division by constants.
Figs. 11-1 to 11-4. Integer square root.
Fig. 11-5. Integer cube root, hardware algorithm.
P. 434. Integer cube root of a 64-bit integer.
Fig. 11-6. Computing xn by binary decomposition of n.
Figs. 11-7 to 11-13. Integer log base 10.
Fig. 12-1. Division in base −2.
P. 436. Convert a base −1 + i integer to a + bi, a and b real integers (Python).
Figs. 14-5 to 14-7. Cyclic Redundancy Check (CRC-32).
Figs. 15-1 and 15-2. SEC-DED Hamming code for 32 information bits.
Fig. 16-3. Hilbert curve generator.
Fig. 16-4. Driver program for Hilbert curve generator.
Fig. 16-5. Program for computing (x, y) from s.
Fig. 16-6. Lam and Shapiro method for computing (x, y) from s.
P. 363. Variation of Fig. 14-6 that avoids a branch.
Fig. 16-7. Code to verify the logic circuit of Fig. 14-7. NB error in first edition, first and second printings (Fig. 14-7): The title of this figure should be "Logic circuit for computing (x, y) from s."
Fig. 16-8. Parallel prefix method for computing (x, y) from s.
Fig. 16-9. Program for computing s from (x, y).
Fig. 16-10. Lam and Shapiro method for computing s from (x, y).
---. Variation of Fig. 16-10 that avoids a branch.
Fig. 16-11. Program for taking one step on the Hilbert curve.
Fig. 16-12. Code to verify the logic circuit of Fig. 14-12.
---. Right-to-left algorithm for computing s from (x, y).
Some Hilbert curves (not a program).
Fig. 17-1. Approximate reciprocal square root of an IEEE float.
P. 447. Approximate square root of an IEEE float.
P. 448. Approximate cube root of an IEEE float.
---, Approximate reciprocal of an IEEE double.
---. Montgomery multiplication.

Home