Math.abs (Math.Abs in C# :-) is one of those methods that sould be pretty simple, right? Just take the value, if it's negative, return a positive version, duh! Well, it's not that simple.
There are 232 possible values of int, each of which is positive, negative or zero. There's only one integer that is zero, namely 0x00000000. That means that either there is one bit pattern of ints that doesn't represent an integer, or there is not a 1-1 mapping between positive and negative numbers. It turns out, the second is the case. The odd number is int.MinValue, which is equal to 0x80000000 in binary.
What happens when you negate this number? In two's complement -x=~x+1. ~x = 0x7fffffff. ~x+1=0x80000000. That means -int.MinValue == int.MinValue. Uh oh!
Enter Math.abs. What's the function to do when passed int.MinValue. Well, in C#, Math.Abs throws an OverflowException. Java, on the other hand, happily returns int.MinValue. Either way, the caller of the function probably wasn't expecting this.
I discovered this oddity when reading Effective Java (kindly provided to all Google Engineers). The book talks about the code: Math.abs (new Random ().nextInt ()) % n as a way to generate random numbers between 0 and n. This code usually works, except when Random happens to return int.MinValue. In this case, the abs returns a negative value, causing the modulus operator to return a negative number. Eeeek!
At this point, I realized that for the data structures course I TA, many students used a similar piece of code in a hashtable they wrote. I wrote a quick script to check how many people screwed up on int.MinValue. Most students did.
I wondered how much this occurred in production code. Luckily, I had one of the best test cases at my fingertips. Google has an internal "grep" tool (the inspiration for the new Code Search) utility. I made a quick regex to find where this occurred. There were many instances.
Now that Google has released an external version of this tool, you can see some of the places this anti-pattern is used in the real world:
Each of these snippits is a time bomb. One in 232 executions, the function will do something strange.
Having found this issue in Google's source code, I emailed somebody inside Google who had been running FindBugs internally. He in turn talked to Bill Pugh, who added a detector. I added a test case to the test suite for the homework assignment at CMU, so students will have to handle this case. All in all, a very obscure bug
So, what should you do rather than Math.abs? I've seen primarially two buggy patterns:
- Hashtables People want to find "which bucket should I put an object with hashcode x in". The best way to do this is (o.GetHashCode () & 0x7fffffff) % table.Length. This has the advantage of being faster than Math.abs (no branches).
- Random Numbers People want to say Math.Abs (new Random ().Next ()) % N. Not only is this buggy in the rare case, it can also cause a bad distribution of numbers for large N. Use the Next (int, int) method which allows you to specify bounds