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

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

Fig. 4-4. Maximum value of

Fig. 4-5. Minimum value of

Fig. 4-6. Maximum value of

P. 77. Minimum value of

P. 77. Maximum value of

P. 78. Minimum value of

P. 78. Maximum value of

P. 82-87. Population count algorithms.

Fig. 5-5. Computes pop(

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

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 2

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

Figs. 11-7 to 11-13. Integer log base 10.

Fig. 12-1. Division in base −2.

P. 436. Convert a base −1 +

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 (

Fig. 16-6. Lam and Shapiro method for computing (

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 (

Fig. 16-8. Parallel prefix method for computing (

Fig. 16-9. Program for computing

Fig. 16-10. Lam and Shapiro method for computing

---. 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

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.