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

binary-search java bit-manipulation bitwise-operators

2022-09-01 11:29:36

我理解溢出的修复：当添加两个大的正多头时，你可能会得到一个负数。有人可以解释这种按位移位如何神奇地解决溢出问题吗？它与有何不同？>>>>>

我的怀疑：我认为这与Java使用二进制补码的事实有关，所以如果我们有额外的空间，溢出是正确的数字，但因为我们没有，它就会变成负数。因此，当您用零移位和填充时，由于两者的互补性，它会神奇地固定下来。但我可能是错的，有一点脑筋的人必须确认。:)

答案 1

简而言之，是一个技巧，它使用未使用的符号位来执行非负数的正确平均值。(high + low) >>> 1

在假设和都是非负数的情况下，我们确信最上面的位（符号位）为零。highlow

因此，两者和实际上都是31位整数。highlow

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) / 2high + low
作为无符号 32 位整数，总和是正确的。所需要的只是将其除以2。

当然，Java不支持无符号整数，因此我们必须除以2（作为无符号整数）的最好方法是逻辑右移。>>>

在具有无符号整数的语言（例如C和C++）中，它会变得更加棘手，因为您的输入可以是完整的32位整数。一种解决方案是：low + ((high - low) / 2)

最后，列举、和：>>>>>/

>>>是逻辑右移。它用零填充上面的位。
>>是算术右移。它用原始顶部位的副本填充其上部。
/是分裂。

数学：

x >>> 1视为无符号整数并将其除以二。它向下舍入。x
x >> 1视为有符号整数并将其除以 2。它四舍五入到负无穷大。x
x / 2视为有符号整数并将其除以 2。它四舍五入为零。x

答案 2

它将最上面的位填充为零，而不是对它们进行签名填充。

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