Fast sign of integer in C

Question

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.

See http://stackoverflow.com/questions/1903954/is-there-a-standard-sign-function-signum-sgn-in-c-c — xanatos, Jan 29 '13 at 09:50
Or more specifically, this answer: http://stackoverflow.com/a/1904074/253056 — Paul R, Jan 29 '13 at 09:51
I think after compilation the original variant will a lot faster with only one test and two condintional jump — qPCR4vir, Jan 29 '13 at 09:53
A good compiler should optimise the original version to a branchless instruction stream anyway. — Paul R, Jan 29 '13 at 09:53
sign = +1 | (v >> (sizeof(int) * CHAR_BIT - 1)); // if v < 0 then -1, else +1 --From the link given by @PaulR — gaganbm, Jan 29 '13 at 09:56
What do you need, a fast calculation or something interesting but not so fast? I see no point avoiding only one (pseudo)comparition with 0 in favor to some other swith and sing change — qPCR4vir, Jan 29 '13 at 10:06
@Paul R : +1... but only a very bad compliler will not optimize this — qPCR4vir, Jan 29 '13 at 10:08
@Alex: Your claim about the duplicate is false. It contains (at least) two C-compatible answers without branches. — GManNickG, Jan 30 '13 at 18:21
"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 '13 at 19:49

NPE · Accepted Answer · 2013-01-30T20:26:13.130

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:

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

Chris Dodd · Answer 2 · 2013-01-30T23:30:06.123

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.

edited Jan 30 '13 at 23:30

answered Jan 30 '13 at 19:48

Chris Dodd

119,907
13
134
226

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 09 '15 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. – Peter Cordes Dec 17 '22 at 17:51
@PeterCordes `-(unsigned)INT_MIN` is `INT_MIN`. `~INT_MIN` is `INT_MAX` and `(unsigned)INT_MAX) + 1` is `INT_MIN`. – Benjamin Riggs May 12 '23 at 20:57
You can avoid the `INT_MIN` bug by doing the negation manually and excluding the addition for `INT_MIN`: `(~x + !!(x^INT_MIN))`, but godbolt shows me this is more instructions than `(x>0)-(x<0)` on every compiler I sampled. – Benjamin Riggs May 12 '23 at 21:05
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. https://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. – Peter Cordes May 12 '23 at 21:27
@PeterCordes `(unsigned) -(unsigned)INT_MIN` is the same as `(unsigned) INT_MIN`, so the bug persists. – Benjamin Riggs May 12 '23 at 21:31
@BenjaminRiggs: Correct, but what bug? For this particular use-case, `INT_MIN` is negative so `INT_MIN >> 31` will be `-1` (assuming a sane implementation where right-shifts round toward -Inf). It doesn't matter what you OR that it (on a 2's complement machine at least), so there's no need to generate the wrong unsigned absolute value; it's perfectly ok to OR in `0x80000000u >> 31` = `1`. The OR trick probably doesn't work on 1's complement machines. – Peter Cordes May 12 '23 at 21:32
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.) – Peter Cordes May 12 '23 at 21:37

score 2 · Answer 3 · answered Aug 07 '13 at 11:50

2

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

answered Aug 07 '13 at 11:50

Bruce

37
3

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). – James Wilkins Sep 30 '17 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 '17 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. – Toby Speight Apr 10 '18 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 08 '20 at 17:00

score 0 · Answer 4 · edited Jun 20 '20 at 09:12

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)

score -1 · Answer 5 · answered Jan 30 '13 at 19:44

-1

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

answered Jan 30 '13 at 19:44

Aniket Inge

25,375
5
50
78

Fast sign of integer in C

5 Answers5

Linked