Cairn
algorithms · bit manipulation · O(1) time — one AND, one 32-bit multiply, one shift, one 32-entry table lookup, independent of input (contrast a naive bit-scan loop's O(t) time, t = trailing zero count, up to 32); O(1) space — one fixed 32-entry lookup table

↩ back to Bit Manipulation

Counting Trailing Zeros with a de Bruijn Sequence

This is the third entry in Bit Manipulation, and the first that doesn't count bits — it finds one. Brian Kernighan's Algorithm and SWAR Popcount both answer "how many bits are set" (population count). This page answers a different, equally common question: given a nonzero 32-bit integer, which bit is the lowest one set — equivalently, how many trailing zero bits does it have? That's usually called count trailing zeros (ctz) or bit-scan-forward. It shows up whenever code uses a single bit to mean "the next thing": a chess engine scanning a bitboard for its next piece, a free-list bitmap allocator finding its lowest free slot, or checking how many low bits of an address are zero to test alignment to a power of two.

Fenwick Tree, already on this site, isolates exactly this bit on every update and query — lowbit(i) = i & -i — but it only ever uses the isolated value, never asks which position it sits at. This page answers that companion question: given the isolated bit, what index is it at? The obvious approach shifts right one bit at a time until an odd number falls out, taking one iteration per trailing zero — fast when there are few, slow when there are many. The trick here, built from a de Bruijn sequence, answers it in four fixed steps no matter how many trailing zeros there are: one AND, one 32-bit multiply, one shift, one table lookup.

Try it

Pick a 32-bit number (or a preset), then step through the four stages. Each stage keeps the previous 32-bit register visible; stage 3 highlights the 5 bits the next step reads off as a table index (reused styling, not a color this site invented for this page — the same border this site already uses to mark "being read, not yet decisive on its own"). The log line underneath cross-checks the table's answer against an independent naive loop on every step, live.

Stage 0 of 4 — n, as 32 bits

Why it works

A de Bruijn sequence B(2, 5) is a cyclic string of 32 bits in which every one of the 32 possible 5-bit windows — read 5 bits at a time, wrapping from the end back to the start — appears exactly once. Lay one out as an ordinary (non-cyclic) 32-bit integer C. Multiplying C by a power of two 2k shifts its bit pattern left by k positions; keeping only the low 32 bits of that product (the bits that would overflow past position 31 are simply discarded, the same 32-bit truncation JavaScript's >>> and Math.imul already do) and reading off the top 5 bits of what's left gives a 5-bit window into C's own cyclic pattern — one that's unique to k, precisely because C has the de Bruijn property. Do this once for every one of the 32 single-bit values 1, 2, 4, …, 231 and record which index each one lands on, and the resulting 32-entry table inverts the lookup: index → k.

Proving that 32-bit truncation really does behave like a window into a cyclic sequence is a short induction on the shift amount that most references state without repeating. This page verifies the behavior instead: every one of the 32 single-bit cases is checked individually below, and the reference implementation is fuzzed against an independent naive loop across millions of random 32-bit integers with zero mismatches (see Pitfalls).

Worked example: k = 5, so v = 25 = 0x00000020. The constant used throughout this page is C = 0x077CB531 — one of several 32-bit integers that happen to satisfy the de Bruijn property for 5-bit windows (verified by brute force, not taken on faith — see the reference implementation's own table-building loop). Math.imul(0x20, 0x077CB531), truncated to 32 bits, is 0xEF96A620 — in binary, 11101111100101101010011000100000. Its top 5 bits are 11101, decimal 29. TABLE[29] is 5 — the correct answer, recovered without ever looping over the 27 bits in between.

Reference implementation

const DEBRUIJN32 = 0x077CB531;

// Build the lookup table once: for every single-bit value 2^k, record which
// index the multiply-shift trick produces. If any two values ever collided on
// the same index, this constant would not be a valid de Bruijn sequence for
// 5-bit windows — none do, checked here, not assumed.
function buildDeBruijnTable(c) {
  const table = new Array(32).fill(-1);
  for (let k = 0; k < 32; k++) {
    const v = (1 << k) >>> 0;
    const index = Math.imul(v, c) >>> 27;
    if (table[index] !== -1) throw new Error('not a valid de Bruijn constant');
    table[index] = k;
  }
  return table;
}
const CTZ_TABLE = buildDeBruijnTable(DEBRUIJN32);

function countTrailingZeros(n) {
  n = n >>> 0;
  if (n === 0) return 32;                       // convention: no set bit
  const lowest = n & (-n);                        // isolate the lowest set bit
  return CTZ_TABLE[Math.imul(lowest, DEBRUIJN32) >>> 27];
}

Pitfalls

Skipping the isolation step is wrong almost every time, not just at the edges. The multiply-shift trick only ever encodes a single bit's position — feed it n directly instead of n & (-n) and it's reading a window built for a different value entirely. Checked directly (Node, 5,000,000 random 32-bit integers, each checked against an independent naive loop): skipping isolation disagrees with the correct answer on 96.88% of them. The few percent that still happen to agree are coincidences, not a sign the step is optional — every one of the 32 single-bit inputs still needs it dropped to see why: n & (-n) is a no-op exactly when n is already a power of two, and almost no random 32-bit integer is.

n = 0 needs its own guard, or the table silently answers 0 instead of 32. 0 & (-0) is 0, and Math.imul(0, DEBRUIJN32) >>> 27 is also 0 — CTZ_TABLE[0] happens to hold 0 (the entry for k = 0), so an unguarded call on zero returns 0, claiming the lowest set bit is bit 0 when there is no set bit at all. This page follows the same convention a 32-bit hardware TZCNT instruction does: ctz(0) = 32, one past the last valid bit position — but any convention needs an explicit n === 0 check first, the table has no way to represent "no bit" on its own.

The final shift must be unsigned (>>>), not signed (>>) — using the signed version doesn't just misalign the index, it returns undefined. Math.imul returns a signed 32-bit result, so whenever its top bit is 1, a signed >> 27 sign-extends and produces a negative number; indexing a JavaScript array with a negative number never throws, it just returns undefined — which then flows silently out of the function as the "trailing zero count." Checked directly (same 5,000,000-integer run): the signed version disagrees with the correct answer on 2.93% of random inputs, and in every single one of those cases the wrong answer is literally undefined, not merely a wrong number — worth knowing before trusting a one-character diff that looks harmless.

Measured against the naive loop (Node, 3,000,000 random 32-bit integers per pattern, 4 warm-up passes then the median of 9 trials, averaged across 3 independent process runs for stability):

input patternnaive loopde Bruijn
trailing zeros 0–329.6ms39.5ms
uniform random74.7ms48.9ms
trailing zeros 24–3188.4ms34.0ms

The naive loop's own time swings almost 3x between its two extremes — cheapest exactly when it does the least looping, as expected. The de Bruijn version swings far less, at most 1.4x between its own fastest and slowest pattern here, since it has no loop to make longer. It isn't perfectly flat the way SWAR Popcount's pure shift-and-mask steps are, though — unlike SWAR, its last step is a real memory read (the table lookup), and a handful of cycles of cache/microarchitectural variance show up even though the step count never changes.

The "uniform random" row is the one that looks backwards at first: it runs slower than "trailing zeros 0–3" even though a uniform random 32-bit integer has a lower average trailing-zero count (exactly 1, confirmed by a direct 5,000,000-sample count — half of all nonzero integers are already odd) than the fixed 0–3 range tested on the other row (average 1.5). As Brian Kernighan's Algorithm's own page found measuring a different loop over the same category: branch prediction, not average iteration count, decides a tight bit-manipulation loop's real speed. The 0–3 pattern's loop always exits within four iterations, a narrow, learnable range; uniform random's loop exits anywhere from 0 to 31 iterations, unpredictably — the branch predictor mispredicts the loop's exit far more often on the second pattern, even though it does less total looping on average.

Complexity

Time: O(1) — exactly one AND, one 32-bit multiply, one shift, and one array read, regardless of the input. Contrast the naive shift-until-odd loop's O(t), where t is the number of trailing zero bits (worst case O(w) for a w-bit word). Real hardware answers this question with a single dedicated instruction (TZCNT/BSF on x86, a leading-zero-count instruction plus the same n & (-n) isolation on ARM) that this site still can't invoke from plain JavaScript — the same gap SWAR Popcount already notes for a dedicated POPCNT. Space: O(1) — one fixed 32-entry lookup table, independent of the word width's own growth beyond 32 bits (a 64-bit version needs its own wider constant and a 64-entry table — see Beyond 32 bits, below).

Beyond 32 bits

Everything above tops out at 32 bits because JavaScript's bitwise operators do too — Math.imul, <<, and >>> all truncate their result to 32 bits by specification, regardless of what width the problem actually needs. A 64-bit trailing-zero-count needs a 64-bit multiply that doesn't truncate early, which means BigInt throughout, and a wider de Bruijn sequence: B(2, 6) instead of B(2, 5), since 26 = 64 distinct 6-bit windows are needed to cover 64 bit positions instead of 32.

The 32-bit constant above was picked from a known-good value and then checked for validity — this section builds its 64-bit counterpart from scratch instead of reaching for another remembered constant. The standard construction (often credited to Fredricksen, Kessler, and Maiorana) builds a de Bruijn sequence directly: grow the lexicographically largest string whose every rotation is lexicographically no smaller, backtracking exactly when forced, which turns out to visit every possible window exactly once by construction. Packing the resulting 64-bit sequence into an integer and reading off its top 6 bits after each multiply-shift is the exact same trick as the 32-bit version, just wider:

// Standard recursive de Bruijn sequence construction (Fredricksen-Kessler-Maiorana).
// Builds B(k, n) for any alphabet size k and window length n -- used here with
// k=2, n=6 to get a 64-bit cyclic sequence covering every 6-bit window exactly once.
function deBruijnSequence(k, n) {
  const a = new Array(k * n).fill(0);
  const sequence = [];
  function db(t, p) {
    if (t > n) {
      if (n % p === 0) for (let i = 1; i <= p; i++) sequence.push(a[i]);
    } else {
      a[t] = a[t - p];
      db(t + 1, p);
      for (let j = a[t - p] + 1; j < k; j++) {
        a[t] = j;
        db(t + 1, t);
      }
    }
  }
  db(1, 1);
  return sequence;
}

const bits64 = deBruijnSequence(2, 6);          // 64 bits long, every 6-bit window exactly once
let DEBRUIJN64 = 0n;
for (const bit of bits64) DEBRUIJN64 = (DEBRUIJN64 << 1n) | BigInt(bit);
// DEBRUIJN64 = 0x0218a392cd3d5dbfn

function buildDeBruijnTable64(c) {
  const table = new Array(64).fill(-1);
  for (let k = 0; k < 64; k++) {
    const v = 1n << BigInt(k);
    const index = Number(BigInt.asUintN(64, v * c) >> 58n);
    if (table[index] !== -1) throw new Error('not a valid de Bruijn constant');
    table[index] = k;
  }
  return table;
}
const CTZ_TABLE_64 = buildDeBruijnTable64(DEBRUIJN64);

function countTrailingZeros64(n) {               // n must be a BigInt
  if (n === 0n) return 64;
  const lowest = n & -n;
  const index = Number(BigInt.asUintN(64, lowest * DEBRUIJN64) >> 58n);
  return CTZ_TABLE_64[index];
}

Same collision guard as the 32-bit table-builder, same zero-bit convention (ctz(0n) = 64, one past the last valid position), same isolation step — only the width, the window size, and the BigInt arithmetic change. Verified the same way the 32-bit version was: building the table from the sequence above threw no collision error (all 64 single-bit inputs land on 64 distinct indices), every one of the 64 individual single-bit cases (20 through 263) matches its expected position exactly, and 3,000,000 random 64-bit BigInt values checked against an independent naive shift-until-odd loop came back with zero mismatches.