Cairn
algorithms · bit manipulation · O(k) time, k = number of set bits (naive scan is always O(w), w = word width); O(1) space

↩ back to Bit Manipulation

Brian Kernighan's Algorithm

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.

Try it

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.

Naive scan — checks all 32 positions, left (bit 31) to right (bit 0)
Kernighan — clears the lowest set bit each step

Why it works

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.

Reference implementation

// 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];
}

Pitfalls

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 patternnaive scanKernighanlookup table
all zero (popcount 0)140ms24ms29ms
one bit set (popcount 1)135ms28ms31ms
uniform random bits (popcount ≈16 avg)448ms115ms49ms
all ones (popcount 32, worst case)172ms111ms39ms

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.

Complexity

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.