BUGFIX-66

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:

func span(x uint64) (lo, hi int) { if x == 0 { return } var ( lowest1 = x & -x shiftHi = mul * lowest1 shiftLo = shiftHi >> 58 ) lo = int(lut[shiftLo]) if x>>32 != 0 { x >>= 32 hi = 32 } var ( float = float64(int64(x)) e11m52 = math.Float64bits(float) exp = int(e11m52 >> 52) ) hi += exp - 1023 return } var ( mul uint64 lut [64]uint8 ) func init() { var ( deBruijn1 func(used, seq, bit uint64) bool deBruijn2 func(used, seq, bit uint64) bool ) deBruijn1 = func(used, seq, bit uint64) bool { if bit == 0 { mul = seq return true } if bit--; deBruijn2(used, seq, bit) { return true } seq |= 1 << (63 - bit) return deBruijn2(used, seq, bit) } deBruijn2 = func(used, seq, bit uint64) bool { var ( idx = seq << bit >> 58 mask = uint64(1) << idx ) if used&mask == 0 { used |= mask if deBruijn1(used, seq, bit) { lut[idx] = uint8(bit) return true } } return false } if !deBruijn1(0, 0, 64) { panic(nil) } }

To receive a hint, submit unfixed code.