无中断的两个整数（或长整数）的平均值，截断为0

Question

我想要一种计算(x + y)/2Java中任意两个整数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));
}