Branchless Min and Max with Bitwise Operations

Branchless computation of the minimum or maximum of two integers is an optimization technique used in high-performance computing to avoid CPU branch mispredictions. By replacing conditional jump instructions with a fixed sequence of bitwise and arithmetic operations, the processor executes instructions in constant time across parallel execution units without disrupting the instruction pipeline.

The Sign Bit and Mask Generation

In binary representation using the two's complement system, the most significant bit (MSB) indicates the sign of an integer: 0 for non-negative numbers and 1 for negative numbers.

When subtracting integer \(y\) from integer \(x\) (\(x - y\)), the sign of the result indicates the relationship between the two values:

  • If \(x < y\), then \((x - y)\) is negative, and the sign bit is 1.
  • If \(x \ge y\), then \((x - y)\) is non-negative, and the sign bit is 0.

By performing an arithmetic right shift by \(N - 1\) bits (where \(N\) is the bit width of the integer, such as 32 or 64), the sign bit is replicated across all bit positions. This generates a bitmask:

  • If \(x < y\), the resulting mask is all ones (0xFFFFFFFF or -1 in decimal).
  • If \(x \ge y\), the resulting mask is all zeros (0x00000000 or 0 in decimal).

\[\text{mask} = (x - y) \gg (N - 1)\]

Calculating Minimum and Maximum via Masking

Once the bitmask is generated, it can be combined with bitwise AND (&) and addition or subtraction to select the target value deterministically:

Minimum: \[\min(x, y) = y + ((x - y) \ \& \ \text{mask})\]

  • When \(x < y\), \(\text{mask} = -1\), reducing the expression to \(y + (x - y) = x\).
  • When \(x \ge y\), \(\text{mask} = 0\), reducing the expression to \(y + 0 = y\).

Maximum: \[\max(x, y) = x - ((x - y) \ \& \ \text{mask})\]

  • When \(x < y\), \(\text{mask} = -1\), reducing the expression to \(x - (x - y) = y\).
  • When \(x \ge y\), \(\text{mask} = 0\), reducing the expression to \(x - 0 = x\).

The XOR-Based Method

An alternative approach avoids subtraction entirely to eliminate the risk of integer overflow. It relies on the XOR (^) operator:

\[\min(x, y) = y \oplus ((x \oplus y) \ \& \ -(x < y))\] \[\max(x, y) = x \oplus ((x \oplus y) \ \& \ -(x < y))\]

If \(x < y\) evaluates to 1, its negation -(1) produces a full bitmask of ones (~0). The expression evaluates to \(y \oplus (x \oplus y) = x\). If \(x \ge y\), the evaluation yields 0, leaving \(y \oplus 0 = y\).

Parallel and SIMD Execution

Bitwise branchless logic is foundational for Single Instruction, Multiple Data (SIMD) architectures such as AVX, SSE, and ARM NEON. Because SIMD registers operate on packed data vectors simultaneously, traditional control-flow branching cannot be executed on individual vector lanes. Bitwise masks allow SIMD units to evaluate minimums and maximums across dozens of parallel integers simultaneously within a single clock cycle.