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 repertoire, with provenance

The trick in every case is the same: produce an all-1s or all-0s mask from a boolean or a sign bit, then use it to select. From bit-twiddling-hacks:

• Min / max: r = y ^ ((x ^ y) & -(x < y)); — -(x < y) is 0 or 0xFFFF…, so the & picks one operand or the other. Anderson’s own caveat: it costs two extra instructions and typically the obvious x < y ? x : y is best; the mask form only wins where branching is genuinely expensive.
• Sign of an integer: sign = -(v < 0);, or the shift form -(int)((unsigned)v >> (WIDTH-1)). Anderson flags the shift version as not portable — signed right-shift is implementation-defined under 1989 ANSI C — and recommends the cast.
• Opposite signs: bool f = ((x ^ y) < 0); (Manfred Weis, 2009) — the high bit of x ^ y is set exactly when the signs differ.
• Conditionally set/clear bits: w ^= (-f ^ w) & m; (Glenn Slayden, 2003; superscalar variant by Marco Yu, 2007). Anderson reports the measured win as architecture-dependent: ~5–10% on an AMD Athlon, ~16% on a Core 2 Duo — a reminder that these are dated, machine-specific numbers.
• Conditionally negate: r = (v ^ -fNegate) + fNegate; (Anderson, 2009) — an XOR-add form devised to avoid a multiply.
• Absolute value: r = (v + mask) ^ mask; with mask = v >> (WIDTH-1). The shorter (v ^ mask) - mask variant (branchless-abs) is patented (Volkonsky / Sun Microsystems, US, 2000) — a rare case where the canonical trick carries a legal caveat, not just a portability 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