平均兩個整數（或長）沒有溢出，截斷爲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

回答

相關問題