2006-06-05
Extra, Extra - Read All About It: C, C++, Java are Broken
Joshua Bloch reports that Nearly All Binary Searches and Mergesorts are Broken:
The bug is in this line:
6: int mid =(low + high) / 2;In Programming Pearls Bentley says that the analogous line “sets m to the average of l and u, truncated down to the nearest integer.” On the face of it, this assertion might appear correct, but it fails for large values of the int variables low and high. Specifically, it fails if the sum of low and high is greater than the maximum positive int value (231- 1). The sum overflows to a negative value, and the value stays negative when divided by two. In C this causes an array index out of bounds with unpredictable results. In Java, it throws ArrayIndexOutOfBoundsException.
Of course, this bug does not exist in Lisp, Scheme, Python, Ruby, and other languages with proper bignum support. In the context of 21st century computer hardware, there is a strong argument that the bug is in the language, not in the line of code above.
(C# gets half marks for its checked context, where integer overflows cause an exception to be thrown.)
[Update: Patrick Logan gets it. But Tim Bray seems determined not to.]
16 June 2006 18:14
Comment from nikita
Funny point, is that an array of such size that (low + high) could possibly overflow, wouldn't fit into 32-bit address space. :-)
Indeed, overflow implies that at least one of them is greater than 2^30, which implies that a.length > 2^30, which implies that total space occupied by the array is sizeof(int)*a.length > 2^32.
In C you are safe using size_t as a type.