java - 是否溢出，与 >>> 运算符

Question

我一直在使用 int mid = low + ((high - low)/2); 来计算中点，因为这可以防止潜在的溢出。这是有道理的，因为 (high - low)/2 确保没有溢出。但是最近我发现了一种更快的方法。这是通过 int mid = (low + high) >>> 1; 实现的。

显然这也不会导致溢出。有人可以解释为什么吗？这与 int mid = (low + high)/2 非常相似，其中 (low + high) 导致溢出。

 System.out.println((Integer.MAX_VALUE + Integer.MAX_VALUE) / 2); // -1
 System.out.println((Integer.MAX_VALUE + Integer.MAX_VALUE) >>> 1); //2147483647

 System.out.println((Integer.MAX_VALUE + (Integer.MAX_VALUE - Integer.MAX_VALUE) / 2)); //2147483647

Answer 1

这通过有效地将您可以表示的最大数量加倍来防止溢出。与 >>> 不同，>>> 不会将符号位视为特殊位，因此就此操作而言，您拥有所有 32 位来表示数字。

为了简化示例，让我们想象一个 3 字节有符号类型，使用补码，就像 Java 对其整数类型所做的那样。

0b000 = 0
0b001 = 1
0b010 = 2
0b011 = 3     // MAX
0b100 = -4    // MIN
0b101 = -3
0b110 = -2
0b111 = -1

在二进制补码中，如果最左边的位为零，则将数字解释为正数。如果最左边的位是一，则为负；反转位并加一以获得幅度。

  0b101 
= -(0b010 + 1) 
= -(2 + 1) 
= -3

... 并且具有将 011 递增到 100 以尽可能合理的方式溢出的理想属性 -- MAX 到MIN，并将 000 递减到 111 得到 -1。

现在，如果我们在此方案中添加 3 + 2，我们就会溢出到负数中:

0b011 + 0b010 = 0b101 

如果我们将其解释为无符号的 3 位整数，这将转换为 5(正确)。但由于 Java 将整数解释为二进制补码，因此它转换为 -3。

-3/2 给出 -1 -- 不是我们想要的答案。

-3 >>> 1 给出 0b101 >>> 1 给出 0b010，也就是 2，我们想要的答案。

所以这里我们使用>>> 1作为“除以二，将原始数字视为无符号整数”。当然你只能用这个除以2的幂。

在 Java 8 中，java.lang.Integer 和 java.lang.Long 中有许多新方法可将数字视为无符号数。一种是 divideUnsigned()，可用于除以任意数:

Returns the unsigned quotient of dividing the first argument by the second where each argument and the result is interpreted as an unsigned value.

优先使用此代码而不是 >>> 可能会对您代码的 future 读者有所帮助。

通过使用无符号安全方法处理整数，您可以处理大于 Integer.MAX_VALUE -- 2^31 -1 的数字。但是如果超过 2^32 -1 仍然会溢出。

最大的 Java 数组或 List 可以是 Integer.MAX_VALUE，因此对于数组或 List 索引，(low + high) >>> 1 或 Integer.divideUnsigned( low + high, 2) 是安全的。