Mean of two ints (or longs) without overflow, truncating towards 0

Question

I'd like a way to calculate (x + y)/2 for any two integers x, y in Java. The naive way suffers from issues if x+y > Integer.MAX_VALUE, or < Integer.MIN_VALUE.

Guava IntMath uses this technique:

  public static int mean(int x, int y) {
    // Efficient method for computing the arithmetic mean.
    // The alternative (x + y) / 2 fails for large values.
    // The alternative (x + y) >>> 1 fails for negative values.
    return (x & y) + ((x ^ y) >> 1);
  }

... but this rounds towards negative infinity, meaning the routine doesn't agree with the naive way for values like {-1, -2} (giving -2, rather than -1).

Is there any corresponding routine which truncates towards 0?

"Just use long" is not the answer I'm looking for, since I want a method that works for long inputs too. BigInteger is also not the answer I'm looking for. I don't want a solution with any branches.

Answer 1

You need to add 1 to the result if the lowest bits are different (so the result is not exact and you need to round), and the sign bit in the result is set (the result is negative, so you want to change the round down into a round up).

So the following should do (untested):

public static int mean(int x, int y) {
    int xor = x ^ y;
    int roundedDown = (x & y) + (xor >> 1);
    return roundedDown + (1 & xor & (roundedDown >>> 31));
}