用>>>運算符溢出或不運算

我一直使用int mid = low + ((high - low)/2);來計算中點，因爲這可以防止潛在的溢出。這是有道理的，因爲(high - low)/2確保沒有溢出。但是最近我發現了一個更快的方法。這是通過做int mid = (low + high) >>> 1;。用>>>運算符溢出或不運算

顯然這也不會導致溢出。有人可以解釋爲什麼嗎？這與int mid = (low + high)/2非常相似，其中(low + high)會導致溢出。

System.out.println((Integer.MAX_VALUE + Integer.MAX_VALUE)/2); // -1 
System.out.println((Integer.MAX_VALUE + Integer.MAX_VALUE) >>> 1); //2147483647 

System.out.println((Integer.MAX_VALUE + (Integer.MAX_VALUE - Integer.MAX_VALUE)/2)); //2147483647

來源

2016-10-25 Zanko

通過有效地將您可以表示的最大數量有效翻倍來防止溢出。與>>不同，>>>不會將符號位視爲特殊符號，所以就此操作而言，您可以使用全部32位來表示數字。

爲了讓示例更容易，讓我們設想一個3字節的帶符號類型，使用2的補碼，就像Java對其整數類型所做的那樣。

0b000 = 0 
0b001 = 1 
0b010 = 2 
0b011 = 3  // MAX 
0b100 = -4 // MIN 
0b101 = -3 
0b110 = -2 
0b111 = -1

在二進制補碼中，如果最左邊的位爲零，請將該數字解釋爲正數。如果最左邊的位是一位，那麼這是一個負值;反轉位並添加一個來獲得幅度。

0b101 
= -(0b010 + 1) 
= -(2 + 1) 
= -3

...並且具有作爲明智的方式遞增011到100溢出，因爲可以是期望的特性 - MAX到MIN，和遞減000到111給你-1。

現在，如果我們在該方案中添加3 + 2，我們溢出到底片：

0b011 + 0b010 = 0b101

這將轉化爲5（正確的），如果我們把它解釋爲一個無符號3位整數。但是由於Java將整數解釋爲二進制補碼，因此它轉換爲-3。

-3/2給出-1 - 不是我們想要的答案。

-3 >>> 1給出0b101 >>> 1給出0b010，這是2，我們想要的答案。

所以這裏我們使用>>> 1作爲「除以2，將原始數字視爲無符號整數」。當然，你只能用這個來除以2的冪。

在Java 8中，在java.lang.Integer和java.lang.Long中有許多新方法將數字視爲無符號數。一個是divideUnsigned()其可用於通過任意數量來劃分：

返回其中每個參數和結果被解釋爲一個無符號的值的第二分割的第一個參數的無符號的商。

這可能會有助於您的代碼的未來讀者優先使用此代碼>>>。

通過使用unsigned-safe方法使用整數，您可以處理大於Integer.MAX_VALUE - 2^31 -1的數字。但是如果你超過2^32 -1，你仍然可以溢出。

最大的Java數組或List可以是Integer.MAX_VALUE，所以對於數組或列表索引，(low + high) >>> 1或Integer.divideUnsigned(low + high, 2)是安全的。

來源

2016-10-26 08:49:15 slim

取決於您認爲的「溢出證明」。 >>>運算符本身與溢出無關，其可能溢出的表達式「低+高」。

然而，在實踐中，低/高可能是列表或數組索引（讀取：正整數），並且這會造成所有差異。

雖然加低+高可以超過Integer.MAX_VALUE（這是溢出），「>>> 1」將該參數視爲無符號 - 因此可能溢出並導致符號翻轉的位通過移位使用，將結果帶回到帶符號整數的範圍內。

來源

2016-10-25 16:49:05 Durandal

用>>>運算符溢出或不運算

回答

相關問題