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.
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 · branchless-programming · bit-twiddling-hacks · xor-swap · branchless-abs · count-set-bits-so