解释两个数字的安全平均值

Question

每当我需要为二进制搜索等算法平均两个数字时,我总是这样做:

int mid = low + ((high - low) / 2);

我最近在这篇文章中看到了另一种方法,但我不明白.它说你可以用Java做到这一点:

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

或者在C++中:

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

C++版本实质上使两个操作数都无符号,因此执行移位会导致算术移位而不是有符号移位.我理解这两段代码正在做什么,但是这如何解决溢出问题呢？我认为整个问题是中间值high + low可能溢出？

编辑:

哦,呃.所有答案都没有完全回答我的问题,但是@John Zeringue的答案让它点击了.我会试着在这里解释一下.

(high + low)/2Java中的问题并不完全是high + low溢出(它会溢出,因为整数都是有符号的,但所有的位仍然存在,并且没有信息丢失).像这样取平均值的问题是分裂.该部门以签名值运行,因此您的结果将为负数.相反,使用移位将除以2但考虑位而不是符号(有效地将其视为无符号).

Answer 1

所以让我们考虑字节而不是整数.唯一的区别是一个字节是一个8位整数,而一个int有32位.在Java中,两者始终都是有符号的,这意味着前导位表示它们是正数(0)还是负数(1).

byte low = Byte.valueOf("01111111", 2); // The maximum byte value
byte high = low; // This copies low.

byte sum = low + high; // The bit representation of this is 11111110, which, having a
                       // leading 1, is negative. Consider this the worst case
                       // overflow, since low and high can't be any larger.

byte mid = sum >>> 1; // This correctly gives us 01111111, fixing the overflow.

对于整数,这是一回事.基本上所有这一点的要点是在有符号整数上使用无符号位移允许您利用前导位来处理低和高的最大可能值.

Answer 2

您看到的代码已损坏:它无法正确计算负数的平均值.如果你只使用非负值,比如索引,那就没关系,但它不是一般的替代品.你原来的代码,

int mid = low + ((high - low) / 2);

溢出也不安全,因为差异high - low可能超出有符号整数的范围.同样,如果你只使用非负整数,那很好.

使用A+B = 2*(A&B) + A^B我们可以计算两个整数的平均值而不会溢出的事实,如下所示:

int mid = (high&low) + (high^low)/2;

您可以使用位移计算除以2,但请记住两者不相同:除法向0舍入,而位移始终向下舍入.

int mid = (high&low) + ((high^low)>>1);