Conditionally Set or Clear Bits Without Branching

This article explores techniques for modifying binary bits based on a condition without using standard conditional jump or branch instructions (if/else or ternary operators). In performance-critical software, avoiding branch mispredictions can significantly improve CPU pipeline efficiency. By leveraging binary arithmetic, bitwise operators, and two’s complement properties, you can set, clear, toggle, or assign bit states deterministically across various architectures.

The Fundamental Primitive: Mask Generation

The foundation of branchless bit manipulation relies on converting a boolean condition (\(0\) for false, \(1\) for true) into an all-ones (~0 or -1) or all-zeros (0) bitmask.

In two’s complement arithmetic, negating a boolean integer yields: - -0 results in 0x00000000 (all bits 0) - -1 results in 0xFFFFFFFF (all bits 1)

If your condition c is already normalized to 0 or 1, you can create a full-width mask using:

mask = -c;

1. Conditionally Setting a Specific Bit

To set the \(n\)-th bit of a variable x only if condition c (where c is 0 or 1) is true:

x |= (c << n);

How it works: - If c == 1, (1 << n) creates a mask with only the \(n\)-th bit set. Performing a bitwise OR sets the \(n\)-th bit in x. - If c == 0, (0 << n) equals 0. Bitwise OR with 0 leaves x unchanged.

2. Conditionally Clearing a Specific Bit

To clear the \(n\)-th bit of x only if condition c is true:

x &= ~(c << n);

How it works: - If c == 1, ~(1 << n) creates a mask with all bits set to 1 except the \(n\)-th bit, which is 0. Bitwise AND clears the \(n\)-th bit. - If c == 0, ~(0 << n) creates a mask of all 1s (~0). Bitwise AND with all 1s leaves x unchanged.

3. Setting a Bit to a Dynamic State (0 or 1)

To unconditionally update the \(n\)-th bit of x to match the value of v (where v is either 0 or 1), you can use the standard bit-twiddling approach:

x = (x & ~(1 << n)) | (v << n);

An alternative formulation using fewer operations uses the XOR trick:

x ^= (-v ^ x) & (1 << n);

How it works: - If v == 1, -v is all 1s. (-1 ^ x) is the bitwise NOT of x. Masking with (1 << n) extracts the inverted \(n\)-th bit. XORing x with this value forces the \(n\)-th bit to 1. - If v == 0, -v is all 0s. (0 ^ x) is x. Masking with (1 << n) extracts the current \(n\)-th bit. XORing x with its own bit clears it to 0.

4. Conditionally Setting or Clearing Arbitrary Bitmasks

When dealing with arbitrary bit patterns rather than single bits, full-width mask generation applies.

Conditionally Set Mask M If Condition c Is True:

x |= (M & -c);

• If c == 1, -c is ~0, so (M & ~0) evaluates to M. x |= M sets all bits in M.
• If c == 0, -c is 0, so (M & 0) evaluates to 0. x |= 0 leaves x unmodified.

Conditionally Clear Mask M If Condition c Is True:

x &= ~(M & -c);

• If c == 1, ~(M & ~0) evaluates to ~M. x &= ~M clears all bits specified by M.
• If c == 0, ~(M & 0) evaluates to ~0. x &= ~0 leaves x unmodified.

5. Conditionally Merging Bits from Two Sources

To select bits from source A when condition c == 1 and from source B when condition c == 0 for a specific mask M:

mask = -c;
x = B ^ ((A ^ B) & mask);

This branchless multiplexer (often called a bitwise select) replaces the target bits entirely without needing comparison jumps or branching logic.