Java，(low + high)>>1会溢出吗？

Question

我知道 >> 表示有符号，>>> 表示无符号

类似的问题不能回答我的问题:

Java, will (low + high) >>> 1 overflow?

Safe integer middle value formula

根据第二个链接，他们为什么得出这样的结论:avg = (low & high) + ((low ^ high) >> 1); 可以避免溢出吗？

为什么他们不能直接使用这个:(low + high) >> 1？

(这是java中的二分查找)

Answer 1

是的，如果总和足够高，(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)