Optimized abs function

Microsoft's algorithm

Microsoft Visual C++ 2005 generates the following code for integer abs function:

cdq           ; if eax >= 0 then edx := 0
              ;             else edx := 0xFFFFFFFF

xor eax, edx  ; if eax >= 0 then eax := eax xor 0 = eax 
              ;             else edx := eax xor 0xFFFFFFFF = not eax

sub eax, edx  ; if eax >= 0 then eax := eax xor 0 - 0 = eax 
              ;             else edx := (eax xor -1) - (-1) = not eax + 1 = -eax

The first instruction, CDQ, copies the sign bit from eax register to edx. So, if eax was negative, edx will be –1 (0xFFFFFFFF); otherwise, it will be zero.

When one operand of XOR is zero, it returns another operand. Also, XORing something with –1 is equivalent to bitwise NOT:

A ⊕ 0 = A

A ⊕ –1 = ¬A, where –1 is a register with all bits set to 1

(You can verify these formulas with the truth table for XOR).

The last instruction substracts edx from eax. If eax is positive, edx is 0, and the instruction doesn't change the number. But when eax < 0, it adds 1 to it, effectively computing –eax:

¬A + 1 = –A

This clever trick helps to avoid a conditional jump, which can cost you a dozen of cycles if it will be mispredicted. The code also demonstrates a smart choice of instructions: CDQ is fast on all processors, while the equivalent shift (SAR eax, 31) is slow on Pentium IV.

However, the author of Bit Twiddling Hacks mention that the algorithm was patented by some Russian guy working at Sun. If you a lawyer specialized in US patent law, please comment whether Microsoft's use of the abs function violates the Sun's patent.

Alternative algorithm

Here is an alternative to Microsoft's method:

cdq
add eax, edx
xor eax, edx

Or, in C language:

int my_abs(int a) {
   int mask = (a >> (sizeof(int) * CHAR_BIT - 1));
   return (a + mask) ^ mask;
}

Explaining why it works is left as an exercise to reader. Here is a hint for you:

¬(A – 1) = –A

Legal note. This wiki page does not claim that any of the algorithms is free from the power of Sun's patent. You should consult with your lawyer before using the code in compilers or code generators.