Explanation of the safe average of two numbers

Question

Whenever I need to average two numbers for an algorithm like binary search, I always do something like this:

int mid = low + ((high - low) / 2);

I recently saw another way to do it in this post, but I don't understand it. It says you can do this in Java:

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

or this in C++:

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

The C++ version essentially makes both operands unsigned, so doing a shift results in an arithmetic shift instead of a signed shift. I understand what both these pieces of code are doing, but how does this solve the overflow issue? I thought the whole issue was that the intermediate value high + low could overflow?

Edit:

Oh, duh. All the answers didn't exactly answer my question, but it was @John Zeringue's answer that made it click. I'll try to explain here.

The issue with (high + low)/2 in Java isn't exactly that high + low overflows (it does overflow since the integers are both signed, but all the bits are still there, and no information is lost). The issue with taking the average like this is the division. The division is operating on a signed value, so your result will be negative. Using the shift instead will divide by two but consider the bits instead of the sign (effectively treating it as unsigned).

Answer 1

The code you saw is broken: it doesn't compute the average of negative numbers correctly. If you are operating on non-negative values only, like indexes, that's OK, but it's not a general replacement. The code you have originally,

int mid = low + ((high - low) / 2);

isn't safe from overflow either because the difference high - low may overflow the range for signed integers. Again, if you only work with non-negative integers it's fine.

Using the fact that A+B = 2*(A&B) + A^B we can compute the average of two integers without overflow like this:

int mid = (high&low) + (high^low)/2;

You can compute the division by 2 using a bit shift, but keep in mind the two are not the same: the division rounds towards 0 while the bit shift always rounds down.

int mid = (high&low) + ((high^low)>>1);

Answer 2

The C++ version has a hidden cheat: low and high are ints but they're never negative. When you cast them to unsigned int your sign bit becomes an extra precision bit, which a single addition cannot overflow.

It's not a very good cheat because array indices should be unsigned anyway.

Like was said elsewhere, i >> 1 means /2 for unsigned integers.