Related to this answer.
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 ~?
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.