java - 使用 >>> 1 如何在将两个数字相加而不是除以 2 时防止溢出？

Question

我看过几个places以下代码建议将数字相加并除以 2，特别是在要快速排序的数组中查找中间索引的情况下。

int middle = ( low + high ) >>> 1;

反对int middle = ( low + high )/2;

如果我在基础知识上有误，请纠正我。将位右移 1 个位置 (>> 1) 具有除以 2 的效果。由于在 java 中 int 是有符号的，我们不想更改第一位，所以我们使用无符号移位运算符 >>>。我听说过这样可以防止整数溢出的说法，但我不知道如何做到。根据docs算术运算符负责轮类。这是一个有争议的问题，因为无论如何都会使用括号。如果 ( ) 中的任何内容溢出，为什么外部的东西会很重要？

Answer 1

当你把两个int相加时，这个数可能会溢出成一个负数，但是位还在，没有信息丢失；如果 Java 有这样的类型，它可以被解释为一个无符号的 int。让我们尝试用这种方法平均 2^30 和 2^30 + 2。

  01000000 00000000 00000000 00000000
+ 01000000 00000000 00000000 00000010
  -----------------------------------
  10000000 00000000 00000000 00000010  // overflow

在 Java 中，这将被解释为 -2^30 + 2，但如果它是无符号的，那么它将被解释为 2^31 + 2。

Java 的无符号右移运算符 >>> 向零移动而不是符号扩展。

  10000000 00000000 00000000 00000010  >>> 2 yields
  01000000 00000000 00000000 00000001

这是正确答案，2^30 + 1。

这与带符号的位移运算符 >>> 形成对比，后者符号扩展:

  10000000 00000000 00000000 00000010  >> 2 yields
  11000000 00000000 00000000 00000001

这是不正确的，-2^30 + 1。

这将适用于平均两个正 int 值。但是因为结果总是非负的，所以如果正确的平均值是负的，这将不起作用。

真实例子:

int low = 0x40000000;
int high = 0x40000002;

int unsigned = (low + high) >>> 1;
int signed = (low + high) >> 1;

System.out.println("low     =" + low);
System.out.println("high    =" + high);
System.out.println("unsigned=" + unsigned);
System.out.println("signed  =" + signed);

输出:

low     =1073741824
high    =1073741826
unsigned=1073741825
signed  =-1073741823