Compute the integer absolute value (abs) without branching
int v; // we want to find the absolute value of v
int r; // the result goes here
r = (v ^ (v >> (sizeof(int) * CHAR_BIT - 1))) -
(v >> (sizeof(int) * CHAR_BIT - 1));
Some CPUs don't have an integer absolute value instruction (or the compiler fails to use them). On machines where branching is expensive, the above expression can be faster than the obvious approach, r = (v < 0) ? -v : v, even though the number of operations is the same. Caveats: On March 7, 2003, Angus Duggan pointed out that the 1989 ANSI C specification leaves the result of signed right-shift implementation-defined, so on some systems this hack might not work. I've read that ANSI C does not require values to be represented as two's complement, so it may not work for that reason as well (on a diminishingly small number of old machines that still use one's complement). On March 14, 2004, Keith H. Duggar sent me the solution above; it is superior to the one I initially came up with, r=(+1|(v>>(sizeof(int)*CHAR_BIT-1)))*v, because a multiply is not used. Unfortunately, this method has been
patented in the USA on June 6, 2000 by Vladimir Yu Volkonsky and assigned to
Sun Microsystems. (For an unpatented non-multiplying alternative, consider (v ^ (v >> (sizeof(int) * CHAR_BIT - 1))) + ((unsigned) v >> (sizeof(int) * CHAR_BIT - 1)), suggested by Thorbjørn Willoch on June 21, 2004 or my variation, (v ^ (v >> (sizeof(int) * CHAR_BIT - 1))) + (v < 0), both of which take one more operation than the patented one, though it may be computed in parallel on modern CPUs.) On August 13, 2006, Yuriy Kaminskiy told me that the patent is likely invalid because the method was published well before the patent was even filed, such as in
How to Optimize for the Pentium Processor by Agner Fog, dated November, 9, 1996. Yuriy also mentioned that this document was translated to Russian in 1997, which Vladimir could have read. Moreover, the Internet Archive also has an old
link to it.
Выводы:
1. все придумали до нас в 60-70 гг ХХ века.
2. интырнэд знаит всйо!
3. ценность вопросника в том что он показываает где лежат грабли.