This site's Bit Manipulation category has three entries answering two different questions — Brian Kernighan's Algorithm and SWAR Popcount both count set bits (population count); Counting Trailing Zeros with a de Bruijn Sequence finds the lowest set bit's position instead. Read problem by problem, that looks like two separate stories. Read by mechanism instead, the same four shapes keep reappearing, and that's the more useful way to decide what to reach for the next time a raw integer's bit pattern, not its value, is the thing worth exploiting.
Every reference implementation across these three pages falls into one of four families:
| Mechanism | Shape | Built for popcount | Built for ctz |
|---|---|---|---|
| Fixed full-width scan | always exactly w steps, checks every position whether or not it's set | naive scan, O(w) | — (see below) |
| Data-dependent, one-bit-at-a-time loop | steps scale with a value-dependent quantity, no table, no fixed arithmetic | Kernighan's n & (n-1) clear-lowest loop, O(k) set bits | shift-right-until-odd, O(t) trailing zeros |
| Fixed-step arithmetic fold | a constant number of shift/mask/add steps, no loop, no table, no memory access | SWAR, 5 fixed steps | — (not built) |
| Precomputed-table lookup | a constant number of table reads, built once | byte lookup table, 4 reads | de Bruijn multiply-and-lookup, 1 multiply + 1 read |
The two blank cells aren't an oversight to fill in later — they're a real structural asymmetry
between the two questions, worth naming rather than quietly leaving unexplained. Population count has
to look at every one of a word's bits to sum them, so "check all w positions,
unconditionally" is a meaningful, honest baseline on its own. Finding the position of the
lowest set bit only ever needs to look as far as that one bit — even the "obvious" approach short-circuits
the instant it finds a 1, which is exactly why the de Bruijn page's own naive baseline is already the
data-dependent shift loop, not a fixed full sweep. A fixed-step arithmetic fold for ctz, the SWAR row's
empty twin, is a genuinely open gap: nothing on this site builds one, and it isn't named here as a
promise to close later — see this site's own content-picking discipline about not inventing a
backlog item just to fill a table cell.
Both data-dependent loops in the row above were measured on their own page, independently, and both measurements turned up the identical surprise: the thing that actually decides how fast a tight bit-manipulation loop runs isn't how many iterations it does on average — it's how predictable the loop's own exit point is.
Brian Kernighan's Algorithm's own page measured the naive scan — fixed at exactly 32 iterations no matter what, so the iteration count can't be the explanation at all — and still found its time swing 2.6–3.3x between three fixed bit patterns (135–172ms) and uniform random bits (448ms). A monotonous all-0 or all-1 branch inside the loop is cheap for the CPU to predict every time through; a 50/50 random bit on every single iteration isn't, and that misprediction cost is invisible to an iteration count that never changes.
The de Bruijn CTZ page's own naive shift-until-odd loop shows the same effect from the opposite direction. Its measured rows: trailing zeros 0–3 at 29.6ms, uniform random at 74.7ms, trailing zeros 24–31 at 88.4ms. The middle row looks backwards at first — uniform random's own average trailing-zero count (1, since half of all nonzero integers are already odd) is lower than the fixed 0–3 range's average (1.5), yet it runs slower. The 0–3 range always exits within four iterations, a narrow range the branch predictor learns quickly; uniform random exits anywhere from 0 to 31 iterations, unpredictably, and that unpredictability — not the average trip count — is what the page's own numbers charge for.
Neither page set out to prove a category-wide rule; each explained its own loop. Read together, though, it's the same mechanism showing up on two unrelated loops solving two different problems, which is a much stronger signal than either page's own single data point: a tight, data-dependent bit-manipulation loop's real-world cost depends on how predictable its exit condition is, not just on how many times it runs on average, and no Big-O notation on either page's own Complexity section captures that at all.
SWAR Popcount and the de Bruijn CTZ trick both buy their way out of the branch-prediction problem above by never branching on the input's value in the first place — but they pay for that guarantee in two different currencies. SWAR's five steps are pure register arithmetic: shift, mask, add, nothing else, no memory touched beyond the input integer itself. The de Bruijn trick's own last step is a real array read. Its own Pitfalls section says so directly: it "isn't perfectly flat the way SWAR Popcount's pure shift-and-mask steps are... 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 byte lookup table sitting on Brian Kernighan's Algorithm's own page pays that same memory-read cost, four times over instead of once — and still comes out fastest in every measured case on that page and on SWAR's. Precomputed tables win on raw speed here precisely because they move the real work to build time; the cost that's left at call time is a cache lookup, not an input-dependent branch, and a cache lookup turns out to be cheaper than the arithmetic SWAR does to avoid needing a table at all — by 3–6% on SWAR Popcount's own measurements, consistently across four tested patterns.
All three pages only ever operate on a 32-bit word — matching plain JavaScript's own
&/>>>/Math.imul, which silently truncate anything
wider. Each page is explicit that its own trick doesn't just stop working past 32 bits — it needs
different amounts of new work to extend, and the ranking from the section above doesn't survive the
jump unchanged. SWAR Popcount's own Pitfalls section: the same five-step shape "generalizes to 64
bits (six steps...), but it needs its own wider constants... and BigInt arithmetic." The
de Bruijn CTZ page's own Complexity section: a 64-bit version "needs its own wider constant and a
64-entry table" — a different de Bruijn sequence for 6-bit windows, not just a wider version of the
5-bit one already built, and (unlike when this guide first shipped) that 64-bit version is now built
on that page, with BigInt throughout since plain JavaScript numbers truncate past 32 bits. The byte lookup table is the one mechanism that doesn't need
any of that: its own Complexity section already states it as O(w / b) for a fixed
b-bit table index, which means extending to 64 bits is just running the identical
256-byte table four more times (8 lookups instead of 4), not deriving a new constant or switching
number representations. The fastest fixed-cost mechanism at 32 bits is also the cheapest one to grow —
not a coincidence this guide can resolve, just a second axis worth weighing alongside raw speed before
picking one.
| Mechanism | Cost shape | Memory touched | Reach for it when |
|---|---|---|---|
| Fixed full-width scan | O(w), always |
none | never for real use — it's the correctness oracle every other mechanism on these pages was checked against, not a production choice |
| Data-dependent one-bit loop (Kernighan / shift-until-odd) | scales with a value-dependent quantity (k set bits, or t trailing zeros) — and its real-world cost rides on how predictable that quantity's distribution is, not just its average |
none | the input is usually sparse (few set bits, or few trailing zeros) and nothing about the value needs to stay secret from a timing observer — see Constant-Time vs. Data-Dependent Execution for when that second condition fails |
| Fixed-step arithmetic fold (SWAR) | O(log w) fixed steps, every input |
none | a fixed cost matters but a precomputed table isn't available or wanted — no allocation, no cache line to warm, portable to anywhere plain integer arithmetic runs |
| Precomputed-table lookup (byte table / de Bruijn) | O(1) fixed, after a one-time table build |
one small, fixed-size table (256 bytes for the byte table; a 32-entry array for de Bruijn) | raw speed is the priority and a tiny fixed table is an acceptable cost — fastest on every pattern measured on both pages it appears on, and (for the byte table specifically) the cheapest of the four to extend past 32 bits |