CODEWITHSUNDEEP
c++calgorithm
user2052436
user2052436

Reputation: 4765

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

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.

Upvotes: 2

Views: 245

Answers (9)

Hans Olsson
Hans Olsson

Reputation: 12507

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.

Upvotes: 0

mcleod_ideafix
mcleod_ideafix

Reputation: 11428

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.

Upvotes: 1

Remy Lebeau
Remy Lebeau

Reputation: 595827

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.

Upvotes: 0

Thomas Matthews
Thomas Matthews

Reputation: 57678

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.

Upvotes: 0

cigien
cigien

Reputation: 60218

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))

Upvotes: 4

dbush
dbush

Reputation: 223739

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.

Upvotes: 2

Lakshya Raj
Lakshya Raj

Reputation: 1775

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

Upvotes: -2

Mike Robinson
Mike Robinson

Reputation: 8945

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?

Upvotes: 0

gnasher729
gnasher729

Reputation: 52538

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.

Upvotes: 1

Related Questions