bit-manipulation-wiki

Branchless programming

Branchless programming computes a result without a data-dependent conditional, usually by turning a branch into arithmetic on bits — most often using the sign bit (an arithmetic right shift yields an all-1s or all-0s mask) to select between two values. The motivation is the CPU pipeline: a mispredicted branch costs many cycles, so on hot paths a slightly longer branch-free sequence can win.

Canonical instances (in this spoke)

• Absolute value — (x ^ (x>>31)) - (x>>31).
• Sign / min / max without branching — sign-bit mask to pick the result (bit-twiddling-hacks).
• XOR swap — branch-free and temp-free, though it’s a register trick rather than a branch-avoidance one.

The recurring caveat — the spoke’s central tension

Branchless tricks were clear wins on older CPUs, but three forces have eroded the advantage:

1. Compilers emit them for you — x < 0 ? -x : x and a < b ? a : b already compile to conditional-move or dedicated sequences, so the hand-written trick rarely beats -O2.
2. Dedicated instructions — POPCNT/LZCNT/TZCNT replace whole bit-counting hacks.
3. Readability + correctness cost — the tricks carry portability hazards (signed-shift/UB, two’s-complement assumptions, aliasing as in xor-swap) that a branch does not.

So the modern guidance the sources converge on: measure, prefer the clear version, and reach for a branchless bit trick only when a profiler shows a misprediction-bound hot path the compiler didn’t already fix. Understanding the tricks remains valuable; deploying them by default does not.

Related

bit-manipulation · branchless-abs · xor-swap · population-count · bit-twiddling-hacks