performancebit-manipulationbranch-predictionbranchless

# How can I make branchless code and how does it work?

In the above answer, it's mentioned how you can avoid branch prediction fails by avoiding branches.

The user demonstrates this by replacing:

``````if (data[c] >= 128)
{
sum += data[c];
}
``````

With:

``````int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
``````

How are these two equivalent (for the specific data set, not strictly equivalent)?

What are some general ways I can do similar things in similar situations? Would it always be by using `>>` and `~`?

Solution

• ``````int t = (data[c] - 128) >> 31;
``````

The trick here is that if `data[c] >= 128`, then `data[c] - 128` is nonnegative, otherwise it is negative. The highest bit in an `int`, the sign bit, is 1 if and only if that number is negative. `>>` is a shift that extends the sign bit, so shifting right by 31 makes the whole result 0 if it used to be nonnegative, and all 1 bits (which represents -1) if it used to be negative. So `t` is `0` if `data[c] >= 128`, and `-1` otherwise. `~t` switches these possibilities, so `~t` is `-1` if `data[c] >= 128`, and `0` otherwise.

`x & (-1)` is always equal to `x`, and `x & 0` is always equal to `0`. So `sum += ~t & data[c]` increases `sum` by `0` if `data[c] < 128`, and by `data[c]` otherwise.

Many of these tricks can be applied elsewhere. This trick can certainly be generally applied to have a number be `0` if and only if one value is greater than or equal to another value, and `-1` otherwise, and you can mess with it some more to get `<=`, `<`, and so on. Bit twiddling like this is a common approach to making mathematical operations branch-free, though it's certainly not always going to be built out of the same operations; `^` (xor) and `|` (or) also come into play sometimes.