解释两个数字的安全平均值
每当我需要为二进制搜索等算法平均两个数字时，我总是这样做：
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的答案让它点击了。 我会试着在这里解释一下。
Java中的(high + low)/2问题并不完全是high + low溢出（它会溢出，因为整数都是有符号的，但所有的位仍然存在，并且没有信息丢失）。 像这样取平均值的问题是分裂。 该部门以签名值运作，因此您的结果将为负数。 相反，使用移位将除以2但考虑位而不是符号（有效地将其视为无符号）。
所以让我们考虑字节而不是整数。 唯一的区别是一个字节是一个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.
对于整数，这是一回事。 基本上所有这一点的要点是在有符号整数上使用无符号位移允许您利用前导位来处理低和高的最大可能值。
您看到的代码已损坏：它无法正确计算负数的平均值。 如果你只使用非负值，比如索引，那就没关系，但它不是一般的替代品。 你原来的代码，
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);
C ++版本有一个隐藏的作弊： low和high是int但它们永远不会消极。 当您将它们转换为unsigned int您的符号位将成为一个额外的精度位，单个加法不会溢出。
这不是一个很好的作弊因为数组索引无论如何都应该是unsigned的。
就像在其他地方所说的那样， i >> 1表示/2表示无符号整数。
C ++版本无法解决溢出问题。 它只解决了使用shift而不是/来成功除以2的问题，如果这是一个性能改进，那么编译器应该能够自己进行优化。
另一方面，如果您的积分类型足够大以容纳合理的索引范围，则溢出可能不是真正的问题。
您不能在Java中使用unsigned int。 在溢出的情况下，考虑低32位，并且丢弃高位。 无符号右移将帮助您将int视为unsigned int。 但是，在C ++中你不会有溢出。
使用您已经使用过的方式可以避免整数溢出，这是：
int mid = low + ((high - low) / 2);
如果需要，让编译器做它的工作来优化它。