爲什麼在Java（高+低）/ 2是錯誤的，但（高+低）>>> 1不是？

我明白>>>修復了溢出問題：當增加兩個大的正數時，最終可能會產生負數。有人可以解釋這個按位變換如何神奇地修復溢出問題嗎？它與>>有什麼不同？爲什麼在Java（高+低）/ 2是錯誤的，但（高+低）>>> 1不是？

我的懷疑：我認爲它必須做的事實，Java使用兩恭維所以溢出是正確的號碼，如果我們有額外的空間，但因爲我們不就變成負的。所以當你換零號時，它會因爲兩個讚美而神奇地被固定下來。但我可能是錯的，一個有點腦的人必須證實。 :)

來源

2012-12-09 JohnPristine

我假設您指的是[二進制搜索錯誤]（http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html）？ – Mehrdad

你怎麼知道它修復溢出問題？另外，什麼溢出問題？ – 2012-12-09 06:21:01

Joshua Bloch告訴我：http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html – JohnPristine

總之，(high + low) >>> 1是使用未使用的符號位以執行非負數的正確平均特技。

在假設high和low都是非負的，我們確實知道最上面的位（符號位）爲零。

因此high和low實際上是31位整數。

high = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824 
low = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824

當你將它們加在一起時，它們可能會「溢出」到最高位。

high + low =  1000 0000 0000 0000 0000 0000 0000 0000 
      = 2147483648 as unsigned 32-bit integer 
      = -2147483648 as signed 32-bit integer 

(high + low)/2 = 1100 0000 0000 0000 0000 0000 0000 0000 = -1073741824 
(high + low) >>> 1 = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824

作爲符號的32位整數，它是溢出並翻轉爲負。因此(high + low)/2是錯誤的，因爲high + low可能是負數。
作爲無符號的32位整數，總和是正確的。所有這一切需要的是2

當然分才Java不支持無符號整數，所以我們必須除以2（無符號整數），最好的辦法就是邏輯右移>>> 。

在使用無符號整數（例如C和C++）的語言中，由於輸入可以是完整的32位整數，因此會變得棘手。一種解決方案是：low + ((high - low)/2)

最後到>>>，>>，和/之間枚舉的差異：

>>>是邏輯右移。它用零填充高位。
>>是算術右移。它用原來的最高位的副本填充它的上部。
/是除法。

數學：

x >>> 1對待x爲無符號整數和除以二它。它下降。
x >> 1將x視爲有符號整數並將其除以2。它朝向負無窮。
x/2將x視爲有符號整數並將其除以2。它趨向於零。

來源

2012-12-09 06:37:42 Mysticial

不確定何時使用>>>以及何時使用>>。我認爲在這種情況下，我們選擇>>>來解決可能的溢出（符號位溢出）問題。在>>和>>>之間進行選擇的經驗法則是什麼？ – JohnPristine

+10

'>>>'是邏輯右移。它用零填充高位。 '>>'是算術右移。它用原始頂級位的副本填充高位。在數學上，'>>> 1'將數字視爲無符號數，並將其除以2。 '>> 1'將數字視爲已簽名，並向負無窮的方向舍入。 '/ 2'把這個數字視爲有符號的，並且向零回合。 – Mysticial

它填滿了最高位而不是填充它們。

int a = 0x40000000; 
(a + a)/2 == 0xC0000000; 
(a + a) >>> 1 == 0x40000000;

來源

2012-12-09 06:25:21 Mehrdad

請參閱我的編輯問題... – JohnPristine

@JohnPristine：恩，一個二進制補碼CPU對符號和無符號整數執行完全相同的加法......唯一的區別在於'/ 2'中。所以到目前爲止，一切都是正確的。顯然，由於有足夠的位來表示總和，所以有足夠的位來表示商，而「>>> 1」就是這樣做的。 '/ 2'錯誤的唯一原因是它試圖糾正符號，顯然'>>> 1'執行按位右移，這與無符號除法相同，因此它必須*正常工作。我不確定這是否回答了您的問題... – Mehrdad

我的陳述是否正確：「我認爲這與Java使用雙重讚美的事實有關，因此如果我們有額外的空間，溢出是正確的數字，我們不會變成負面的，所以當你換零槳時，它會被神奇地修復「？ – JohnPristine

我建議你閱讀Joch Bloch的http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html#!/2006/06/extra-extra-read-all-about-it-nearly.html約高低

「二進制搜索的，我寫的JDK版本包含相同的錯誤。據報道，Sun最近時，它打破了別人的方案，等了九年左右。「

來源

2012-12-09 07:08:53

爲什麼在Java（高+低）/ 2是錯誤的，但（高+低）>>> 1不是？

回答

相關問題