Synthesis — Bit Manipulation

The evolving thesis. Spun out of the hub _inbox on 2026-06-15 from a rapid Telegram burst of bit-trick sources (Bit Twiddling Hacks, the Stack Overflow popcount question, two Stephan Brumme bits pages) — the trigger cluster that crossed the ≥3 spin-out threshold.

Current thesis

Bit manipulation (bit-manipulation) is a body of techniques for computing common integer operations directly on bits — to be branchless and/or parallel-within-a-word (SWAR) rather than using conditionals, arithmetic, or table lookups. Two motivations organize the whole field:

1. Branchless computation (branchless-programming) — replace a data-dependent conditional with sign-bit arithmetic so there is no branch to mispredict: absolute value, sign, min/max, and the temp-free xor-swap.
2. Parallelism within a word (SWAR) — treat a machine word as a vector of small fields and act on all at once: the parallel popcount, byte-pattern detection.

The corpus has a clear shape: canonical reference → practical question → measured reality → a system that depends on it. bit-twiddling-hacks (Sean Anderson) is the field's primary catalog; count-set-bits-so is the genre's most-asked practical instance (popcount); stephan-brumme's benchmarked pages (xor-swap, branchless-abs) are the reality check; and from 2026-08-22 valyu-billion-scale-vector-index is the first operator — a search company (valyu) whose index-build rate is set by how fast popcount(a XOR b) runs (hamming-distance).

The central tension — elegant, but mostly superseded

The sources converge on one uncomfortable finding: most classic bit tricks are no longer performance wins. Three forces erased the advantage:

• Dedicated instructions — POPCNT/LZCNT/TZCNT replace whole hand-rolled hacks (population-count); std::popcount (C++20) is the modern answer. hamming-weight-wikipedia dates the takeover precisely: AMD POPCNT in 2007 (SSE4a), Intel in late 2008 (SSE4.2), with ARM VCNT and RISC-V CPOP alongside — every major ISA adopted it.
• Compilers emit branchless code for you — x<0 ? -x : x and a<b ? a : b already become conditional-move sequences, so the hand-written abs/min/max trick rarely beats -O2.
• The naive version is often faster now — Brumme benchmarks xor-swap as slower than a temp-variable swap on modern Intel CPUs (register renaming + store-to-load forwarding, and the XOR chain's serial dependency).

The counterweight, added 2026-08-22. valyu-billion-scale-vector-index does not overturn any of that, and it is worth being precise about why it doesn't. Nothing in it beats a compiler with a clever hack; the arithmetic was already VPOPCNTDQ. What it shows is the next layer down, which the spoke had no source for: once the instruction is the arithmetic, the remaining cost is everything that is not the instruction. Their first brute-force kernel spent about 80% of its 10 ns per operation on bookkeeping — per-call feature detection, reloading the compared value into the register, per-query setup. Removing that, not changing the maths, got them to 6.9 ns.

Three further readings this source adds, all of them dated and all of them the vendor's own numbers:

• A hardware instruction can be the ceiling. Their GPU kernel runs at 93% of throughput on the MIO unit because popcll shares that pipe with branches and shared-memory ops. "The hardware won" and "the hardware is now the limit" turn out to be the same sentence read at different scales.
• Wide popcount does not scale with threads. 0.32 GH/s on one core, 7.25 GH/s on 44 SMT threads — a 22× return on 44 threads, attributed to AVX-512's shared 512-bit execution units and turbo throttling. The spoke's ISA story ("every architecture adopted POPCNT") says nothing about how many of them can issue at once. Now it does (2026-08-22): uops-info measures VPOPCNTQ zmm at 1.00 per cycle on port 5 alone, on every Intel microarchitecture from Ice Lake to Emerald Rapids. One port per core, so an SMT sibling can fill idle cycles and cannot add throughput — 44 threads on 22 cores returning 22× is what that predicts. What Valyu inferred from a profile, an independent measurement confirms.

And the ISA story needs a vendor attached (added 2026-08-22, from the same source). This spine has said "every major ISA adopted POPCNT" and treated that as the end of it. Intel and AMD adopted the same instruction and built it differently: Zen 4 and Zen 5 issue VPOPCNTQ zmm on two FP pipes rather than one, and Zen 5 does it at latency 1 against Intel's 3. So a Hamming-distance kernel that is issue-bound runs at twice the rate on one vendor, and a dependency chain of popcounts runs at three times. "The hardware wins now" is true on both, and any number quoted without naming the microarchitecture is unfinished — the same lesson as the scale-conditional one below, one layer down. There is also a free win hiding in the table: VPOPCNTQ ymm costs the same port at the same rate as the 512-bit form, so on an AVX-512 machine the 256-bit version is strictly worse.

• The optimisation is scale-conditional, in both directions. Their query tiling is a 5% regression at 1M vectors (array fits in L1, setup is pure overhead) and a large win at 10M. That is the same finding as xor-swap losing on a modern CPU, generalized: the answer depends on where the working set sits, and any claim without a size attached is unfinished.

So the durable value of these tricks has shifted from raw speed to (a) correctness-critical bit work that is inherently bitwise — flags, masks, protocols, codecs, hashing, bitsets, bitboards — and (b) understanding how the machine and compiler actually behave. The modern rule the sources imply: measure, prefer the readable version, and reach for a branchless bit trick only when a profiler shows a misprediction-bound hot path the compiler didn't already fix.

The clearest case yet of hand-written low-level code winning (2026-09-10)

turbovec is a 16,771-star MIT vector index whose scoring path is hand-written SIMD — NEON SDOT/SMMLA on ARM, AVX-512 VNNI and vpermb on x86, AVX2 and scalar underneath — and it beats FAISS IndexPQFastScan in every measured configuration on both architectures: ~3.4–3.5× at 4-bit, 20–26% at 2-bit, 100K vectors, k=64, median of 5 runs, hardware named (Google Axion; Xeon Platinum 8481C).

It answers the spoke's oldest open question with a caveat attached. "When do hand tricks still win?" — here, and the shape of the answer is precise: the 4-bit path wins by 3.4× because dedicated dot-product instructions exist for it, and the 2-bit path wins by only 20–26% because it falls back to a LUT scan. The advantage tracks which instruction the data width can reach. That is the same finding as population-count's POPCNT story read forwards instead of backwards: the hardware wins, and the way to win is to arrange your data so the hardware's instruction applies. Nobody here is out-clevering a compiler with a mask sequence; they are choosing a memory layout the ISA has an instruction for.

It also settles the SWAR-versus-SIMD scope question in practice. swar's page has carried an open note about whether true SIMD is in scope or a sibling cluster. The corpus's two most substantial performance sources are now both real-SIMD (valyu-billion-scale-vector-index, this) and both reach the spoke through the same door — the arithmetic is bit-level, the win is in how it is fed. Keeping SIMD out would leave the spoke holding only the techniques it has already concluded are superseded.

And it is the counterweight to the trust problem. Valyu's numbers are a company measuring its own closed system with nothing published; this is an author measuring his own project with the harness, the raw JSONs and the hardware published, comparing against a deliberately stronger FAISS baseline than the paper he implements used, and flagging an artifact in his own measurement rather than banking it. Same conflict of interest, opposite disclosure — T2 against T3, and the difference is entirely what a reader can check.

One number is not about bits at all and is worth keeping anyway. Removal by id: 0.44–1.22 µs here against 0.19–1.02 seconds in FAISS, because FAISS repacks its codes on every call. Six orders of magnitude, from a data-structure choice. The spoke's thesis says the durable value of this material has moved from raw speed to correctness-critical bit work and to understanding the machine — here is a third: knowing which layer your cost actually sits in. A SIMD kernel that is 3.4× faster is the headline; the swap-and-pop is the bigger number.

Open questions

• The book-shaped gap. Hacker's Delight (Henry S. Warren Jr.) is the canonical textbook these sources cite but it isn't paged yet. Closed (2026-06-15): paged as hackers-delight (T1) — the field's foundational text (Warren/IBM, Addison-Wesley 2002/2013). It also sharpens the central thesis: its division-by-constants and bit-counting derivations are where many of the compiler optimizations that now beat hand-written tricks were first written down — so "the compiler wins now" reads as "the compiler absorbed Hacker's Delight."
• When do hand tricks still win? The "compiler/hardware wins" claim needs the boundary cases: bit-parallel algorithms with no instruction (Morton codes, specific SWAR), pre-POPCNT targets, embedded/MCU contexts. A controlled, dated benchmark would sharpen this.
• SWAR / SIMD depth. SWAR (parallelism-within-a-register) is now its own concept page — the data-parallel half of the spoke beside branchless-programming. Open: whether true SIMD (SSE/AVX/NEON) is in scope or a sibling cluster (see adjacency); SWAR's durable niche is precisely where SIMD isn't available (embedded, portable, wide-word inner loops).
• Portability/UB. Several tricks lean on arithmetic right shift of signed ints and two's-complement — portable in practice, not by the C standard's letter. Worth a dedicated note as the spoke grows. Answered in part 2026-09-28 by wg14-n2412 and p1236-signed-integers-twos-complement. C23 makes two's complement the only representation, but a negative left shift is still undefined and a negative right shift still implementation-defined. C++20 defines both shifts. Signed overflow stays undefined in both. So the caveat now holds for the shift in C and for nothing in C++.

Growth edges

Ranked; each names the kind of source that would close it (see ../QUALITY.md → Growth edges).

1. When hand tricks still win. "The compiler wins now" is the spoke's central claim and it needs its boundary cases: bit-parallel algorithms with no instruction, pre-POPCNT targets, MCU contexts. — needs: a dated, controlled benchmark with compiler version and target stated. Partly advanced 2026-08-22 by valyu-billion-scale-vector-index, which supplies a boundary case of a different kind: hand work still wins around the instruction (batching, register pinning, tiling) even where it cannot win at the instruction. Still open as stated, because the source names no compiler version and publishes no code — a T3 profile, not a controlled benchmark.
2. Portability and UB. Several catalogued tricks lean on signed-shift and two's-complement behaviour that is portable in practice and not by the standard's letter. — needs: a standards-level treatment (C standard text, or a compiler-writer's account). HALF CLOSED 2026-09-28 (research pass) by wg14-n2412 (C23 text) and p1236-signed-integers-twos-complement (C++20). The representation is settled in both languages; the right shift of a negative value is defined in C++20 and still implementation-defined in C23. Successor, edge 2a: what the major C compilers actually document for that implementation-defined case. — needs: GCC's, Clang's or MSVC's own implementation-defined-behaviour documentation for signed >>. Half closed the same day by gcc-integers-implementation: GCC documents sign extension for negative >> and treats signed << as defined, as a language extension. Clang and MSVC are still unread, so the edge stays open for them.
3. SWAR versus true SIMD. swar is paged; whether SSE/AVX/NEON is in scope or a sibling cluster is undecided. — needs: a source that treats the two together. Decided in practice 2026-08-22: valyu-billion-scale-vector-index is an AVX-512 source and it was routed here rather than parked, so true SIMD is in scope when the subject is a bitwise primitive (popcount, Hamming). The spoke's registry note already anticipated widening toward performance-engineering/SIMD; this is the first source exercising it. What is still missing is a source that treats SWAR and true SIMD comparatively.

Coverage edges (added 2026-08-08, at the curator's request for a wider backlog). These widen what the spoke covers instead of answering an open question above; one ordinary solid source closes any.

4. Morton codes and space-filling curves. The open questions name them as the case where hand tricks may still beat the compiler, and there is no page to argue against. — needs: a paper or a dated benchmark showing the interleave beating the generated code.
5. Where bit tricks are load-bearing. Closed 2026-08-22 by valyu-billion-scale-vector-index — an engine's own account, which is exactly what the edge asked for. Valyu's vector index is built on popcount(a XOR b) over 512-bit binary vectors, and the post traces the whole build architecture back to that operation costing 5 ns. The named alternatives (Roaring bitmaps, chess bitboards, Bloom filters) are still unpaged and still wanted; the category now has a member.
6. The instructions the compiler emits. POPCNT, LZCNT/TZCNT, BMI1/BMI2 and their ARM counterparts are what "the hardware wins now" actually means; no page names them. Closed for x86 popcount 2026-08-22 by uops-info (Abel & Reineke, T2 — a third party measuring somebody else's silicon, which is better than the vendor tables the edge settled for). It answers the concrete question the edge had acquired the day before: one port. VPOPCNTQ zmm is 1.00/cycle on p5 alone across Ice Lake, Tiger Lake, Rocket Lake, Alder Lake-P and Emerald Rapids, latency 3 — so two SMT siblings share one unit, which is the 22×-on-44-threads result exactly. — still needs: LZCNT/TZCNT, BMI1/BMI2, and ARM's CNT/ADDV, none of which is paged. Sharpened, not closed, 2026-08-22. valyu-billion-scale-vector-index names VPOPCNTDQ (AVX-512) and CUDA's popcll, and gives measured throughput for both — but as an application's profile, not as ISA documentation. The edge now has a concrete question attached: how many ports can issue a 512-bit popcount, and why do 44 threads return only 22×? Agner Fog's tables would answer it. ARM half closed 2026-08-30 by cortex-a76-optimization-guide (Arm's own tables, T3) — and it overturns the flat comparison this spoke had been implying. On AArch64 popcount is not one instruction: CNT counts per byte lane (latency 2, throughput 2) and the horizontal ADDV that turns sixteen lane counts into one number costs latency 6 at one every two cycles, so the reduction is three times the latency and a quarter the throughput of the counting. Trailing zeros go the other way: no TZCNT exists in these tables, and the RBIT+CLZ idiom costs only 2 cycles. — still needs: BMI1/BMI2 (PDEP/PEXT especially), unpaged. 6a. Nobody has measured ARM the way uops.info measures x86. New 2026-08-30. The spoke's x86 numbers are third-party measurements (uops-info, T2); its ARM numbers are the vendor's own (cortex-a76-optimization-guide, T3), for one core from 2019, and uops.info exists precisely because vendor tables and silicon sometimes disagree. — needs: an independent instruction-timing measurement for any AArch64 core, or a published methodology equivalent to uops.info's.
7. The classical constructions. de Bruijn sequences for bit-scan and Gray codes are standard material hackers-delight assumes, absent here. — needs: a textbook or paper treatment.

Contradictions / tensions

None internal yet — the sources agree. The live tension is trick vs. compiler/hardware (recorded above), which is a finding, not a conflict: every benchmarked source lands on "the naive/modern path usually wins."

Cross-spoke adjacency

• ../optimization-algorithms-wiki — a homonym, not a neighbour. That spoke owns metaheuristic global optimization of objective functions (PSO/GA/CMA-ES, No-Free-Lunch); this spoke owns instruction-level bit/micro-optimization. The shared word "optimization" is the only overlap; do not cross-file.
• ../webperf-wiki — shares a performance sensibility but at the web-delivery layer (page weight, bytes shipped), not CPU bit operations.
• ../llm-inference-wiki — low-level kernels (quantization packing, bitmask attention) touch bit work, but its subject is model serving, not bit tricks per se. Watch for a genuine bridge (e.g. bit-packed quantization).
• ../analytical-databases-wiki — the routing runner-up for valyu-billion-scale-vector-index. That spoke owns index construction and storage layout as data infrastructure (Druid segments, Pinot's inverted indexes); this spoke took the source because its load-bearing substance is the bit primitive underneath. A future source about vector-index storage with no bit-level content belongs there, not here.
• Vector search / information retrieval — owned by no spoke yet. The hub _inbox holds a parked information-retrieval cluster (Manning et al.), which named "embeddings and vector search" as its expected growth. valyu-billion-scale-vector-index's architecture half (centroid graphs, posting lists, recall) is recorded on the source page as cross-spoke context and should be re-read from that spoke if it is ever spun out.

Index — Bit Manipulation Wiki

Catalog of every page, grouped by schema.org @type. Spine: synthesis (thesis), log.md (history), this file (catalog). Spun out of the hub _inbox low-level-programming cluster on 2026-06-15. Scope: bitwise/low-level integer techniques. Not metaheuristic optimization (that's ../optimization-algorithms-wiki — a homonym), not web performance, not inference kernels.

DefinedTerm (concepts / techniques)

• bit-manipulation — the hub concept: operating on bits directly (branchless + SWAR) instead of arithmetic/branches/tables · domain
• population-count — popcount / Hamming weight: counting set bits; the method ladder (naive → Kernighan → SWAR → POPCNT) · mechanism
• branchless-programming — replacing data-dependent conditionals with sign-bit arithmetic; the "compiler/hardware usually wins now" caveat · practice
• hamming-distance — popcount(a XOR b): the cheapest interesting distance (~5 ns at 512 bits with AVX-512/VPOPCNTDQ), and what a cheap primitive lets the algorithm above it get away with · mechanism
• swar — SIMD Within A Register: a word as a vector of lanes, operated on in parallel with masked integer ops; the data-parallel half (basis of parallel popcount, byte-pattern search) · mechanism

SoftwareSourceCode (sources)

• turbovec — a Rust/Python vector index over Google Research's TurboQuant (arXiv:2504.19874), MIT, 16,771★ / 1,444 forks, created 2026-03-26, pushed 2026-08-21. 10M documents from 31 GB float32 to 4 GB, and faster than FAISS IndexPQFastScan in every measured cell — ~3.4–3.5× at 4-bit (NEON SDOT/SMMLA · AVX-512 VNNI), 20–26% at 2-bit (vpermb LUT scan), on named ARM and x86 hardware. Removal by id at 0.44–1.22 µs against FAISS's 0.19–1.02 s. Benchmark scripts, raw JSONs and a self-flagged harness artifact published — T2, not T3, and the disclosure is the reason · source · T2 · github.com

TechArticle (sources)

• bit-twiddling-hacks — Sean Anderson's canonical Stanford collection; the field's primary catalog (seed source) · source · T1 · graphics.stanford.edu

• xor-swap — Stephan Brumme: swap without a temp via 3 XORs; aliasing hazard + slower than temp on modern CPUs · source · T2 · bits.stephan-brumme.com

• branchless-abs — Stephan Brumme: (x ^ (x>>31)) - (x>>31); sign-bit mask abs; superseded by compiler conditional-move · source · T2 · bits.stephan-brumme.com

• valyu-billion-scale-vector-index — Valyu's engineering post (2026-05-22): a billion-scale vector index built on popcount(a XOR b) over 512-bit binary vectors. 5 ns per 512-bit Hamming with AVX-512/VPOPCNTDQ, tiling + register pinning 10 ns → 6.9 ns, 488 G popcounts/s on one L4 GPU at 93% of MIO throughput — the instruction as the bottleneck. Closes growth edge 5 (a system that depends on this) · source · T3 (vendor's own numbers, no code) · valyu.ai

• cortex-a76-optimization-guide — Arm's own instruction tables for the Cortex-A76 (v8.0, 2019), read for the ARM half of edge 6. CNT is per-byte-lane (lat 2, thr 2) and the ADDV reduction that finishes a popcount costs lat 6 at one per two cycles; CLZ and RBIT are 1/3 each, and no trailing-zero count is listed. T3 — vendor-stated timings for the vendor's own core, beside uops-info's T2 measurements of x86 · source · T3 · documentation-service.arm.com

Dataset (sources)

• uops-info — Abel & Reineke's measured instruction tables (Saarland; method in arXiv:1810.04610), read 2026-08-22 for the popcount family. Intel Ice Lake → Emerald Rapids: VPOPCNTQ zmm is latency 3, throughput 1.00/cycle, on port 5 alone — same rate as scalar POPCNT r64 on p1, so 512-bit width is free and the issue rate is the ceiling. VPOPCNTQ ymm sits on the same port at the same rate, so 256-bit buys nothing. AMD Zen 4/5 issue it on two FP pipes (0.50/cycle) and Zen 5 at latency 1. Confirms the SMT anomaly valyu-billion-scale-vector-index could only infer, and closes coverage edge 6 for x86 · source · T2 · uops.info

Standard (sources)

• wg14-n2412 — WG14 N2412 (Bastien & Gustedt, 2019): C23 makes two's complement the only signed representation, but keeps negative << undefined and negative >> implementation-defined (N3220 §6.5.8) · source · T1 · open-std.org

• p1236-signed-integers-twos-complement — WG21 P1236R1 (Maurer, 2018): C++20 defines both signed shifts (modulo left shift, arithmetic right shift); signed overflow stays UB · source · T1 · open-std.org

• gcc-integers-implementation — GCC manual: negative >> sign-extends; signed << treated as defined (a GCC extension); two's complement only · source · T1 · gcc.gnu.org

Book (sources)

• hackers-delight — Henry S. Warren Jr., Hacker's Delight (Addison-Wesley 2002/2013); the field's canonical/foundational text; where many compiler bit-optimizations were first written down · source · T1 · en.wikipedia.org
• hamming-weight-wikipedia — Wikipedia on Hamming weight; pins down the SWAR popcount constants (m1/m2/m4/h01), the ladder's exact op counts (17 / 24 / 3-per-bit), and the POPCNT hardware timeline · source · T1 · en.wikipedia.org

QAPage (sources)

• count-set-bits-so — Stack Overflow: count set bits in a 32-bit int; the popcount method ladder (honest note — SO unfetchable, from known content) · source · T3 · stackoverflow.com

Organization

• valyu — search/retrieval-API company behind valyu-billion-scale-vector-index; the spoke's first operator, as opposed to a catalogue or a benchmark

Person

• sean-anderson — author of bit-twiddling-hacks; the field's canonical reference
• stephan-brumme — author of bits.stephan-brumme.com; benchmarks the tricks (the empirical "naive often wins" backbone)

Synthesis

• synthesis — the thesis: bit manipulation as branchless/SWAR technique; canonical refs; the central "elegant-but-superseded" tension