# Sign of a 32 bit integer

Code
``` 01: int sign(int x) 02: { 03:   // minusOne will be 0xFFFFFFFF (=> -1) for negative numbers, else 0x00000000 04:   int minusOne = x >> 31; 05: 06:   // plusOne will be 0x00000001 for positive numbers, else 0x00000000 07:   unsigned int negateX = (unsigned int) -x; 08:   int plusOne = (int)(negateX >> 31); 09: 10:   // at least minusOne or plusOne is zero, the other one gives our desired result 11:   int result = minusOne | plusOne; 12:   return result; 13: } 14: 15: int sign2(int x) 16: { 17:   return (x > 0) - (x < 0); 18: } ``` bits.stephan-brumme.com

Explanation The sign() function is usually defined as followed:
if x < 0 → sign(x) = −1
if x = 0 → sign(x) =  0
if x > 0 → sign(x) = +1

It's pretty straightforward to convert any negative number into −1, a number where all bits are set.
All we have to do is a full arithmetic right shift that spreads the highest bit (→ 0xFFFFFFFF).
For any 32 bit integer, a right shift of 31 is perfect. The simple code in line 4 stores
the intermediate result 0 (non-negative input) or −1 (negative input) in minusOne.

Note: In C, for unsigned data types an arithmetic shift is generated whereas for signed data types
a logical shift will be used. The difference lies in the value assigned to the new bits on the left side:
An arithmetic right shift copies the highest bit, but a logical right shift always insert a zero.

It is a little bit tricky to get +1 for all positive numbers: the highest bit (bit 31) is always zero.
If we negate any positive number then the highest bit will be set to one (line 7).
Now we perform a logical right shift, which, in contrast to an arithmetic right shift, zeros the high bits (line 8),
just as explained before. That's why negateX must be unsigned while minusOne is signed.
Line 7 and line 8 produce 0 for any non-positive number.

Keep in mind that zero is neither positive nor negative. Negating zero or shifting zero still yields zero,
which is essential to get the right results for both minusOne and plusOne.

Combining minusOne and plusOne gives us the following situation:
if x < 0 → minusOne = −1, plusOne = 0
if x = 0 → minusOne =  0, plusOne =  0
if x > 0 → minusOne =  0, plusOne = +1

It doesn't matter whether we OR (that means ||) or ADD (that means + ) minusOne and plusOne, I choose the latter way.
The code looks a bit ugly in C because we need a few type conversion between int and unsigned int to force
the compiler to generate the right code.

I included a very elegant solution of computing the sign in line 17, that makes use of the way boolean
values are implemented in C. My compilers convert the short C code into similarly short assembler code based on
the SETx instructions of x86/x64 CPUs. Despite it's efficient register usage, it runs much slower than
the first algorithm on my machines. However, this code runs out-of-the-box on 64 bit systems ...

Restrictions • designed for 32 bits, can be easily modified for 64 bits

help me to pay
my server bills

Performance • constant time, data independent

+ Intel® Pentium™ D:
sign: ≈ 2.5 cycles per number
sign2/VC: ≈ 13 cycles per number
sign2/GCC: ≈ 11 cycles per number

+ Intel® Core™ 2:
sign: ≈ 2 cycles per number
sign2/VC: ≈ 5 cycles per number
sign2/GCC: ≈ 3.5 cycles per number

+ Intel® Core™ i7:
sign: ≈ 2.25 cycles per number
sign2/VC: ≈ 5 cycles per number
sign2/GCC: ≈ 3 cycles per number

CPU cycles
(full optimization,
lower values are better)

Assembler Output
``` sign: compiler: Visual C++ 2008 in: ecx ← x out: eax → result 01:   mov eax, ecx 02:   neg eax 03:   shr eax, 31 04:   sar ecx, 31 05:   or  eax, ecx sign2Vc: compiler: Visual C++ 2008 in: eax ← x out: eax → result temp: ecx, edx 01:   xor ecx, ecx 02:   test eax, eax 03:   setg cl 04:   xor edx, edx 05:   test eax, eax 06:   setl dl 07:   sub ecx, edx 08:   mov eax, ecx sign2Gcc: compiler: GCC 4.4 in: edx ← x out: edx → result temp: eax 01:   xor eax, eax 02:   test edx, edx 03:   setg al 04:   shr edx, 31 05:   sub edx, eax ``` bits.stephan-brumme.com