8

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.

starblue
  • 55,348
  • 14
  • 97
  • 151
BeeOnRope
  • 60,350
  • 16
  • 207
  • 386
  • *"I don't want a solution with any branches."* - not even if the best branchless solution is slower than the best solution with branches? – Stephen C Apr 20 '13 at 01:23
  • 2
    Here's a solution for C++: http://stackoverflow.com/a/3816473/139985 . It should work for Java too. – Stephen C Apr 20 '13 at 01:34
  • You are right - if there is a solution with branches that performs better than a branchless one on random input, I'm happy to use it. I guess I was showing my bias - I doubt such a solution exists :) – BeeOnRope Apr 20 '13 at 01:35
  • @Stephen C - the solution you link to only works for unsigned values (so would probably be better replaced the guava version, actually). With negative values it rounds towards negative infinity still. – BeeOnRope Apr 21 '13 at 10:23

2 Answers2

2

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));
}
starblue
  • 55,348
  • 14
  • 97
  • 151
0

Why don't you do something like (x-y)/2 + y, which reduces to x/2 - y/2 + y = x/2 + y/2? So if x+y gives you an overflow or underflow, you do it the (x-y)/2 + y way.

Anjoola
  • 128
  • 9
  • 1
    `x - y` can underflow and this is problematic in the same way as the original. Also, branches are very slow if they are poorly predicted. – BeeOnRope Apr 20 '13 at 02:24
  • I think if `x+y` overflows/underflows, it's not possible for `x-y` to underflow/overflow... – Anjoola Apr 20 '13 at 05:56
  • Sure, but that means that you need to do a check to see if x + y overflows, introducing a branch, which will be very poorly predicted if the input data is randomly distributed (since many combinations will over/underflow). That's why I said "no branches". – BeeOnRope Apr 20 '13 at 06:53