12

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).

gsgx
  • 12,020
  • 25
  • 98
  • 149
  • 1
    Java doesn't have unsigned integers. Consider what would happen if your `int` overflowed? Also consider what `>>>` does. – Sotirios Delimanolis Oct 01 '13 at 01:06
  • I suggest you try it and see what difference it makes. This has been a known issue for decades so you could look it up but you will learn more by figuring it out by yourself. – Peter Lawrey Oct 01 '13 at 01:12

7 Answers7

17

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);
Joni
  • 108,737
  • 14
  • 143
  • 193
  • If one wants the avg(-x,y) to equal -avg(x,y), the division-based approach is better. If one wants avg(x+n,y+n) to equal avg(x,y)+n, an approach with shift-based division may be better. – supercat Jan 10 '14 at 23:58
7

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.

John Zeringue
  • 705
  • 3
  • 13
  • Nice explanation. But if you would forgive my impertinence, what if both numbers were negative? It would appear from your example that the sign bit would/could be lost by that final bit shift. –  Oct 01 '13 at 10:07
  • That's correct. For negative numbers, you'd have to use >>, the signed bit shift. You could easily handle this case with an if-else statement. The only numbers this method doesn't work on is (for bytes) -128 and -128. For other integer types, it's always the minimum value plus itself. If you're curious, I recommend playing around with it yourself. I wouldn't use bytes though. It turns out that Java doesn't support true byte addition, so the code I gave above doesn't work in practice. – John Zeringue Oct 01 '13 at 16:11
  • Note that the original question was about averaging indices, and that negative numbers aren't an issue in that context. – John Zeringue Oct 01 '13 at 16:17
4

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 may be unsigned already. In that case the assumption is that the actual values aren't large enough to overflow even though they could be. If using 64-bit integers then that's a safe enough bet.

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

Adam
  • 16,808
  • 7
  • 52
  • 98
1

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.

Mark B
  • 95,107
  • 10
  • 109
  • 188
0

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.

trimble13
  • 59
  • 3
0

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.

Diego Giagio
  • 1,027
  • 7
  • 7
  • The other code is way more readable than this, and both will probably be the same speed. My questions is why it works... – gsgx Oct 01 '13 at 01:19
  • 1
    What about overflow on the right hand addition? If high is INT_MAX and low is negative, then the addition will overflow => undefined behavior. – Phil Feb 28 '18 at 08:35
  • @Phil it's not really undefined behavior, at least in java. it is pretty known what will happen, the fact that the answer would be wrong in such a case is a different story. – Eugene Jul 18 '19 at 12:35
  • It doesn't work in either language. In C++, int overflow is undefined behavior, and existing compiler's optimizations break code that assumes addition is performed mod 2^n. Java says "the result is the low-order bits of the mathematical sum as represented in some sufficiently large two's-complement format. If overflow occurs, then the sign of the result is not the same as the sign of the mathematical sum of the two operand values." I tried high = Integer.MAX_VALUE and low = -1, and above code gives a negative value on my Java, which is clearly not the midpoint. @Eugene – Phil Jul 19 '19 at 20:18
  • @Phil you said yourself, Java does have a predictable as easy to depict outcome, unlike C++. That was my entire point. And the example usually used for showing how `(a+b)/2` breaks is when `a=b=Integer.MAX_VALUE` – Eugene Jul 20 '19 at 05:20
0

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

user3150318
  • 49
  • 4