This is the site's first entry in a new Bit Manipulation category — tricks that work directly on an integer's binary representation rather than treating it as an opaque number. The problem here is population count (also called Hamming weight): given a 32-bit integer, how many of its bits are 1? It shows up any time a bitmask stands in for a set — counting how many items a subset-enumeration bitmask contains, measuring Hamming distance between two fixed-length codes, or just answering "is this a power of two" (exactly one bit set). Not to be confused with the unrelated Kernighan–Lin graph-partitioning heuristic — same Brian Kernighan, a different famous algorithm.
The obvious approach checks all 32 bit positions one at a time. Brian Kernighan's trick, popularized in The C Programming Language, does one subtraction-and-AND per set bit instead — zero extra work for every 0 bit the naive scan would otherwise have checked. The demo below runs both against the same number side by side, plus a third approach (a precomputed byte lookup table) that turns out to beat them both. A fourth approach — folding partial bit-counts into the word itself using only shifts, masks, and adds, no table and no loop — comes within a few percent of the lookup table's speed; see SWAR Popcount.
Pick a 32-bit number (or a preset), then step each grid forward one iteration at a time, or run it to completion. The naive grid scans every one of the original number's 32 bit positions left to right; the Kernighan grid shows the current working value, one bit disappearing per step, until nothing's left.
Subtracting 1 from any nonzero integer flips the lowest set bit to 0 and flips every bit below it
(which must all have been 0) up to 1 — every bit above the lowest set bit is untouched. ANDing that
with the original number keeps every untouched high bit exactly as it was, zeroes the lowest set bit
(1 AND 0), and zeroes everything below it too (0 AND 1, since those were already 0 in the original).
Net effect: n & (n - 1) clears exactly the lowest set bit and changes
nothing else.
Worked example: n = 12 is 0b1100. n - 1 = 11 is
0b1011 — the lowest set bit (value 4) became 0, and the single bit below it (value 1,
previously 0) became 1; the bit above (value 8) is unchanged in both. n & (n - 1) =
0b1100 & 0b1011 = 0b1000 = 8 — bit value 4 is gone, bits 8 and the rest are untouched.
Looping x = x & (x - 1) until x reaches 0 therefore takes exactly
k iterations, one per set bit, regardless of how many of the word's other bits are 0 —
unlike a fixed scan over all w positions, which pays for every 0 bit too.
// Naive: always exactly 32 iterations, one shift + mask + branch each.
function countBitsNaive(n) {
let count = 0;
for (let i = 31; i >= 0; i--) {
if ((n >>> i) & 1) count++;
}
return count;
}
// Brian Kernighan's algorithm: exactly k iterations, k = number of set bits.
function countBitsKernighan(n) {
let count = 0;
let x = n >>> 0; // treat as unsigned
while (x !== 0) { // see Pitfalls below for why this must be !== 0, not > 0
x = x & (x - 1); // clears the lowest set bit
count++;
}
return count;
}
// Byte lookup table: always exactly 4 iterations, any bit pattern.
const POPCOUNT_TABLE = (() => {
const t = new Uint8Array(256);
for (let i = 0; i < 256; i++) t[i] = (i & 1) + t[i >> 1];
return t;
})();
function countBitsLookup(n) {
const x = n >>> 0;
return POPCOUNT_TABLE[x & 0xff] + POPCOUNT_TABLE[(x >>> 8) & 0xff] +
POPCOUNT_TABLE[(x >>> 16) & 0xff] + POPCOUNT_TABLE[(x >>> 24) & 0xff];
}
while (x > 0) instead of while (x !== 0) silently undercounts
every number with bit 31 set — a real, verified bug, not a theoretical one. It looks safe:
x = n >>> 0 starts out non-negative. But JavaScript's &
operator always converts both operands — and its own result — to a signed 32-bit integer
before returning, regardless of how x was produced. The instant bit 31 is still set,
x & (x - 1) can come back negative even though plenty of set bits remain, and
x > 0 stops the loop right there. Checked directly: of 500,000 random 32-bit integers,
the buggy guard undercounts 49.9% of them (every one with bit 31 set) — e.g.
n = 0x80000003 (popcount 3) returns 1 instead of 3, because the very
first clear already flips the sign and the loop exits with two set bits still uncounted.
x !== 0 has no such blind spot — it doesn't care about sign, only about reaching zero.
Kernighan's own time still depends on the input — just not the way big-O makes it look, and it never loses to the naive scan even in its own worst case. Measured directly (Node, 3,000,000 random 32-bit integers per run, 5 warm-up passes then the median of 9 trials alternating call order to cancel cache-warming bias, repeated twice for stability):
| input pattern | naive scan | Kernighan | lookup table |
|---|---|---|---|
| all zero (popcount 0) | 140ms | 24ms | 29ms |
| one bit set (popcount 1) | 135ms | 28ms | 31ms |
| uniform random bits (popcount ≈16 avg) | 448ms | 115ms | 49ms |
| all ones (popcount 32, worst case) | 172ms | 111ms | 39ms |
Two things in that table don't follow from iteration counts alone. First, Kernighan's own worst case
(all ones, 32 iterations — identical to naive's fixed count) is still 35% faster than
naive's 172ms, because each Kernighan iteration is one subtract-and-AND while each naive iteration is a
shift, a mask, and a branch — the per-iteration cost differs even when the iteration count
doesn't. Second, naive's own time swings 2.6–3.3x between the three fixed-pattern rows
(135–172ms) and the random row (448ms) despite always running exactly 32 iterations regardless of
input — the difference is branch prediction, not iteration count: a monotonous all-true or all-false
if is cheap to predict, a 50/50 random one on every single bit isn't, and big-O counts
neither.
The byte lookup table wins everywhere, and it's the one production code actually reaches
for. Always exactly 4 lookups, 29–49ms across every pattern tried — faster than Kernighan even
in Kernighan's own best case. The one approach that gets close without any memory table is
SWAR Popcount's own shift-and-mask folding — measured on
that page within a few percent of the lookup table across the same four patterns, never quite
overtaking it. (A real hardware population-count instruction — x86's POPCNT, exposed in C
as __builtin_popcount — is faster still, but there's no portable way to reach it from
plain JavaScript; the lookup table is the ceiling available here.) Kernighan's algorithm is rarely the
fastest choice in practice — its real value is being branch-light and allocation-free, a clean two-line
loop worth reaching for whenever a lookup table isn't already lying around, and the classic teaching
example for "a loop that runs once per set bit" showing up elsewhere, like bitmask subset
enumeration.
Time: naive scan is O(w), always exactly w iterations for
a w-bit word (32 here), independent of the value. Kernighan's algorithm is
O(k), exactly k iterations where k is the number of set bits —
0 ≤ k ≤ w, so it's never asymptotically worse than naive and strictly better whenever any
bit is 0. The lookup table is O(w / b) for a b-bit table index — 4 lookups for
an 8-bit table over a 32-bit word — constant in both w and k once
b is fixed. Space: O(1) for naive and Kernighan; the lookup
table needs a fixed 2b-entry table built once, not per call — 256 bytes here,
independent of how many numbers get counted.