Vectorized CLZ and CTZ

The write-up presents fast SIMD implementations of CLZ (count leading zeros) and CTZ (count trailing zeros) using bit-level and floating-point tricks to avoid scalar instructions. For CLZ, a 64-bit double exponent trick embeds a 32-bit input into a double’s mantissa, subtracts a biased power-of-two, and extracts the exponent to compute clz; this requires 64-bit floats so it only works up to 52-bit inputs. The author shows the AVX assembly sequence, reports throughput gains (e.g., Haswell ~0.45 ns/iter vs 1 ns scalar, Alder Lake ~0.29 ns/iter), and notes platform caveats (AMD’s cheap lzcnt and AVX-512 vplzcntd as alternatives).

For CTZ, the primary approach isolates the low set bit with x xor (x−1), then uses a similar double-exponent trick with carefully chosen bit-mixed constants to avoid subnormals and to handle x=0; the AVX code and measured latencies are given (Haswell ~0.49 ns/iter, Alder Lake ~0.35 ns/iter). Added alternatives include a vectorized de Bruijn method using vpshufb and a magic multiplier (0xf0a6f0a7) that doubles throughput and a 64-bit specialized solution using pshufb plus vpsadbw to compute per-byte inverted popcounts, returning ctz(0)=64 at ~0.63 ns on Haswell. The write-up compares these options, discusses instruction choices (vpternlogq, vpopcntd) and trade-offs across CPU microarchitectures.