Overflowing...

Joshua Bloch is well-known to any Java programmer.  He's been working for Google for years now.  I just ran across his 2006 blog post talking about broken binary sorts and mergesorts, but really the problem he's describing is simply an overflow in binary integer addition: adding together two numbers whose sum is larger than the largest value an integer can hold. 

Joshua's example is using 32 bit integers, which very roughly can hold values between -2 billion and + 2 billion.  So, for example, if you tried to add 1.5 billion to 1.6 billion, the result (3.1 billion) is larger than an integer can hold, and the result is invalid.  That's an overflow.

I was amused to see him write about overflow as though it were a rare and exotic phenomenon.  To those of us who “grew up” with 8 bit microcomputers, overflow is an old “friend” we know very well.  Why?  Well, simply because the largest number an 8 bit integer can hold is quite small (specifically, -128 to +127), so you'll frequently run into overflow in common sorts of problems.  Oh, yes, I know overflow very well.  And I suspect that early experience has made me much more sensitive to the possibility of overflow.  Everywhere I've ever worked, I've run into (and fixed) examples of possible overflow – they're more common than I suspect Joshua knows.

Most recently I found an example in a signum function, where one integer was subtracted from another, and the sign of the result was tested to see if it was positive or negative.  The original code was naively written, making the assumption that no overflow was possible (technically with subtraction the problem is called underflow, but it's really the same thing in the end).  Here's a simple example in 8 bit integers: let's say you were comparing +100 to -100.  The signum function subtracted the second number from the first number (+100 minus -100).  The result you'd expect would be 200 – but that's too large a value to hold in an 8 bit integer.  Overflow is the result.

Here's where a “feature” of Java (and many other languages) gets in the way: Java has no test for overflow, and doesn't produce any exceptions.  In the example above, the result of (+100 minus -100) is a negative number – definitely not the expected value, and not even the right sign.  In a signum function, that means it gives results exactly backward from the intent.  It's certainly possible to write Java code that detects overflows, but it's a bit of a pain, and outside the experience and knowledge of most Java programmers.  In fact, the very possibility of an overflow seems to catch many Java programmers by surprise, which is probably why these problems are so common.

I've recently been programming a PIC microcontroller, one of the very low-end models in the line.  This very primitive little computer is an 8 bit machine, much like the machines I worked on in the '70s.  But unlike them, and to my great surprise, the little PIC doesn't even have overflow detection in hardware.  Overflow detection is trivial for hardware, so I suspect its omission is more oversight than intent.  But in any case, the code I wrote had to look for overflow exactly as you'd have to do in Java...