Bit Hacking and Complexity Limits

6. Bit-Hacking, “Doom Hacks,” and the Provable Limit on How Far They Go

The core move

The fastest operator you can put in place of “actually computing” something is almost always: don’t compute it, look it up or exploit the representation.

Concrete techniques covered

Lookup tables — precompute a small truth table once, read a row via array index instead of recomputing a formula.

XOR swap — swap two variables with no temp variable, pure bit identity.

Popcount (Kernighan’s trick) — clear the lowest set bit each loop iteration instead of checking every bit: n &= (n-1).

Bitboards — pack an entire grid (e.g. a chess board) into one integer; AND/OR/XOR then act on every cell simultaneously in one instruction.

Fast inverse square root (0x5f3759df) — reinterprets a float’s bits as an integer, exploiting how IEEE-754 floating point encodes something log-like, to get a near-correct answer from one subtraction and one shift plus a Newton refinement. The purest version of the whole family: skip the arithmetic, manipulate the bit pattern that represents the answer.

CORDIC — computes rotations, sin/cos, and magnitude using only shifts, adds, and a small precomputed arctangent table — no multiply, no divide, no float unit. Used in real DSPs, graphing calculators, and early flight computers before floating-point hardware was affordable.

Integer angles (Doom’s actual technique, Binary Angle Measurement) — represent a full circle as an unsigned integer wraparound; adding a fixed integer wraps for free via overflow, and the top bits index straight into a precomputed sin/cos table.

Float-to-int via the “magic number” trick — adding 1.5 × 2^52 to a double forces the FPU to round the value into the mantissa’s low bits, which are then extracted by reinterpreting the bit pattern as an integer — no cast, no truncation instruction.

The provable ceiling: Shannon’s 1949 counting argument

All of the above work because the specific functions people actually want (AND, OR, XOR, parity, majority, sin/cos, sqrt) happen to have short, structured descriptions. Shannon proved (by simple counting, not by trying and failing) that almost every possible n-input boolean function has no compact formula at all: there are 2^(2^n) distinct functions, but only a limited number of distinct short circuits/formulas of any given length, so once n is even modestly large, the overwhelming majority of functions in that space require a circuit close to maximal size — no clever search will find a shortcut for them because none exists. The “hack-finding” strategy is sound specifically because real-world functions are drawn from the small, structured, non-random corner of a vastly larger space that is almost entirely incompressible junk.

The doubly-exponential wall for enumeration

Separately from the “does a shortcut exist” question: literally enumerating every possible n-input function hits a wall driven by the function count itself, not by any algorithm’s inefficiency: 2^(2^n) grows so fast that n=6 alone already produces more distinct functions (≈ 1.8×10^19) than there is storage capacity to hold, regardless of hardware generation — the ceiling is physical (more matter would be needed than exists in reach), not a matter of a smarter enumerator. The optimal generation algorithm (build level n from level n−1 by concatenating pairs, one shift-and-OR per new table) is genuinely optimal — the per-item cost is minimal — but the item count itself is the unmovable bottleneck.

Related Research: The complexity limits and Shannon’s counting argument explored here connect to When One Size Doesn’t Fit All: Scale-Dependent Cosmic Evolution and the Unity of Physics which examines scale-dependent behavior, and Understanding Our Universe Through Simple Scaling Laws which provides an intuitive scaling framework.