Bit manipulation
Bit manipulation (bit twiddling) is the practice of operating directly on the individual bits of an integer — with AND/OR/XOR/NOT, shifts, and masks — to compute results that would otherwise use arithmetic, branches, or table lookups. It is the hub concept of this spoke.
Why it exists
Two motivations recur across the sources:
- Branchless / data-independent computation — replace a conditional with arithmetic on bits so there is no branch to mispredict (branchless-programming: branchless-abs, sign, min/max).
- Parallelism within a word (SWAR) — treat a machine word as a vector of small fields and operate on all of them at once (the parallel popcount, byte-pattern detection).
The canonical references
- bit-twiddling-hacks — Sean Anderson's Stanford collection, the field's primary catalog.
- stephan-brumme's bits — per-trick pages with disassembly + benchmarks (xor-swap, branchless-abs).
- hackers-delight — Hacker's Delight (Henry Warren) — the canonical book the above cite; the field's foundational text.
- count-set-bits-so — the popcount question, the genre's most-asked practical instance.
Who it is load-bearing for
Technique pages are easy to fill and easy to leave abstract. The spoke's first working system is
valyu-billion-scale-vector-index: a search company whose index stores 512-bit binary vectors, so
every comparison it makes is popcount(a XOR b) (hamming-distance) and its whole build pipeline
is shaped around that operation costing about 5 ns. Their own line is that the cheap primitive
"drives every decision in this post."
What it argues, at a scale where the answer is measurable rather than debatable: the cheapness of a bit operation is not a micro-optimisation, it is an architectural input. It decided that an exact brute-force sweep beats a clever graph search, which decided that the work belongs on a GPU, which ended with the popcount instruction itself as the bottleneck.
The standing tension
Most classic bit tricks were performance optimizations for older CPUs. On modern hardware many are matched or beaten by a dedicated instruction (POPCNT, LZCNT/TZCNT) or by what the compiler already emits (conditional-move for abs/min/max). So the durable value of bit manipulation today is more about correctness-critical bit work (flags, masks, protocols, codecs, hashing) and understanding than about hand-beating the compiler — see branchless-programming for the recurring caveat.
Related
population-count · hamming-distance · swar · branchless-programming · bit-twiddling-hacks · xor-swap · branchless-abs · count-set-bits-so · valyu-billion-scale-vector-index