Log — Bit Manipulation Wiki

Append-only history. Each entry starts with ## [YYYY-MM-DD] <op> | <title> where <op> is ingest, query, lint, or split, so grep "^## \[" log.md | tail -5 works.

[2026-06-15] split | spoke spun out of the hub _inbox (low-level-programming cluster)

Created from a rapid Telegram burst (msgs 428–433) of bit-trick sources that crossed the HUB.md ≥3 spin-out threshold. Trigger cluster (≥3 distinct sources): bit-twiddling-hacks (Sean Anderson, Stanford — first parked in _inbox 2026-06-15, migrated here), count-set-bits-so (the canonical Stack Overflow popcount question), and two Stephan Brumme bits pages — xor-swap and branchless-abs. Scaffolded CLAUDE.md (domain header), spine files, and 9 wiki pages: 4 source summaries + 3 concepts (bit-manipulation, population-count, branchless-programming) + 2 author entities (sean-anderson, stephan-brumme). Registered in ../wikis.md; hub log split entry added; the _inbox/bithacks.md park record (and its low-level-programming cluster tag) is superseded by this spin-out and removed.

Notes: SO blocked automated fetch — count-set-bits-so written from established knowledge, flagged T3 + unfetched. The two bithacks Telegram sends (whole page + #CountBitsSetKernighan anchor) are one source, counted once; SO + the two Brumme pages are the other distinct sources. Thesis: bit tricks are branchless/SWAR technique whose performance edge is now mostly superseded by hardware instructions + compilers (the "elegant but obsolete" tension); durable value is correctness-critical bit work + understanding. Hacker's Delight flagged as the top open T1/T2 gap.

[2026-06-15] ingest | Hacker's Delight — closing the named book-gap (Ralph loop, ontology-guided)

Created hackers-delight (Book, T1) — Henry S. Warren Jr., Hacker's Delight (Addison-Wesley 2002/2013), the field's canonical/foundational text, cited by all the spoke's other sources. Closes the synthesis "book-shaped gap" open question (flagged at spin-out as the top T1/T2 gap). Covers overflow, bit counting/rearranging, mask extraction, bit-matrix multiply, multiword arithmetic, and division-by-constants-via-multiply — the last sharpening the central thesis: it's where many compiler bit-optimizations were first written down, so "the compiler wins now" = "the compiler absorbed Hacker's Delight." Linked from synthesis (open-q resolved), bit-manipulation concept, index (new Book section). Provenance: scope summarized from secondary sources (Wikipedia/foreword), not a full read — noted on page. +1 page (→10).

[2026-06-15] ingest | SWAR — concept page (Ralph loop, ontology-guided, synthesis-from-corpus)

Created swar (DefinedTerm) — SIMD Within A Register, referenced by bit-manipulation + population-count as a core technique but unpaged. The data-parallel half of the spoke (complement to branchless-programming's control-flow trick): a word as a vector of masked lanes; the parallel popcount mask-cascade IS SWAR. Synthesized from already-ingested sources (bit-twiddling-hacks, hackers-delight) — a concept page, no new external source (like branchless-programming). Linked from both referencing pages + index; partly resolves the synthesis "SWAR/SIMD depth" open question (SWAR's niche = where true SIMD isn't available). +1 page (→11).

[2026-06-18] ingest | DefinedTerm enrichment pass (subagent)

Deepened the two thinnest DefinedTerm pages with sourced facts. New source: hamming-weight-wikipedia (TechArticle, T1) — pinned the SWAR popcount named constants (m1/m2/m4/h01), the method ladder's exact op counts (17 parallel / 24 naive / 3-per-set-bit sparse), the POPCNT hardware timeline (AMD SSE4a 2007, Intel SSE4.2 2008, ARM VCNT, RISC-V CPOP), and the RSA / __builtin_popcount / std::popcount notes — folded into population-count. Enriched branchless-programming with the specific mask-select formulas from the already-paged bit-twiddling-hacks (min/max, sign, opposite-signs (Weis), set/clear bits (Slayden/Yu, with the dated 5-16% AMD/Intel numbers), conditional-negate (Anderson), and the patented abs variant (Volkonsky/Sun)). Synthesis + index updated. +1 page (→12). All four DefinedTerm pages already carried ## Related. No build, no commit.

[2026-08-22] ingest | Building Vector Indices at Billion Scale (Valyu)

Routed from the hub (Telegram). Runner-up spoke: ../analytical-databases-wiki. The post is mostly a vector-search systems piece, and no spoke in the hub owns vector indices — but its load-bearing primitive is popcount(a XOR b) over 512-bit binary vectors, and the source says so itself: "the 5 ns Hamming primitive that drives every decision in this post."

New pages: valyu-billion-scale-vector-index (T3 — the company measuring its own closed system, no code, no replication), hamming-distance (the mechanism page the spoke was missing between population-count and any application), valyu (Organization).

Growth edge 5 closed. "Where bit tricks are load-bearing… the spoke is currently all technique and no user — needs the Roaring paper or an engine's own account." This is an engine's own account.

What it adds that the existing sources could not. Every benchmark here so far measures a trick against its naive alternative on a desk. This one measures the instruction under a production load and finds the layer below: their first brute-force kernel spent ~80% of 10 ns per operation on bookkeeping rather than arithmetic, and the fix was batching, register pinning and tiling — not better maths. 10 ns → 6.9 ns.

Three findings folded into synthesis:

• A hardware instruction can be the ceiling. Their CUDA kernel sits at 93% of throughput on the GPU MIO unit, where popcll shares issue cycles with branches and shared-memory ops. Not memory-bound; bound on the only pipe that issues its hot instruction.
• Wide popcount does not scale with threads — 0.32 GH/s per core, 7.25 GH/s on 44 SMT threads (22×, not 44×), attributed to AVX-512's shared 512-bit execution units and turbo throttling.
• Optimisations are scale-conditional in both directions — query tiling is a 5% regression at 1M vectors (L1-resident) and a large win at 10M (L2-resident).

Also: growth edge 3 (SWAR vs true SIMD) decided in practice — an AVX-512 source was routed here, so true SIMD is in scope when the subject is a bitwise primitive. Edge 6 sharpened with a concrete question (why 22× on 44 threads) that Agner Fog's tables would answer. Edge 1 partly advanced: hand work still wins around the instruction, though this source names no compiler version and ships no code, so it is a profile rather than a controlled benchmark.

[2026-08-22] ingest | uops.info — the popcount instructions, measured (via quality cycle)

uops-info — Abel & Reineke's measured x86 instruction tables (Saarland University; method published as arXiv:1810.04610), read for POPCNT r64, VPOPCNTQ ymm and VPOPCNTQ zmm. T2: a third party measuring hardware it does not make, which is better than the vendor ISA documentation coverage edge 6 was willing to settle for. Where Intel's or AMD's own documented figure differs from the measurement, the source prints both.

Closes coverage edge 6 for x86 popcount and answers the concrete question the edge picked up the day before, from valyu-billion-scale-vector-index: how many ports can issue a 512-bit popcount. One. VPOPCNTQ zmm is latency 3, throughput 1.00 per cycle, port p5 alone, identically on Ice Lake, Tiger Lake, Rocket Lake, Alder Lake-P and Emerald Rapids. One µop, one retire slot, no microcode.

Three readings folded into synthesis.md:

• The SMT anomaly is confirmed, not merely plausible. Valyu measured 0.32 GH/s on one core and 7.25 GH/s across 44 SMT threads and attributed the 22× to threads sharing execution units. One issue port per core predicts exactly that, so their inference now has a measurement under it. That note has been added to the Valyu page too, with the turbo-throttling half marked untested.
• Width is free; issue rate is the ceiling. Scalar POPCNT r64 is also 1.00/cycle (on p1), so moving to a ZMM register multiplies throughput eightfold at no extra issue cost. And VPOPCNTQ ymm sits on the same port at the same rate as the 512-bit form — on an AVX-512 machine the 256-bit version is strictly worse, which is a free correction rather than an optimisation.
• "Every ISA adopted POPCNT" needed a vendor attached. AMD Zen 4 and Zen 5 issue the same instruction on two FP pipes (0.50/cycle), and Zen 5 at latency 1 against Intel's 3. An issue-bound Hamming kernel runs at twice the rate on one vendor; a dependency chain at three times. The spine had treated the ISA adoption story as finished.

Edge 6 stays open in narrowed form — LZCNT/TZCNT, BMI1/BMI2 and ARM's CNT/ADDV are still unpaged. The source is also per-instruction only: the loads, the XOR and the horizontal reduction around the popcount are exactly where Valyu found its remaining wins, and none of them is in this table.

[2026-08-30] ingest | Arm's own tables — and popcount is not one instruction on AArch64

Via the hub research pass, taking hub quick win 19 / edge 6's ARM half. uops-info had ended by naming exactly this gap.

cortex-a76-optimization-guide (Arm, v8.0, 2019) supplies it, and the result is more interesting than a second column of numbers. On x86 a popcount is one instruction that returns one number. On AArch64 CNT counts set bits per byte lane and leaves sixteen of them in the register; getting the single number takes ADDV, and ADDV over 16 byte lanes costs latency 6 at one instruction every two cycles against CNT's 2 and 2. The reduction is the expensive half. Set beside uops.info's VPOPCNTQ zmm at 3 cycles, one per cycle, for 512 bits, the per-cycle bit rate is not close.

Trailing zeros run the other way and it is worth not over-generalising from the popcount result: these tables list CLZ and RBIT at 1 cycle / 3 per cycle each and no trailing-zero count at all, so the RBIT+CLZ idiom costs 2 cycles of latency — two instructions where x86 spends one, at a difference small enough to ignore.

Graded T3, deliberately. These are Arm's timings for Arm's core, and nobody independent has checked them. uops-info is T2 because Abel and Reineke measure somebody else's silicon, and it opens by noting that vendor documentation and measurement sometimes disagree. The spoke now knows x86 from a measurement and ARM from the maker, which is written up as new edge 6a rather than left as an accident of what was reachable.

Also fixed the stale sentence on uops-info — struck in place with the date, per QUALITY.md dimension 5.

[2026-09-10] ingest | turbovec — TurboQuant vector index in Rust

Routed in from the hub (Telegram). Read the GitHub API for the figures and the full README.md, including the recall, speed, mutation and persistence sections.

Source: turbovec, T2. 16,771★ / 1,444 forks / 16 open issues, created 2026-03-26, pushed 2026-08-21, Rust with Python bindings, MIT, on PyPI and crates.io. published: 2026-03-26 (repository creation). Easily the largest project in this spoke.

The tier decision is the part worth recording. This is an author benchmarking his own project against the incumbent — the exact shape that put valyu-billion-scale-vector-index at T3. It sits a rung higher because the benchmark scripts and raw result JSONs are published, every number names its hardware (GCP c4a-standard-8 Google Axion; Xeon Platinum 8481C Sapphire Rapids), the baseline chosen is deliberately stronger than the one in the TurboQuant paper it implements, and the README flags an artifact in its own harness instead of banking it. Same conflict of interest, opposite disclosure. Unreplicated, so not T1.

Recorded: beats FAISS IndexPQFastScan in every measured cell — ~3.5× at 4-bit / +26% at 2-bit on ARM, ~3.4× / +20% on x86 (100K vectors, 1K queries, k=64, median of 5); insert 6.3–19.7 µs; remove by id 0.44–1.22 µs against FAISS's 0.19–1.02 s; recall roughly a wash with FAISS IndexPQ, and behind it at deeper k on GloVe d=200. Method summarized: normalize → one shared random rotation making every coordinate Beta/Gaussian regardless of input → Lloyd-Max codebook from that known distribution → optional TQ+ per-coordinate calibration. No training phase, which is what the online-ingest claim rests on.

Synthesis: new section. It answers the spoke's oldest open question — when hand-written low-level code still wins — with a sharp shape: the 4-bit path wins 3.4× because dot-product instructions exist for it, the 2-bit path wins 20–26% because it falls back to a LUT scan. The advantage tracks which instruction the width can reach, which is the POPCNT lesson read forwards. Also updated swar: the SWAR-vs-real-SIMD scope question now has a practical answer, since the spoke's two largest performance sources are both true SIMD.

Kept out of the claim: the memory headline (10M docs, 31 GB → 4 GB) is stated by the README with no cell behind it in the benchmark JSONs read here, so it is recorded as the project's framing rather than as a measurement.

[2026-09-28] research | portability and UB (edge 2) — half closed, via research pass

Added wg14-n2412 and p1236-signed-integers-twos-complement, both T1. C23 makes two's complement the only signed representation, but a negative left shift is still undefined and a negative right shift is still implementation-defined (N3220 §6.5.8). C++20 defines both shifts. Signed overflow stays undefined in both. Updated branchless-abs with a dated note and the synthesis open question. New successor edge 2a: what GCC, Clang and MSVC document for the implementation-defined right shift. Also added gcc-integers-implementation (T1): GCC documents sign extension for negative >> and treats signed << as defined, as an extension. Edge 2a is half closed; Clang and MSVC remain.