Branchless way to set all bits if no bits are set?

Question

I'm looking for a branchless implementation of the following:

int f(int c) {
  if (c == 0) {
    return 0xffffffff; // all bits set
  } else {
    return c;
  }
}

I haven't come across any clever ways to do this. Any tricks?

Answer 1

As mentioned by Nick ODell, there is a good chance that a compiler will already compile this code to instructions without a branch. A formulation making this even more likely is x - (x == 0) or x - !!x, which a compiler would typically be able to implement without branches by using CPU specific features. You can even try to replace this by a formulation purely based on bit manipulation. E.g. ((x - 1) & ~x) >> 31 (x unsigned) is 1 only if x == 0, and 0 otherwise. So

x - (((x - 1) & ~x) >> 31)

would be a completely branchless implementation of f. In practice I would expect it to be slower though than whatever the compiler generates for the other formulations.

Answer 2

You could cast c to the bool type to get 1 if any of the bits are set and 0 otherwise. Use _Bool or #include <stdbool.h> unless you are using C23.

Then subtract 1. If the result of the previous step was one, this will result in -1 which is all 1 bits on a two's complement system. To make this even more portable you could cast them to unsigned types first. Otherwise the result will be 0.

The previous step will result in a number that is -1 if c is 0 and otherwise 0. Bitwise OR the number with c will simply result in -1 if the number is -1 or leave c unchanged otherwise.

c | ((bool)c - 1)