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

Question

我正在查看 Java 1.8 Api。在 java.util.Arrays.binarySearch(int[] a, int key) 中，我找到了这段代码。

int low = fromIndex;
int high = toIndex - 1;

while (low <= high) {
    int mid = (low + high) >>> 1;
    int midVal = a[mid];

    if (midVal < key)
        low = mid + 1;
    else if (midVal > key)
        high = mid - 1;
    else
        return mid; // key found
}
return -(low + 1);  // key not found.

这段代码中(low + high) >>> 1不会溢出。谁能告诉我为什么会这样？我用我自己的代码测试它。

int low = Integer.MAX_VALUE;
int high = Integer.MAX_VALUE;
System.out.println((low + high) / 2);
System.out.println((low + high) >>> 1);

那么，是否意味着逻辑右移会考虑溢出位？

Answer 1

您是正确的，对于足够大的 low 和 high 值，表达式会溢出。如果其中一个值为负，您可能会得到不正确的结果。

但是，您不能在二进制搜索方法中得到负数，因为 low 和 high 都是数组的索引；他们必须是积极的。因此，加法的结果只会溢出到符号位；它不会产生进位。

由于 Java 的 >>> 运算符会在没有符号扩展的情况下移动符号位，因此即使对于两个 Integer.MAX_VALUE，您也会得到正确的结果。本质上，>>> 运算符允许您将第 32 位视为无符号存储的额外位，即使该位属于有符号类型。