Bug 56: A Spanner In The Works
- This illustrates two classic methods for bit indexing: de Bruijn hashing and floating point normalization.
- The code computes the smallest half-open interval [lo, hi) that contains the indexes of all the 1-bits of x.
- If x has no 1-bits, the empty interval [0, 0) is returned. The index of the most-significant bit of x is 63.
- A 64-bit de Bruijn multiplier (with corresponding lookup table) is precomputed by recursive backtracking.
- Leiserson, Prokop, and Randall's de Bruijn hashing method yields the index of x's least-significant 1-bit.
- The most-significant 1-bit of x is found through conversion to IEEE 754 binary64 (double-precision) float.
- The 11-bit exponent of the float is isolated and the binary64 exponent bias (1023) is subtracted from it.
- The code puts 31 or fewer explicit 1-bits into a 52-bit binary64 mantissa, so rounding is not a problem.
Fix The Tiny Bug In This Go Code: