Determine the sign of a 32-bit int

Question

Use ONLY:

! ~ and ^ | + <→

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? At first I thought about switching over 31 bits, and then looked at this sign, but this obviously will not work, and now I'm kind of stuck.

Answer 1

Try the following:

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

How about this:

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

EDIT 2:

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

The assumptions for these decisions are valid:

• x has a 32-bit signed integer.
• On this system, signed 32-bit integers are two additions. (right shift is arithmetic)
• Flow over arithmetic overflow.
• For the first solution, the literal 0 is the same type as x.

Answer 2

If the conditions of conditional statements (not if ) and subtraction are allowed, the simplest and cleanest solution (IMO) is:

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

Do not use subtraction (and it is assumed that 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 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 

Answer 3

Why do you need to use bitwise operators?

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

If you absolutely need to use bitwise operators, you can use the & operator to check for negative values, without the need to change:

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

Answer 4

A bit more confusing, but there is the following:

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

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

For breakdown anywhere we have this design:

 (z >> 31) & 1 

The result will be 1 if negative, and 0 otherwise.

Any place with us:

 (~z + 1) 

We get a negative number (-z)

So, the first half will result in 0xFFFFFFFF (-1) if x is negative, and the second half will produce 0x00000001 (1) if x is positive. Then bitwise or together with them produce 0x00000000 (0), if none of them is true.

Answer 5

What about:

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

.. for a 32-bit signed int, only 2 additions.

!!n gives 1 if n is nonzero. ((n >> 30) & 2) gives 2 if the high bit (sign) is set. Bitwise NOT and +1 take 2 additions to 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 .

Answer 6

Assuming the implementation defines an arithmetic shift to the right:

 (x>>31) | !!x 

Unlike the mystical answer, there is no UB.

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

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

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

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

This version still depends on the implementation, which is a double complement and has either an arithmetic or logical shift to the right, i.e. if the behavior defined by the implementation was something else that could completely break. However, if you change types to unsigned types, all the behavior defined by the implementation disappears, and the result is -1U , 0U or 1U depending on the "sign" (high bit and zero / non-zero status) x .

Answer 7

I'm not sure if this is the perfect way to do something, but I think it is portable enough and at least somewhat easier than yours:

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

Answer 8

Dimitri's idea can be simplified to (!! x) - ((x → 30) and 2)

And just give one more mysterious solution:

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