两个整数(或多头)没有溢出的平均值,截断为0

Question

我想(x + y)/2用Java 计算任意两个整数x,y的方法.如果x + y> Integer.MAX_VALUE或<Integer.MIN_VALUE,则天真的方式会遇到问题.

番石榴IntMath 使用这种技术:

  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也不是我正在寻找的答案.我不想要任何分支机构的解决方案.

Answer 1

如果最低位不同，则需要将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));
}