8

我想要一种(x + y)/2在 Java 中计算任意两个整数 x、y 的方法。如果 x+y > Integer.MAX_VALUE 或 < Integer.MIN_VALUE，则幼稚的方法会遇到问题。

GuavaIntMath 使用这种技术：

  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);
  }

...但是这轮到负无穷大，这意味着例程不同意像 {-1, -2} （给出 -2，而不是 -1）这样的值的幼稚方式。

是否有任何相应的例程向 0 截断？

“只需使用long”不是我正在寻找的答案，因为我想要一种也适用于长输入的方法。BigInteger也不是我正在寻找的答案。我不想要任何分支的解决方案。

4

2 回答 2

2

如果最低位不同，则需要添加1到结果中（因此结果不准确，需要四舍五入），并且设置了结果中的符号位（结果为负，因此您要向下舍入进一个回合）。

所以以下应该做（未经测试）：

public static int mean(int x, int y) {
    int xor = x ^ y;
    int roundedDown = (x & y) + (xor >> 1);
    return roundedDown + (1 & xor & (roundedDown >>> 31));
}
于 2013-04-20T16:02:02.007 回答
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.

于 2013-04-20T01:21:53.590 回答