Abstract:
Branchless abs function for x86 processors.

Created by Peter Kankowski
Last changed
Filed under Low-level code optimization

# 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
xor eax, edx
```

Or, in C language:

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

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.

Peter lives in Siberia, the land of sleeping sun, beautiful mountains, and infinitely deep snow. He likes to program in C with a bit of C++, also in x86 assembly language, Python, and PHP (on Windows platform). He can be reached at kankowski@narod.ru.

Created by Peter Kankowski
Last changed

peter_k,
I'm suprised that such easy and small piece of code can be patented :) This are only 3 instructions... So if i want to write small program (in assembler) i should be careful which tricks are patented, which not...
Bit Twiddling Hacks &laquo; Tekquestions&#8217;s Weblog,
[...] Internet Archive also has an old link to it. On January 30, 2007, Peter Kankowski shared with me an abs version he discovered that was inspired by Microsoft’s Visual C++ compiler output. It is featured [...]
jo,

OMG, you could actually patent 3 lines of code. Don't you think this violates people right to explore something and find/create/whatever it accidentally. You CAN'T patent algorithm, there is a huge distinction between method and algorithm. Sun is being silly.

Sergey,
This patent is mistake, becouse this method "optimised abs" was used many years ago in assembler programs on non IBM PC i386 platform (ZX Spectrum,Amiga). And this method was steal.
Faisal Amin,
Thats why I hate big corporations. Very soon we will have to buy air to breath.
sparrowhawk,

god thanks i live outside US, where no software pattents restrict

Sirmabus,

I don't see how it would be a valid patent, and probably easy busted if challenged.

I remember seeing this trick before 1997.

As a matter of a fact I know someone that had it as an answer on their programmers test even.

Although I don't think to many people knew it, and had to be told the answer. This was the early

90's mind you when the internet was just taking off..