添加两个数字而不是除以2时,如何使用>>> 1防止溢出？

Question

我已经在一些地方看到以下代码建议添加到数字并除以2,特别是在查找数组中间索引以进行快速排序的上下文中.

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

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

如果我在基础知识上错了,请纠正我.右移位1位(>> 1)具有除以2的效果.因为在java int中,我们不想改变第一位,所以我们使用无符号移位运算符>>>.我听说这可以防止整数溢出,但我不知道如何.根据docs算术运算符主导轮班.这是一个有争议的问题,因为无论如何都要使用括号.如果( )溢出中的任何东西为什么外面的东西很重要？

Answer 1

当您添加两个ints时,该数字可能会溢出为负数,但这些位仍然存在,并且没有信息丢失; int如果Java有这样的类型,它可以被解释为unsigned .让我们试着用这种方法平均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