Floating-point exponents double as a logarithm to vectorize CLZ and CTZ

Floating-point hardware as a bit scanner

Count-leading-zeros (clz) and count-trailing-zeros (ctz) report how many zero bits sit at the top or bottom of a fixed-width integer. Modern CPUs expose them as instructions, but they are not equally cheap everywhere: as purplesyringa notes in a blog post that reached the Hacker News front page, tzcnt on Intel's Arrow Lake carries a latency of three cycles. While building an FPU emulator, the author worked out how to replace a ctz with floating-point arithmetic, then realized the idea generalizes into a vectorizable stand-in for both operations on AVX2-class hardware, which has no integer vector equivalents.

Turning exponents into logarithms

The core observation is that an IEEE-754 exponent field is essentially a biased base-2 logarithm you get for free. For clz, the post's Rust snippet takes a double equal to 2^-970, ORs the 32-bit input into its low mantissa bits — producing 2^k(1 + x·2^-52) — and subtracts 2^k back out. The remainder's exponent field then encodes the position of the highest set bit, and clz falls out of a single integer subtraction. That particular exponent also makes x = 0 behave sensibly.

There is a structural limit: a double carries 52 mantissa bits, so the scheme only covers inputs up to 52 bits wide. 32-bit values fit; arbitrary 64-bit values do not.

Vectorized over four lanes, the entire function is five instructions: a broadcast of a bias constant, an OR against a constant, a vector subtract, a 52-bit right shift, and a final subtract. No lookup tables, no lane-crossing shuffles.

ctz by isolating the lowest set bit

For ctz, the post leans on the classic identity x ^ (x - 1), which keeps only the lowest set bit; ctz is then the base-2 log of that value, readable through the same exponent trick. The constant engineering is the hard part. Adding 2^32 - 1 to x rather than subtracting 1, with 2^32 pre-mixed into the constant's mantissa, makes x = 0 return 32; a single preset mantissa bit keeps odd inputs — whose isolated pattern is zero — from landing on a slow subnormal result. The author concedes that arranging those bits took considerable iteration.

This variant needs one instruction more than clz. AVX-512's vpternlogq could fold a step away, but the post argues that if AVX-512 is available you may as well run vpopcntd over (x - 1) & ~x instead.

Reader-contributed alternatives

The post grew through two updates. Nikolay Malkovsky pointed out that de Bruijn sequences also vectorize: multiply the isolated bit by a magic constant, shift, and look the answer up with vpshufb. Because vpshufb cannot cross 16-byte lanes, a true 32-byte table is impossible, so the author repeats a 16-bit de Bruijn sequence twice, derives the low four bits of ctz from the lookup, and adds 16 or 32 depending on which half-words are entirely zero. The constant 0xf0a6f0a7 is reportedly one of just four that work. It runs at 1 ns per iteration on Haswell (0.7 ns on Alder Lake) but has twice the throughput per pass, so it can still come out ahead when it avoids shuffles; relaxing x = 0 handling brings it to 0.82 ns.

A second update, co-developed with arya dradjica, tackles 64-bit inputs: a pshufb-driven table produces inverted popcounts of each byte's two nibbles, and vpsadbw — which aggregates exact eight-byte groups — both sums and un-inverts them in one step, correctly returning ctz(0) = 64 at 0.63 ns on Haswell. That shape is specific to 64-bit lanes; for 32-bit inputs the de Bruijn version remains fastest.

What the numbers show

On the author's Haswell, clz runs at 0.45 ns per iteration against 1 ns for the scalar version, and ctz at 0.49 ns (2.3 ns when latency-bound). Ian Qvist measured Alder Lake at 0.29 ns versus 0.85 ns scalar for clz, and 0.35 ns for ctz. Under latency-bound conditions the scalar version can win, and on AMD, cheap lzcnt means scalar code likely dominates — though Zen's AVX-512 support offers vplzcntd outright.

Why it matters

AVX2 has no vector clz or ctz, so throughput-oriented code that scans bits heavily — emulators like the author's FPU project being a concrete example — has been forced into scalar extraction or awkward shuffle-based workarounds. The post demonstrates a third path: the floating-point datapath doubles as a batched logarithm engine, and its exponent can be harvested with nothing but an OR, a subtract and a shift. The broader lesson is that a slow-instruction problem sometimes has a software answer — but the benchmark caveats in the post, from latency chains to AMD's cheap scalar paths, are a reminder that any such trick lives or dies by measurement on the exact target CPU.