Determine the sign of a 32 bit int

问题:

Using ONLY:

! ~ & ^ | + << >>

NO LOOPS

I need to determine the sign of a 32 bit integer and I need to return 1 if positive, 0 if 0 and -1 if negative.

Any ideas? I first thought about shifting over 31 bits and then looking at that sign but that obviously wont work and now I am kind of stuck.

回答1:

Try this:

(x >> 31) | (((0 - x) >> 31) & 1)

How about this:

(x >> 31) | (((~x + 1) >> 31) & 1)

EDIT 2:

In response to issues (or rather nit-picking) raised in the comments...

Assumptions for these solutions to be valid:

1. x is of type 32-bit signed integer.
2. On this system, signed 32-bit integers are two's complement. (right-shift is arithmetic)
3. Wrap-around on arithmetic overflow.
4. For the first solution, the literal 0 is the same type as x.

回答2:

If conditionals (not if statements) and subtraction are allowed, the simplest & cleaner solution (IMO) is:

int sign = (v > 0) - (v < 0);

Not using subtraction (and assuming int is 32 bits):

#include <stdio.h>
#include <assert.h>
#include <limits.h>

int process(int v) {
    int is_negative = (unsigned int)v >> 31; // or sizeof(int) * CHAR_BIT - 1
    int is_zero = !v;
    int is_positive = !is_negative & !is_zero;
    int sign = (is_positive + ~is_negative) + 1;
    return sign;
}

int main() {
    assert(process(0) == 0);
    printf("passed the zero test\n");
    for (int v = INT_MIN; v < 0; v++) {
        assert(process(v) == -1);
    }
    printf("passed all negative tests\n");
    for (int v = 1; v < INT_MAX; v++) {
        assert(process(v) == +1);
    }
    printf("passed all positive tests\n");
    return 0;
}

Here's are the results:

$ gcc -o test test.c -Wall -Wextra -O3 -std=c99 && ./test && echo $#
passed zero test
passed all negative tests
passed all positive tests
0

回答3:

Why do you need to use bitwise operators for that?

int get_sign(int value)
{
    return (value < 0) ? -1 : (int)(value != 0);
}

If you absolutely have to use bitwise operators, then you can use the & operator to check for negative values, no shifting needed:

int get_sign(int value)
{
    return (value & 0x80000000) ? -1 : (int)(value != 0);
}

If you want to shift:

int get_sign(int value)
{
    return ((value >> 31) & 1) ? -1 : (int)(value != 0);
}

回答4:

A bit more convoluted, but there is this:

(~((x >> 31) & 1) + 1) | (((~x + 1) >> 31) & 1)

This should take care of the ambiguity of whether the shift will fill in 1's or 0's

For a breakdown, any place we have this construct:

(z >> 31) & 1

Will result in a 1 when negative, and a 0 otherwise.

Any place we have:

(~z + 1)

We get the negated number (-z)

So the first half will produce a result of 0xFFFFFFFF (-1) iff x is negative, and the second half will produce 0x00000001 (1) iff x is positive. Bitwise or'ing them together will then produce a 0x00000000 (0) if neither is true.

回答5:

What about:

int getsign(int n)
{
  return (!!n) + (~((n >> 30) & 2) + 1);
}

..for 32-bit signed int, 2's complement only.

!!n gives 1 if n is nonzero. ((n >> 30) & 2) gives 2 iff the high bit (sign) is set. The bitwise NOT and +1 take the 2's complement of this, giving -2 or 0. Adding gives -1 (1 + -2) for negative values, 0 (0 + 0) for zero, and +1 (1 + 0) for positive values.

回答6:

Assuming the implementation defines arithmetic right shift:

(x>>31) | !!x

Unlike Mystical's answer, there is no UB.

And, if you want to also support systems where right shift is defined to be arithmetic shift:

~!(x>>31)+1 | !!x

Edit: Sorry, I omitted a ! in the second version. It should be:

~!!(x>>31)+1 | !!x

This version is still dependent on the implementation being twos complement and having either arithmetic or logical right-shift, i.e. if the implementation-defined behavior were something else entirely it could break. However, if you change the types to unsigned types, all of the implementation-defined behavior vanishes and the result is -1U, 0U, or 1U depending on the "sign" (high bit and zero/nonzero status) of x.

回答7:

I'm not sure this is the absolute ideal way to do things, but I think it's reasonably portable and at least somewhat simpler than what you had:

#define INT_BITS 32

int sign(int v) { 
    return (!!v) | -(int)((unsigned int)v >> (INT_BITS-1));
}

回答8:

Dimitri's idea could be simplified to (!!x) - ((x >> 30) & 2)

And just to give one more cryptic solution:

~!x & ((-((unsigned) x >> 31)) | !!x)