This Trick Computes Leading Zeros with One Floating-Point Subtraction
Vectorized CLZ and CTZ
A clever floating-point hack computes clz and ctz without dedicated instructions. By embedding an integer into the mantissa of a double and subtracting, you can extract the leading-zero count from the exponent. The vectorized version runs at 0.45 ns per iteration on Haswell, beating the scalar 1 ns. For ctz, a similar trick isolates the lowest set bit. A de Bruijn sequence approach offers higher throughput, and a 64-bit variant using pshufb and psadbw handles ctz(0)=64 correctly.
Floating-point exponents are biased logarithms of their values. By substituting a 32-bit number x into the mantissa of some value 2^k, we get a double representing 2^k (1 + 2^-52 x). We can then subtract 2^k as a double to get 2^(k-52) x. Extracting the exponent gives k - 52 + 31 - clz(x), from which clz can be computed with a bitwise subtraction.