10

每当我需要为二分搜索之类的算法平均两个数字时，我总是这样做：

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溢出（它确实溢出，因为整数都是有符号的，但所有位仍然存在，并且没有信息丢失）。像这样取平均值的问题是除法。除法是对有符号值进行运算，因此您的结果将为负数。使用移位代替将除以二，但考虑位而不是符号（有效地将其视为无符号）。

4

7 回答 7

12

您看到的代码已损坏：它没有正确计算负数的平均值。如果您仅对非负值（如索引）进行操作，那没关系，但这不是一般的替代品。你原来的代码，

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);
于 2013-10-01T08:01:12.677 回答
7

所以让我们考虑字节而不是整数。唯一的区别是一个字节是一个 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.

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

于 2013-10-01T01:21:33.427 回答
2

C++ 版本有一个隐藏的欺骗：low并且high是ints，但它们从不是负数。当您将它们转换为unsigned int符号位时，它会变成一个额外的精度位，单次加法不会溢出。

这不是一个很好的作弊方法，因为数组索引unsigned无论如何都应该是。

就像在别处所说的那样，i >> 1表示/2无符号整数。

于 2013-10-01T01:20:26.633 回答
1

C++ 版本没有解决溢出问题。它只解决了使用 shift 而不是 2 成功除以 2 的问题，/如果它可以提高性能，您的编译器应该能够自己进行优化。

另一方面，如果您的整数类型足够大以容纳合理范围的索引，则溢出可能不是真正的问题。

于 2013-10-01T01:13:15.370 回答
0

您不能在 Java 中使用 unsigned int。如果发生溢出，则考虑低 32 位，丢弃高位。无符号右移将帮助您将 int 视为无符号 int。但是，在 C++ 中，您不会有溢出。

于 2013-10-01T01:13:00.517 回答
0

通过使用您所说的已经使用的方式，您可以避免整数溢出，即：

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

如果需要，让您的编译器来优化它。

于 2013-10-01T01:16:21.140 回答
0

程序合成技术似乎可以解决这些问题。

在本视频中，程序员指定了约束 a) 无溢出、b) 无除法和 c) 无 if-then-else。合成器自动想出了一些非常好的东西。

https://youtu.be/jZ-mMprVVBU

于 2020-05-18T23:31:22.260 回答