java - 为什么在 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 视为无符号整数并将其除以 2。它向下取整。
• x >> 1 将 x 视为有符号整数并将其除以 2。它向负无穷大舍入。
• x/2 将 x 视为有符号整数并将其除以 2。它向零舍入。