In this blog post the author has suggested the following as the bug fix:
int mid = (low + high) >>> 1;
Does anyone know what is this >>> operator? Certainly its not there on the following operator reference list:
What is it and how does that solve the overflow problem?
The >>> operator is in a Java code snippet, and it is the unsigned right shift operator. It differs from the >> operator in its treatment of signed values: the >> operator applies sign extension during the shift, while the >>> operator just inserts a zero in the bit positions "emptied" by the shift.
Sadly, in C++ there's no such thing as sign-preserving and unsigned right shift, we have only the >> operator, whose behavior on negative signed values is implementation-defined. To emulate a behavior like the one of >>> you have to perform some casts to unsigned int before applying the shift (as shown in the code snippet immediately following the one you posted).
The Java expression x >>> y is more or less equivalent to the C++ expression unsigned(x) >> y.