Friday, February 19, 2010

Find the average between two ints (facing possible overflows/underflows)

How do you compute the average between two ints in Java?

How about...
(x + y) / 2

Well, that doesn't work when (x + y) can overflow, and in fact this buggy implementation was lurking in the binary-search and mergesort implementations of JDK till recent years. (Obligatory Josh Bloch link:

It's an interesting puzzle for you to meditate and try out yourself - it looks simple, but it's not. I have yet to find a simple solution that works without assumptions on x, y - just any ints.

Blochs first solution is this:

x + (y - x) / 2

I.e. starting with x and adding half the distance to y. Only that this assumes that x,y > 0, otherwise y-x can itself overflow!

The second solution:

(x + y) >>> 1

Pretty nifty. If (x + y) does overflow, the high bit of the number (which determines the sign) will become one, i.e. negative, but >>> 1 will do the division and put a zero there. But what if (x + y) underflows (x, y are big negative numbers)? Oops.

So neither solution works for all cases.

Still working out a solution. In my case, I only need that average(x, y) != x && average(x, y) != y,  when x and y are not consecutive ints. Any helping hand appreciated :)

My current solution:

static int avg(int x, int y) {
    return diffSign(x, y) ? (x + y) / 2 : x + (y - x) / 2;

static boolean diffSign(int x, int y) {
    return (x ^ y) < 0;

diffSign returns true iff x and y do not have the same sign. In that case only, (x + y) is safe. Otherwise, (y - x) is safe, so I go for that option. This solution works for corner cases (like Integer.MIN_VALUE) too. Well, I don't think I can get it any simpler (assuming it's really correct). Can you?

It turns out there is a much more elegant solution, which is provably correct, found here.

static int avg(int x, int y) {
  return (x & y) + (x ^ y) / 2;