我正在查看 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);
那么,是否意味着逻辑右移会考虑溢出位?
最佳答案
您是正确的,对于足够大的 low
和 high
值,表达式会溢出。如果其中一个值为负,您可能会得到不正确的结果。
但是,您不能在二进制搜索方法中得到负数,因为 low
和 high
都是数组的索引;他们必须是积极的。因此,加法的结果只会溢出到符号位;它不会产生进位。
由于 Java 的 >>>
运算符会在没有符号扩展的情况下移动符号位,因此即使对于两个 Integer.MAX_VALUE
,您也会得到正确的结果。本质上,>>>
运算符允许您将第 32 位视为无符号存储的额外位,即使该位属于有符号类型。
关于Java, (low + high) >>> 1 会溢出吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33616299/