17

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.

11
  • 3
    See stackoverflow.com/questions/1903954/…
    – xanatos
    Jan 29, 2013 at 9:50
  • 3
    Or more specifically, this answer: stackoverflow.com/a/1904074/253056
    – Paul R
    Jan 29, 2013 at 9:51
  • I think after compilation the original variant will a lot faster with only one test and two condintional jump
    – qPCR4vir
    Jan 29, 2013 at 9:53
  • 5
    A good compiler should optimise the original version to a branchless instruction stream anyway.
    – Paul R
    Jan 29, 2013 at 9:53
  • 4
    "Comparison cost is very high" : how so? Comparing with zero is usually cheap or free, as on every architecture I know the SIGN and ZERO status register bits are set automatically.
    – Roddy
    Jan 30, 2013 at 19:49

5 Answers 5

53

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.
6
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.

8
  • This is very nice. You could get away from the INT_MIN bug by putting x|=x>>1 before the return. INT_MIN is 10000... INT_MIN | INT_MIN>>1 is 11000... which can be negated safely.
    – dodo
    Feb 9, 2015 at 19:16
  • 2
    -x has signed-overflow UB on INT_MIN. Casting first, -(unsigned)x, would avoid that, and give the same binary result on a 2's complement machine. Dec 17, 2022 at 17:51
  • @PeterCordes -(unsigned)INT_MIN is INT_MIN. ~INT_MIN is INT_MAX and (unsigned)INT_MAX) + 1 is INT_MIN. May 12, 2023 at 20:57
  • 1
    @BenjaminRiggs: No, -(unsigned)INT_MIN is an unsigned integer with the value 0x80000000 (the correct magnitude) on machines with 32-bit 2's complement int, like 0u - INT_MIN, because it converts INT_MIN to unsigned first, applying range reduction to get 0x80000000u. Unary - wraps back to the same unsigned value. But -INT_MIN has type int, and has signed overflow UB. godbolt.org/z/7Wzb4sWeG shows the compiler warnings. In practice many compilers wrap, giving -2147483648 (with the same bit-pattern), but you need gcc -fwrapv to make that safe. May 12, 2023 at 21:27
  • 1
    @BenjaminRiggs: Or are you talking about the subtraction version which does have a problem with INT_MIN on 2's complement machines? I wasn't proposing a fix for that, I was just avoiding UB while doing the same binary operations this code is using. It basically assumes -fwrapv, but doesn't need to since we can use unsigned subtraction / negation. (Sorry, I didn't re-read the whole answer before replying to your comment, I forgot part of this answer did have an INT_MIN problem other than requiring wrapping.) May 12, 2023 at 21:37
1
int sign(int x) {    
    return (x>>31)|(!!x);
}  
5
  • He is using the bitwise shift operator. In some languages it is a "Sign-propagating right shift" (such as in JavaScript), which means the sign does not change. Thus, shifting off ALL bits of a 32-bit float using x>>31 leaves only the sign. !!x converts to true or false (1 or 0), then he bitwise "OR"s them together (combines the bits). Sep 30, 2017 at 20:59
  • 1
    Right shifting signed integers is undefined behaviour! You need to cast it to an unsigned integer type: return ((unsigned)x>>31)|(!!x)
    – osvein
    Oct 28, 2017 at 16:46
  • 2
    Not only that, but assuming that int is 32 bits is completely non-portable - you can probably expect it to be sizeof (int) * CHAR_BIT bits. One thing you can't assume is that negative numbers have a particular coding; sign-magnitude, one's complement and two's complement are well-known possibilities, but C doesn't constrain implementations to be one of those. Apr 10, 2018 at 14:41
  • @osvein Sorry, your variant incorrectly returns 1 on all negative values for x. This is not, what the original poster wanted.
    – Kai Petzke
    Oct 8, 2020 at 17:00
  • @osvein No, it is implementation-defined behavior, as in it can be either arithmetic or logic shift, but it cannot cause the program to crash etc. Casting to unsigned is good practice though. And this answer is questionable at best...
    – Lundin
    Sep 26, 2023 at 14:06
0

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)
-2
int i = -10;
if((i & 1 << 31) == 0x80000000)sign = 0;else sign = 1;
//sign 1 = -ve, sign 0 = -ve 
1
  • Left shifting data into the sign bit as was done here (i & 1 << 31) is explicitly undefined behavior.
    – Lundin
    Sep 26, 2023 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.