Fast add/subtract two integers based on sign of third integer

Question

I am looking for a fast (branch-less) code to compute the following:

if ( k > 0 )
    x += i;
else if ( k < 0 )
    x -= i;
else if ( k == 0 ) 
    // do nothing.

where k, x, and i are of int type.

It is fine for the solution to use intrinsics.

Answer 1

This answer shows a fast, branchless way of computing the sign of a value. Assuming that's correct, you can write:

x += i * ((0 < k) - (k < 0))

Answer 2

Try this:

int sign = !!k - !!(k & INT_MIN) * 2;
x += i * sign;

This assumes two's complement representation of integers, resulting in INT_MIN having only the high-order bit set.

Answer 3

Just compile your code with good optimisation settings, get a disassembly of your code, and look at the result. Then change your code until the disassembly shows what you want. There's a chance that you already get branchless code. There's a better chance if you write

if ( k > 0 )
    x += i;
if ( k < 0 )
    x -= i;

because the else in between makes it harder for the compiler to avoid branches.

Answer 4

x = x + i*(k>0) - i*(k<0);

But, honestly, given the many optimization possibilities of modern compilers, I wouldn't trade clarity of code for aleggedly faster code. For the x86 platform, for example, MMX and SSE units can do this operation with no branches.

Answer 5

You seem to be expecting code that is "branchless" to be measurably and importantly "faster?" With maximum optimization settings turned on, exactly what instruction sequence does your compiler now produce? Have you then profiled that code to confirm that it is not fast enough?

Answer 6

Try looking at the assembly language for this:

if (k != 0)
{
    const int multiplier = (k > 0) ? 1 : -1;
    x += (multiplier) * i;
}

Some processors may have conditional instructions that are only executed depending on the condition code (like ARM).

Look at the assembly code printed by your compiler.

Edit 1: performance concerns
A lot of modern processors have enough space in their instruction cache to that they can handle the above code efficiently. The comparison should be quick for the processor's branch decision making circuitry.

Profile or Benchmark before making any judgements about code having to be one line.

Answer 7

Just for kicks, I present this:

using opType = void(*)(int&, int);
const opType ops[3] =
{
    [](int&  , int  ){ },
    [](int& x, int i){ x += i; },
    [](int& x, int i){ x -= i; }
};

auto f = ops[int(k > 0) + (2 * int(k < 0))];
f(x, i);

Live Demo

Obviously, the other solutions using solely mathematics are going to be more efficient :) But this give you some options if you want to do more complex operations based on what k is.

Answer 8

Except for INT_MIN the following should work in C++11

x += (std::signbit(-k)-std::signbit(k))*i;

And the following should work in all cases, including INT_MIN - if long is longer than int:

x += (std::signbit(-(long)k)-std::signbit(k))*i;

Added: Internally std::signbit is in many compilers converted to a simple shift-operation, which should be branch-less and fast.

Answer 9

This is a branchless solution, but the time will vary based on your environment. It shouldn't take too much more than 0.005 seconds, so I think that won't be a problem.

k>0?x+=i:k<0?x-=i:0