Cairn
algorithms · bit manipulation · O(1) time — 5 fixed steps for a 32-bit word, independent of input (contrast Brian Kernighan's O(k) and a byte lookup table's O(w/b)); O(1) space

↩ back to Bit Manipulation

SWAR Popcount

This is the second entry in Bit Manipulation, and it solves the exact same problem as the category's first: Brian Kernighan's Algorithm's population count, counting how many bits of a 32-bit integer are 1. The mechanism here is completely different, though. Kernighan's trick loops once per set bit; a byte lookup table (also built on that page) does four array reads. This page's trick — called SWAR, "SIMD Within A Register" — does neither. It runs a fixed five steps of plain integer add/shift/mask on the whole word at once, every time, regardless of how many bits are set and with no memory access beyond the input itself.

The idea: treat one 32-bit register as 32 independent 1-bit lanes, and fold adjacent lanes together in parallel the way a SIMD instruction would — except using ordinary scalar arithmetic instead of real vector hardware. Step 1 turns 32 one-bit lanes into 16 two-bit lanes, each holding the sum of its two source bits (0, 1, or 2). Step 2 folds those into 8 four-bit lanes (0–4). Step 3 into 4 eight-bit lanes (0–8). Step 4 into 2 sixteen-bit lanes (0–16). Step 5 folds the last two lanes into one 32-bit answer: the total population count. Five steps, because doubling the lane width five times turns 32 one-bit lanes into a single 32-bit lane — log₂32 = 5.

Try it

Pick a 32-bit number (or a preset), then step through the five folding stages one at a time. The top row is the register's actual bits at the current stage — still 32 bits, always — with a thick line marking where each lane starts. The bottom row decodes each lane as a plain number: that number is exactly how many of the original bits underneath that lane are 1, at every stage, which is the whole reason the trick works.

Stage 0 of 5 — group size 1 (32 lanes, one bit each)
Lane sums — each lane decoded as a number

Why it works

Each step adds two overlapping copies of the same register — one shifted right, one not — then masks the sum so each lane's result can't spill into its neighbor. Step 1:

x = (x & 0x55555555) + ((x >>> 1) & 0x55555555);

0x55555555 is the byte 0x55 (binary 01010101) repeated four times — a 1 in every even bit position, a 0 in every odd one. x & 0x55555555 keeps only the low bit of every pair; (x >>> 1) & 0x55555555 shifts the whole register right by one and keeps only what is now the low bit of every pair — which was the high bit of that same pair before the shift. Adding those two together puts each pair's sum (0, 1, or 2) into that pair's own two bits, and because every pair is handled identically and independently, this happens to all 16 pairs in the word simultaneously, in one add.

Worked example, one byte at a time (the same argument holds across all 32 bits at once, since the mask is just this pattern repeated): n = 0b10110110 has five 1s. Reading right to left in pairs — 10, 11, 01, 10 — step 1 sums each pair: 1, 2, 1, 1, written back as 2-bit numbers: 01 10 01 01, i.e. 0b01100101. Step 2 folds adjacent pairs of those 2-bit lanes into 4-bit lanes using the next mask, 0x33333333 (00110011 repeated): the left pair-of-pairs is 01 + 10 = 3, the right is 01 + 01 = 2, giving 0011 0010, i.e. 0b00110010. The lanes keep halving in count and doubling in width — 8-bit lanes via 0x0F0F0F0F, 16-bit lanes via 0x00FF00FF, and a final fold via 0x0000FFFF that leaves one 32-bit lane holding the answer, 5. At every single stage the lanes' values still sum to 5 — folding never loses or double-counts a bit, it just regroups the running totals into fewer, wider lanes.

Reference implementation

// SWAR popcount: exactly 5 steps, every input, 32-bit word.
function countBitsSWAR(n) {
  let x = n >>> 0;                                            // treat as unsigned
  x = (x & 0x55555555) + ((x >>> 1) & 0x55555555);   // 32×1-bit  -> 16×2-bit lanes
  x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);   // 16×2-bit  ->  8×4-bit lanes
  x = (x & 0x0F0F0F0F) + ((x >>> 4) & 0x0F0F0F0F);   //  8×4-bit  ->  4×8-bit lanes
  x = (x & 0x00FF00FF) + ((x >>> 8) & 0x00FF00FF);   //  4×8-bit  ->  2×16-bit lanes
  x = (x & 0x0000FFFF) + ((x >>> 16) & 0x0000FFFF);  //  2×16-bit ->  1×32-bit lane (answer)
  return x;
}

Pitfalls

Forgetting to mask the unshifted operand silently corrupts almost every input, not a rare edge case. It is tempting to write x = x + ((x >>> 1) & 0x55555555) for step 1 — masking only the shifted copy, on the theory that the original x is "already right" — but every lane's high bit is still sitting unmasked in x and leaks straight into the sum instead of being replaced by the lane's own 2-bit total. Checked directly: of 500,000 random 32-bit integers, this version disagrees with a correct bit-by-bit count on 92.5% of them. Both operands of every step's addition need their own mask — the shifted copy to isolate what used to be each lane's high half, and the unshifted copy to isolate what's already its low half.

The trick as written here is specific to a 32-bit word and to JavaScript's 32-bit bitwise operators. The same five-step shape generalizes to 64 bits (six steps, doubling lane widths up to 64), but it needs its own wider constants (0x5555555555555555n and so on) and BigInt arithmetic — plain JavaScript's &/>>> only ever operate on 32-bit integers, silently truncating anything wider.

"No memory access" doesn't mean "fastest" — measured here, the byte lookup table from Brian Kernighan's Algorithm's own page still wins, by a small but consistent margin. 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, averaged across 4 independent process runs for stability):

input patternnaive scanKernighanlookup tableSWAR
all zero (popcount 0)175.1ms24.5ms30.2ms30.2ms
one bit set (popcount 1)155.5ms35.0ms39.7ms42.1ms
uniform random bits (popcount ≈16 avg)442.0ms117.0ms49.7ms51.2ms
all ones (popcount 32, Kernighan's worst case)152.2ms111.3ms39.8ms42.0ms

Two things stand out. First, SWAR's own time is flat across every pattern tried — like the lookup table, and unlike Kernighan or the naive scan, it does the same fixed five steps no matter how many bits are set or where they sit, so there's no pattern that can make it faster or slower. Second, it never actually overtakes the lookup table in any of the four patterns: the two are statistically tied on all-zero input, and the table pulls 3–6% ahead everywhere else, across all four independent runs measured. SWAR is still the better deal than it looks on a bare instruction count — on uniform random bits it's 2.3x faster than Kernighan's algorithm and 8.6x faster than the naive scan, using nothing but arithmetic a compiler can inline anywhere, no 256-byte table to carry around. Real hardware settles this differently again: a dedicated POPCNT instruction beats both, for the same reason SWAR beats a per-bit loop — it's just built into the chip instead of synthesized from five instructions, a comparison this site still can't run from plain JavaScript (see Brian Kernighan's Algorithm's own note on that).

Complexity

Time: O(1) for a fixed word width — exactly 5 steps for 32 bits, independent of the input value, more generally O(log w) steps for a w-bit word since each step doubles the lane width. Contrast Brian Kernighan's Algorithm's O(k) (scales with the number of set bits) and the byte lookup table's O(w / b) for a b-bit table index (scales with word width divided by table granularity, constant once both are fixed). Space: O(1) — no precomputed table of any size, just five integer constants baked into the code.