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.
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.
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.
// 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;
}
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 pattern | naive scan | Kernighan | lookup table | SWAR |
|---|---|---|---|---|
| all zero (popcount 0) | 175.1ms | 24.5ms | 30.2ms | 30.2ms |
| one bit set (popcount 1) | 155.5ms | 35.0ms | 39.7ms | 42.1ms |
| uniform random bits (popcount ≈16 avg) | 442.0ms | 117.0ms | 49.7ms | 51.2ms |
| all ones (popcount 32, Kernighan's worst case) | 152.2ms | 111.3ms | 39.8ms | 42.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).
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.