CODEWITHSUNDEEP
cmicro-optimizationsigned-integer
Alex
Alex

Reputation: 10126

Fast sign of integer in C

There is a sign function in C:

int sign(int x)
{
    if(x > 0) return 1;
    if(x < 0) return -1;
    return 0;
}

Unfortunately, comparison cost is very high, so I need to modify function in order reduce the number of comparisons.

I tried the following:

int sign(int x)
{
    int result;
    result = (-1)*(((unsigned int)x)>>31);

    if (x > 0) return 1;

    return result;
}

In this case I get only one comparison.

Is there any way to avoid comparisons at all?

EDIT possible duplicate does not give an answer for a question as all answers are C++, uses comparison (that I supposed to avoid) or does not return -1, +1, 0.

Upvotes: 18

Views: 34430

Answers (5)

Bruce
Bruce

Reputation: 35

int sign(int x) {    
    return (x>>31)|(!!x);
}

Upvotes: 1

Chris Dodd
Chris Dodd

Reputation: 126203

int sign(int x)
{
    // assumes 32-bit int and 2s complement signed shifts work (implementation defined by C spec)
    return (x>>31) | ((unsigned)-x >> 31);
}

The first part (x>>32) gives you -1 for negative numbers and 0 for 0 or positive numbers. The second part gives you 1 if x > 0 or equal to INT_MIN, and 0 otherwise. Or gives you the right final answer.

There's also the canonical return (x > 0) - (x < 0);, but unfortunately most compilers will use branches to generate code for that, even though there are no visible branches. You can try to manually turn it into branchless code as:

int sign(int x)
{
    // assumes 32-bit int/unsigned
    return ((unsigned)-x >> 31) - ((unsigned)x >> 31);
}

which is arguably better than the above as it doesn't depend on implementation defined behavior, but has a subtle bug in that it will return 0 for INT_MIN.

Upvotes: 6

NPE
NPE

Reputation: 500277

First of all, integer comparison is very cheap. It's branching that can be expensive (due to the risk of branch mispredictions).

I have benchmarked your function on a Sandy Bridge box using gcc 4.7.2, and it takes about 1.2ns per call.

The following is about 25% faster, at about 0.9ns per call:

int sign(int x) {
    return (x > 0) - (x < 0);
}

The machine code for the above is completely branchless:

_sign:
    xorl    %eax, %eax
    testl   %edi, %edi
    setg    %al
    shrl    $31, %edi
    subl    %edi, %eax
    ret

Two things are worth pointing out:

  1. The base level of performance is very high.
  2. Eliminating branching does improve performance here, but not dramatically.

Upvotes: 55

anatolyg
anatolyg

Reputation: 28241

If s(x) is a function that returns the sign-bit of x (you implemented it by ((unsigned int)x)>>31), you can combine s(x) and s(-x) in some way. Here is a "truth table":

x > 0: s(x) = 0; s(-x) = 1; your function must return 1

x < 0: s(x) = 1; s(-x) = 0; your function must return -1

x = 0: s(x) = 0; s(-x) = 0; your function must return 0

So you can combine them in the following way:

s(-x) - s(x)

Upvotes: 0

Aniket Inge
Aniket Inge

Reputation: 25695

int i = -10;
if((i & 1 << 31) == 0x80000000)sign = 0;else sign = 1;
//sign 1 = -ve, sign 0 = -ve

Upvotes: -2

Related Questions