Bit Twiddling Hacks (Sean Anderson)
The canonical reference for bit manipulation — sean-anderson‘s collection (Stanford, compiled ~1997–2005 with contributions from many named developers). The page nearly every other bit-trick source points back to; the founding/seed source of this spoke. Catalogs branchless and parallel bitwise techniques as drop-in C snippets, each with the trick, its derivation, and often the contributor and caveats.
What it collects
A few of the recurring families (each its own concept here over time):
- Counting bits set — naive loop, Brian Kernighan’s
v &= v - 1(iterates once per set bit), parallel/SWAR (“bit-counting in 12 ops”), and lookup-table variants. - Sign, absolute value, min/max without branching — using arithmetic shift of the sign bit instead of a conditional (branchless-programming).
- Bit reversal, integer log base 2, parity, trailing-zero count, modulus without division, Morton-number interleaving, byte-within-word pattern detection.
The recurring lesson
These are engineering tricks, not algorithmic innovations: ways to do common integer operations with bitwise ops to dodge branches and table lookups where “branching is expensive.” The page itself notes the tricks’ value depends on the machine — as CPUs converged on uniform per-op cost (and gained dedicated instructions), several of these are now matched or beaten by a single hardware instruction or compiler intrinsic. So the collection is best read as a catalog of techniques and their derivations, with real-world choice deferred to measurement on the target (branchless-programming).
Tier
T1 — the authoritative, widely-cited primary reference these techniques are canonicalized in; neutral (academic/personal, no vendor interest), with named provenance for most tricks. Routed here on a hub re-classification: it does not belong in optimization-algorithms-wiki (that owns metaheuristic global optimization, a different sense of the word).
Related
bit-manipulation · population-count · branchless-programming · branchless-abs · xor-swap · sean-anderson · count-set-bits-so