我了解 >>>
修复了溢出:当添加两个大的正长时,您最终可能会得到一个负数。有人能解释一下这种按位移位如何神奇地解决溢出问题吗?它与 >>
有何不同?
我的怀疑:我认为这与 Java 使用二进制补码这一事实有关,因此如果我们有额外的空间,溢出是正确的数字,但因为我们没有,所以它变成了负数。因此,当您移位并用零填充时,由于二进制补码,它会神奇地固定。但我可能是错的,有位头脑的人必须确认。 :)
最佳答案
简而言之,(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。它向零舍入。
关于java - 为什么在 Java 中 (high + low)/2 是错误的,但 (high + low) >>> 1 不是?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13785210/