Java，将(低+高)>> 1溢出?

问题描述

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

I am looking at Java 1.8 Api.In the java.util.Arrays.binarySearch(int[] a, int key), I have found this piece of code.

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不会溢出.谁能告诉我为什么会这样吗?我用自己的代码对其进行测试.

In this piece of code (low + high) >>> 1 will not overflow.Can anybody tell me why it happened? I test it with my own code.

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

那么，这是否意味着逻辑右移将考虑溢出位?

So, does it mean that the logical right shift will take the overflow bit into consideration?

推荐答案

对于正确的low和high值，表达式将溢出.如果其中一个值为负数，则可能会得到错误的结果.

You are correct that the expression will overflow for sufficiently large values of low and high. You may get an incorrect result if one of the values is negative.

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

However, you cannot get a negative number in a binary search method, because both low and high are indexes into the array; they must be positive. Therefore, the result of the addition will overflow only into the sign bit; it will not create a carry bit.

由于Java的>>>运算符将移位不带符号扩展名的符号位，因此即使对于两个Integer.MAX_VALUE也将获得正确的结果.本质上，>>>运算符使您可以将第32位视为额外的无符号存储位，即使该位属于带符号的类型也是如此.

Since Java's >>> operator will shift the sign bit without sign extension, you would get the correct result even for two Integer.MAX_VALUE. Essentially, the >>> operator lets you treat the 32-nd bit as an extra bit of unsigned storage, even though the bit belongs to a signed type.

这篇关于Java，将(低+高)>> 1溢出?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！