THE FOLD / CHEAT / THE-SHORTCUT / THE POPCOUNT
THE POPCOUNT
bits counted by folding
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The SWAR population count counts the set bits in a word without a single branch or loop — using a cascade of masked adds that fold the count in parallel. First it adds bits in pairs (mask 0x5555…), then nibbles (0x3333…), then bytes (0x0f0f…), and finally a single multiply-and-shift sums the byte-counts into place. It’s the archetypal SWAR (SIMD-Within-A-Register) trick: treat one machine word as a vector of small counters and operate on them all at once, in a handful of instructions independent of how many bits are set.
LIT verified live: over 200,000 random 32-bit values plus edge cases, the SWAR popcount equals a naive bit-by-bit count exactly — popcount(0xFFFFFFFF)=32 (window.__popcount). FIG no framing; the masked-fold popcount and a reference counter run in-browser.
LIT verified live: over 200,000 random 32-bit values plus edge cases, the SWAR popcount equals a naive bit-by-bit count exactly — popcount(0xFFFFFFFF)=32 (window.__popcount). FIG no framing; the masked-fold popcount and a reference counter run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-shortcut — count all the bits of a word in five instructions, no loop, no branch, by folding pairs into nibbles into bytes. AVAN (AI) built the instrument: the masked-fold SWAR popcount and the naive cross-check.
Credit as content: the SWAR/HAKMEM-lineage bit-count, canonized in Warren’s Hacker’s Delight. The weave: David names the shortcut; I confirm the parallel masked folding counts exactly the set bits.
Credit as content: the SWAR/HAKMEM-lineage bit-count, canonized in Warren’s Hacker’s Delight. The weave: David names the shortcut; I confirm the parallel masked folding counts exactly the set bits.
3 ONE DIMENSION
The fold: pairs → nibbles → bytes → total, each stage summing partial counts in parallel across the word.
4 TWO DIMENSIONS · INTERACTIVE
Pick a 32-bit value; watch the masked stages fold the count, ending equal to the naive bit count.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the population count, folded in parallel.
AVAN’s addition (the inverse-companion): don’t walk the bits — fold them. The inverse of ‘count set bits one at a time’ is ‘treat the word as packed counters and sum them with masked adds in log stages.’ Magenta are the individual set bits; green is the total the fold yields. A word as a vector of counters.
LIT Genuine SWAR/HAKMEM-lineage population count (canonized in Henry Warren's Hacker's Delight). Verified live: the masked-fold popcount (x−((x>>1)&0x55555555); (x&0x33333333)+((x>>2)&0x33333333); (x+(x>>4))&0x0f0f0f0f; (x*0x01010101)>>24) equals a naive bit-by-bit count over 200000 random 32-bit values plus edge cases (window.__popcount.matchesNaive).
FIG No framing: the masked-fold popcount and a reference counter run in-browser. The AVAN inverse is honest — instead of walking the bits one at a time, one treats the word as packed counters and sums them with masked adds in log stages. Magenta are the individual set bits; green is the total the fold yields. A word as a vector of counters.
FIG No framing: the masked-fold popcount and a reference counter run in-browser. The AVAN inverse is honest — instead of walking the bits one at a time, one treats the word as packed counters and sums them with masked adds in log stages. Magenta are the individual set bits; green is the total the fold yields. A word as a vector of counters.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-SHORTCUT · David Lee Wise (ROOT0), with AVAN