Java, will (low + high) >>> 1 overflow?

Question

I am looking at Java 1.8 Api. In the java.util.Arrays.binarySearch(int[] a, int key), I have found this piece of code.

int low = fromIndex;
int high = toIndex - 1;

while (low <= high) {
    int mid = (low + high) >>> 1;
    int midVal = a[mid];

    if (midVal < key)
        low = mid + 1;
    else if (midVal > key)
        high = mid - 1;
    else
        return mid; // key found
}
return -(low + 1);  // key not found.

In this piece of code (low + high) >>> 1 will not overflow. Can anybody tell me why it happened? I test it with my own code.

int low = Integer.MAX_VALUE;
int high = Integer.MAX_VALUE;
System.out.println((low + high) / 2);
System.out.println((low + high) >>> 1);

So, does it mean that the logical right shift will take the overflow bit into consideration?

Answer 1

You are correct that the expression will overflow for sufficiently large values of low and high. You may get an incorrect result if one of the values is negative.

However, you cannot get a negative number in a binary search method, because both low and high are indexes into the array; they must be positive. Therefore, the result of the addition will overflow only into the sign bit; it will not create a carry bit.

Since Java's >>> operator will shift the sign bit without sign extension, you would get the correct result even for two Integer.MAX_VALUE. Essentially, the >>> operator lets you treat the 32-nd bit as an extra bit of unsigned storage, even though the bit belongs to a signed type.

Answer 2

If the result of low + high overflows and becomes negative, neither (low + high) / 2 nor (low + high) >> 1 would work.

a >> 1 keeps the sign bit of the original, so a negative value for a gives a negative result

a >>> 1 works by introducing a zero sign bit, so the result cannot be negative for any a.

Demonstration:

int low = 1;
int high = Integer.MAX_VALUE;
System.out.println(low + high);         // This is negative
System.out.println((low + high) >>> 1); // This is positive, and the desired result.
System.out.println((low + high) >> 1);  // This is negative
System.out.println((low + high) / 2);   // This is negative

Because of overflow, finding the mid-value of two int values is very easy to get wrong. See this question for expressions that work for positive and negative values.