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

These ads
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
Performance Chart
CPU cycles
(full optimization,
lower values are better)

Assembler Output
sign:
01:   mov eax, ecx
02:   neg eax
03:   shr eax, 31
04:   sar ecx, 31
05:   or  eax, ecx

sign2Vc:
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:
01:   xor eax, eax
02:   test edx, edx
03:   setg al
04:   shr edx, 31
05:   sub edx, eax
 bits.stephan-brumme.com

Download The full source code including a test program is available for download.

References "PowerPC Compiler Writer's Guide" by IBM
http://the.wall.riscom.net/books/proc/ppc/cwg/cwgix.html

More Twiddled Bits
  1. Absolute value of a float
  2. Absolute value of an integer
  3. Approximative inverse of a float
  4. Bit manipulation basics
  5. Bit mask of lowest bit not set
  6. Count bits set in parallel a.k.a. Population Count
  7. Detects zero bytes inside a 32 bit integer
  8. Endianess
  9. Extend bit width
  10. Float inverse square root approximation
  11. Float square root approximation
  12. Is power of two
  13. Minimum / maximum of integers
  14. Parity
  15. Position of lowest bit set
  16. Round up to the next power of two
  17. Sign comparison
  18. Sign of a 32 bit integer
  19. Swap two values
Extra: Javascript bit manipulator

... or go to the index