两个整数（或长整数）的平均值，避免溢出，并向0截断。

Question

我希望有一种方法可以在Java中计算任意两个整数x,y的平均值(x+y)/2。朴素的方法会遇到问题，如果x+y>Integer.MAX_VALUE或<Integer.MIN_VALUE。

Guava的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也不是我要找的答案。 我不想要任何分支的解决方案。

- BeeOnRope

---

“我不想要任何分支的解决方案。” - 即使最优秀的无分支解决方案比有分支的最佳解决方案还要慢，也不想要分支。 - Stephen C

以下是C++的解决方案：https://dev59.com/aW865IYBdhLWcg3wcOHG#3816473。它也适用于Java。 - Stephen C

你说得对 - 如果有一个在随机输入上比无分支的解决方案表现更好的分支解决方案，我很乐意使用它。我想我表现出了我的偏见 - 我怀疑这样的解决方案是否存在 :) - BeeOnRope

@Stephen C - 你提供的解决方案只适用于无符号值（因此最好实际上替换为guava版本）。对于负数，它仍然向负无穷大四舍五入。 - BeeOnRope

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

- starblue

---

我找不到更快的东西。 - BeeOnRope

Answer 2

为什么不像这样做：(x-y)/2 + y，它可以简化为x/2 - y/2 + y = x/2 + y/2？因此，如果x+y导致溢出或下溢，您可以使用(x-y)/2 + y的方式来解决。

- Anjoola

---

“x - y” 可能会下溢，在与原始问题相同的情况下这是有问题的。此外，如果分支预测不良，则速度非常慢。 - BeeOnRope

我认为如果 x+y 溢出/下溢，那么 x-y 不可能下溢/溢出... - Anjoola

当然可以，但这意味着您需要检查 x + y 是否溢出，引入一个分支，如果输入数据是随机分布的话，这将非常难以预测（因为许多组合将会溢出/下溢）。这就是为什么我说“不要使用分支”。 - BeeOnRope