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

So let's consider bytes instead of ints. The only difference is that a byte is an 8-bit integer, while an int has 32 bits. In Java, both are always signed, meaning that the leading bit indicates whether they're positive (0) or negative (1).

byte low = Byte.valueOf("01111111", 2); // The maximum byte value
byte high = low; // This copies low.

byte sum = low + high; // The bit representation of this is 11111110, which, having a
                       // leading 1, is negative. Consider this the worst case
                       // overflow, since low and high can't be any larger.

byte mid = sum >>> 1; // This correctly gives us 01111111, fixing the overflow.

For ints, it's the same thing. Basically the gist of all this is that using an unsigned bitshift on signed integers allows you to leverage the leading bit to handle the largest possible values of low and high.

Answer 2

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 3

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.

Answer 4

The C++ version doesn't solve the overflow issue. It only solves the issue of successfully dividing by 2 using shift instead of /, an optimization that your compiler should be able to make itself if it would be a performance improvement.

On the other hand overflow may not be a real problem, if your integral types are large enough to hold a reasonable range of indices.

Answer 5

You cannot use an unsigned int in Java. In case of overflow, the low 32 bits are considered, and the high order bits are discarded. The unsigned right shift will help u treat the int as unsigned int. However, in C++ you won't have the overflow.

Answer 6

You are safe from integer overflows by using the way you said you already use, which is:

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

Let you compiler do it's job to optimize this if it needs to.

Answer 7

Program synthesis techniques appear to solve such problems.

In this video, the programmer specifies constraints a) no overflow, b) no division, and c) no if-then-else. The synthesizer automatically came up with something pretty nice.

https://youtu.be/jZ-mMprVVBU