Java, (low + high) >> 1 会溢出吗？
Java, will (low + high) >> 1 overflow?
我知道 >> 是有符号的，>>> 是无符号的
没有回答我问题的类似问题：
Java, will (low + high) >>> 1 overflow?
Safe integer middle value formula
根据第二个 link，他们为什么得出这样的结论：
avg = (low & high) + ((low ^ high) >> 1); 会避免溢出吗？
为什么他们不能直接使用这个：(low + high) >> 1？
（这用于 java 中的二进制搜索）
是的，如果总和足够高，(low + high) >> 1 可能会溢出。如您所知，>>> 用于无符号，因此它总是会在最重要的一侧移动 0。事实证明这非常重要，以防溢出。
使用 (low + high) 的诀窍是即使有溢出，信息仍然保留。如果确实溢出，最大可能的数学和仍然是 Integer.MAX_VALUE * 2，如果 Java 有一个，它仍然可以表示为无符号 int。但是我们可以将和除以2时使用无符号右移运算符>>>处理为无符号整数。当按 1 向右移位时，这让我们将总和视为无符号 int、"un-overflowing" 和 int.
如果总和溢出，这里使用>>将不起作用，因为它会溢出成负数，而>>将移入1，保持负值。这会导致不正确的平均值计算（2 个正数的总和溢出将导致负平均值）。
无论您使用的是 >>> 还是 >>，溢出都是可能的。所以两者都可能溢出。但是只有>>>会处理好，妥妥的"un-overflowing"总和。
诀窍
avg = (low & high) + ((low ^ high) >> 1);
是求和可能溢出时计算平均值的另一种方法。这完全避免了溢出。这将总和分解为两部分——"carry" 位和 "non-carry" 位。
当使用加法时，结转到下一个更高有效位的位是当两个位都设置时 -- low & high。通常另外，这些位必须左移，但我们计算的是 2 个数字的平均值，所以我们最后也会右移。最终结果：此处没有偏移。
未携带的位要么是 1（如果位不同），要么是 0（如果位相同）——这就是 (low ^ high) 的来源（异或）。此外，通常这些位不会移动，但我们正在计算 2 个数字的平均值，所以我们最后也会右移。这种转变显示为 >> 1。 & 和 ^ 运算符不会溢出，因此 >> 在这里工作得很好。
示例：1100 (12) 和 1010 (10) 的平均值
1100 & 1010 = 1000
1100 ^ 1010 = 0110, 0110 >> 1 = 0011
1000 + 0011 = 1011 (11)
我知道 >> 是有符号的，>>> 是无符号的
没有回答我问题的类似问题：
Java, will (low + high) >>> 1 overflow?
Safe integer middle value formula
根据第二个 link，他们为什么得出这样的结论：
avg = (low & high) + ((low ^ high) >> 1); 会避免溢出吗？
为什么他们不能直接使用这个：(low + high) >> 1？
（这用于 java 中的二进制搜索）
是的，如果总和足够高，(low + high) >> 1 可能会溢出。如您所知，>>> 用于无符号，因此它总是会在最重要的一侧移动 0。事实证明这非常重要，以防溢出。
使用 (low + high) 的诀窍是即使有溢出，信息仍然保留。如果确实溢出，最大可能的数学和仍然是 Integer.MAX_VALUE * 2，如果 Java 有一个，它仍然可以表示为无符号 int。但是我们可以将和除以2时使用无符号右移运算符>>>处理为无符号整数。当按 1 向右移位时，这让我们将总和视为无符号 int、"un-overflowing" 和 int.
如果总和溢出，这里使用>>将不起作用，因为它会溢出成负数，而>>将移入1，保持负值。这会导致不正确的平均值计算（2 个正数的总和溢出将导致负平均值）。
无论您使用的是 >>> 还是 >>，溢出都是可能的。所以两者都可能溢出。但是只有>>>会处理好，妥妥的"un-overflowing"总和。
诀窍
avg = (low & high) + ((low ^ high) >> 1);
是求和可能溢出时计算平均值的另一种方法。这完全避免了溢出。这将总和分解为两部分——"carry" 位和 "non-carry" 位。
当使用加法时，结转到下一个更高有效位的位是当两个位都设置时 -- low & high。通常另外，这些位必须左移，但我们计算的是 2 个数字的平均值，所以我们最后也会右移。最终结果：此处没有偏移。
未携带的位要么是 1（如果位不同），要么是 0（如果位相同）——这就是 (low ^ high) 的来源（异或）。此外，通常这些位不会移动，但我们正在计算 2 个数字的平均值，所以我们最后也会右移。这种转变显示为 >> 1。 & 和 ^ 运算符不会溢出，因此 >> 在这里工作得很好。
示例：1100 (12) 和 1010 (10) 的平均值
1100 & 1010 = 1000
1100 ^ 1010 = 0110, 0110 >> 1 = 0011
1000 + 0011 = 1011 (11)