How does using >>> 1 prevent overflow when adding two numbers than dividing by 2?

Question

I've seen in a few places the following code recommended to add to numbers and divide by 2, particularly in the context of finding a middle index in an array to be quicksorted.

int middle = ( low + high ) >>> 1;

opposed to int middle = ( low + high ) / 2;

Correct me if I'm wrong on the basics. Right shifting bits 1 position (>> 1) has the effect of dividing by 2. Since in java int is signed we don't want to change the first bit, so we use the unsigned shift operator >>>. I've heard the claim this prevents integer overflow but I don't see how. According to the docs arithmetic operators have presidence over shifts. Which is a moot point since brackets are being used anyways. If whatever's in the the ( ) overflows why would something outside matter?

Answer 1

When you add two ints, the number may overflow into a negative number, but the bits are still there, and no information is lost; it could be interpreted as an unsigned int, if Java had such a type. Let's try to average 2^30 and 2^30 + 2 with this method.

  01000000 00000000 00000000 00000000
+ 01000000 00000000 00000000 00000010
  -----------------------------------
  10000000 00000000 00000000 00000010  // overflow

In Java, this would be interpreted as -2^30 + 2, but if it were unsigned, then it would be interpreted as 2^31 + 2.

Java's unsigned bit-shift-right operator, >>>, shifts in a zero instead of sign-extending.

  10000000 00000000 00000000 00000010  >>> 2 yields
  01000000 00000000 00000000 00000001

And that's the correct answer, 2^30 + 1.

That is contrast to the signed bit shift operator, >>, which sign-extends:

  10000000 00000000 00000000 00000010  >> 2 yields
  11000000 00000000 00000000 00000001

That's incorrect, -2^30 + 1.

This will work for averaging two positive int values. But because the result will always be non-negative, this won't work if the correct average value is negative.

Real example:

int low = 0x40000000;
int high = 0x40000002;

int unsigned = (low + high) >>> 1;
int signed = (low + high) >> 1;

System.out.println("low     =" + low);
System.out.println("high    =" + high);
System.out.println("unsigned=" + unsigned);
System.out.println("signed  =" + signed);

The output:

low     =1073741824
high    =1073741826
unsigned=1073741825
signed  =-1073741823