为什么在Java中（high + low）/ 2是错误的，但是（high + low）>>> 1不是吗？

Question

我知道>>>解决了溢出问题：将两个大的正长添加在一起时，您可能最终得到一个负数。有人可以解释这种按位移位如何神奇地解决溢出问题吗？和它有什么不同>>？

我的怀疑：我认为这与Java使用两个补码的事实有关，因此，如果我们有额外的空间，则溢出是正确的数字，但是因为我们没有，所以它变为负数。因此，当您移位并以零进行划桨时，由于两个补全，它神奇地得到了固定。但是我可能是错的，大脑有点位的人必须确认。:)

Answer 1

简而言之，这(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视为有符号整数并将其除以二。向负无穷大舍入。
• x / 2将其x视为有符号整数并将其除以二。舍入为零。