How can I perform a branchless conditional arithmetic operation in C?

Question

I have a value int x where I want to conditionally add (for example) a value int y to, contingent on bool c. I could write code like this:

bool c;    // C23, or stdbool.h macro for _Bool.  Converts to integer 0 or 1
int x, y;  // x could be a global or something

...

if (c)
    x += y;

How could I write this without a branch?

If x is a local variable that no other thread could have a reference to, compilers may do if-conversion to branchless if they think that's more efficient. (Especially if auto-vectorizing, but also for scalar.) But that wouldn't be thread-safe for global variables, or if x is actually *x with an int *. Compilers can't invent writes like *x += 0 to possibly-shared objects that the abstract machine doesn't read or write, that could introduce a data race and step on values stored by other threads.

Answer 1

A basic answer would be to produce a branchless expression that evaluates to y if c is true or to the identity of the operation (0 for addition/subtraction and 1 for multiplication/division) otherwise and then use that expression.

Option 1: Multiplication by the boolean

A very simple solution is simply multiply the boolean with y then add:

x += c*y;

Option 2: Bitwise logic

Create a mask from the boolean, bitwise and, then add:

x += -c&y;

This way, if the boolean is false, negating the value will still be 0, and bitwise and 0 with any number gives zero, so this will result in adding 0 to the value. Otherwise, negating true would give -1 which is all 1s in 2's complement, which would give the y back from the bitwise and, adding y to x.

Note: The question uses addition as an example, but if the operation in question is division or multiplication, the value !c must be added to the right-hand operand of the augmented assignment. This is because the multiplicative identity is 1 and not 0.

E.g.

x *= -c&y+!c;

Answer 2

c can have any value in C language (unless it has the type bool) and you need to normalize it to 0 or 1

x += (!!c) * y;

Answer 3

Compilers can do this for you without you changing the source code, on some architectures.

A short (and concise) example (for ARM):

#include <stdbool.h>

int foo(bool c, int x, int y)
{
    if (c)
        x += y;
    return x;
}

foo:
        mla     r0, r2, r0, r1
        bx      lr

https://godbolt.org/z/PzEedYc8P