我知道 >>
表示有符号,>>>
表示无符号
类似的问题不能回答我的问题:
Java, will (low + high) >>> 1 overflow?
Safe integer middle value formula
根据第二个链接,他们为什么得出这样的结论:
avg = (low & high) + ((low ^ high) >> 1);
可以避免溢出吗?
为什么他们不能直接使用这个:(low + high) >> 1
?
(这是java中的二分查找)
最佳答案
是的,如果总和足够高,(low + high) >> 1
可能会溢出。如您所知,>>>
表示无符号,因此它始终会在最重要的一侧移入 0
。事实证明,这非常重要,以防溢出。
即使溢出,使用(low + high)
的技巧是信息仍然保留。如果它确实溢出,则最大可能的数学和仍然是 Integer.MAX_VALUE * 2
,如果 Java 有的话,它仍然可以表示为无符号 int
。但是,当除以 2 时,我们可以使用无符号右移运算符 >>>
将总和视为无符号 int。当向右位移 1
时,我们可以将总和视为无符号 int
,即“不溢出”int
。
如果总和溢出,在这里使用>>
将不起作用,因为它会溢出成负数,并且>>
将移入1
,保留负值。这会导致平均值计算不正确(2 个正数的总和溢出将导致平均值为负)。
无论您使用的是 >>>
还是 >>
,溢出都有可能。所以两者都会溢出。但只有 >>>
能够很好地处理这种情况,正确地“不溢出”总和。
技巧
avg = (low & high) + ((low ^ high) >> 1);
是当总和可能溢出时计算平均值的另一种方法。这完全避免了溢出。这将总和分为两部分——“进位”位和“非进位”位。
当使用加法时,当两个位都被设置时,被转移到下一个更高有效位的位 - 低和高
。另外,通常情况下,这些位必须左移,但我们计算的是 2 个数字的平均值,所以最后我们也会右移。最终结果:这里没有变化。
如果位不同,则未携带的位为 1
;如果位相同,则为 0
- 这就是 (低^高)
来自(XOR)。另外,通常情况下,这些位不会移位,但我们计算的是 2 个数字的平均值,因此我们最后也会右移。此转变显示为 >> 1
。 &
和 ^
运算符不会溢出,因此 >>
在这里可以正常工作。
示例:1100 (12) 和 1010 (10) 的平均值
1100 & 1010 = 1000
1100 ^ 1010 = 0110, 0110 >> 1 = 0011
1000 + 0011 = 1011 (11)
关于Java,(low + high)>>1会溢出吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36296982/