Average value of two ints (or longs) without overflow, truncation in the 0 direction

Question

I would like to calculate (x + y)/2 for any two integers x, y in Java. The naive way suffers from problems 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 is rounded to negative infinity, that is, the subroutine is not consistent with the naive way for values ​​like {-1, -2} (giving -2, not -1).

Is there any appropriate procedure that truncates in the 0 direction?

“Just use long ” is not the answer I'm looking for since I need a method that also works for long inputs. BigInteger also not the answer I'm looking for. I do not want a solution with any branches.

Answer 1

You need to add 1 to the result if the least significant bits are different (therefore, 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 to round).

So the following (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)); } 

Answer 2

Why don't you do something like (xy)/2 + y , which boils down to x/2 - y/2 + y = x/2 + y/2 ? Therefore, if x+y gives you overflow or underflow, you do it in the way (xy)/2 + y .