提问者:小点点

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


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

int中=(低高)

int中=(低高)/2相反;

如果我在基础上错了,请纠正我。右移位1个位置(


共2个答案

匿名用户

当您添加两个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

匿名用户

我注意到有一个错别字:

    >> 2 

应该是:

    >> 1

    >>> 2

应该是

    >>> 1

对于移位运算符示例…