平均两个整数（或长）没有溢出，截断为0

我想要一种方法来计算(x + y)/2任何两个整数x，y在Java中。如果x + y> Integer.MAX_VALUE或< Integer.MIN_VALUE，那么天真的方式会遇到问题。平均两个整数（或长）没有溢出，截断为0

番石榴IntMathuses这种技术：

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

来源

2013-04-20 BeeOnRope

*“我不想与任何分支机构的解决方案。” * - 甚至，如果最好的网点解决方案比设有分支机构的最佳解决方案慢？ – 2013-04-20 01:23:30

以下是C++的解决方案：http://stackoverflow.com/a/3816473/139985。它也应该适用于Java。 – 2013-04-20 01:34:43

你说得对 - 如果分支机构的解决方案比随机输入的分支机构性能更好，我很乐意使用它。我想我显示了我的偏见 - 我怀疑这样的解决方案存在:) – BeeOnRope 2013-04-20 01:35:53

如果最低位不同（因此结果不准确并需要舍入），并且结果中的符号位被设置（结果为负数，所以您需要将结果中的符号位设置为零），您需要将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-20 16:02:02 starblue

我找不到更快的东西。 – BeeOnRope 2013-06-06 21:25:32

你为什么不做类似(x-y)/2 + y的减少到x/2 - y/2 + y = x/2 + y/2？所以，如果x+y给你一个溢出或下溢，你可以这样做(x-y)/2 + y的方式。

来源

2013-04-20 01:21:53 Anjoola

'x - y'可以下溢，这与原来的问题相同。另外，如果预测不好，分支会很慢。 – BeeOnRope 2013-04-20 02:24:10

我认为如果'x + y'溢出/下溢，'xy'不可能下溢/溢出...... – Anjoola 2013-04-20 05:56:21

当然，但这意味着您需要检查x + y是否溢出，分支，如果输入数据是随机分布的，那么预测的预测能力就会很差（因为许多组合会出现上溢/下溢）。这就是为什么我说“没有分支机构”。 – BeeOnRope 2013-04-20 06:53:29

平均两个整数（或长）没有溢出，截断为0

回答

相关问题