c - 二进制搜索中的逻辑右移防止算术溢出

Question

在二进制搜索实现中，显然：

mid = (low + high)/2

可能导致溢出。我已经阅读了很多文档（如this），以下内容可以防止该问题：

mid = (low + high) >>> 1 

但是，我没有看到这样做的原因。任何人都可以对此有所了解吗？

Answer 1

C 中没有“逻辑右移”之类的东西（没有>>>运算符），所以您可能在谈论 Java。

这是有效的，因为low并且high假定在 0 到 2^31-1 的范围内（假设我们在int这里讨论）。的最大可能值low+high不大于2^32-2，因此可以用 a 表示unsigned int（如果 Java 中存在这样的东西）。Java中不存在这样的东西，所以我们现在已经溢出了。但是，逻辑移位运算符>>>将其操作数视为无符号，因此这给出了预期的结果。

Answer 2

>>>是 Java ( ref )中的无符号右移运算符。因为mid, low, 和high是有符号整数，所以low和的加法high可能会溢出为负值。>>>忽略此结果的潜在负面性并将其向右移动，就好像它是一个无符号数（在 Java 中，没有无符号数）。

在 C 和 C++ 中，这相当于

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

（在您链接到的文章中明确提及）。

这最终与

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

请注意，您可能不想这样做。如果要使用无符号值，则应坚持使用无符号值，并避免在有符号和无符号之间来回跳动。

Answer 3

相同的链接说明了使用 Java 的 >>> 的原因，原因是 (low+high) 可能超过 'mid' 可以容纳的最大值：

在 Programming Pearls Bentley 中说类似的行“将 m 设置为 l 和 u 的平均值，截断为最接近的整数”。从表面上看，这个断言可能看起来是正确的，但是对于 int 变量 low 和 high 的大值，它会失败。具体来说，如果 low 和 high 的总和大于最大正 int 值 (231 - 1)，则会失败。总和溢出为负值，除以 2 时该值保持负数。在 C 中，这会导致数组索引越界，结果不可预测。

它还说明了 C 中的等效操作：

……

在 C 和 C++ 中（没有 >>> 运算符），您可以这样做：

6: 中 = ((unsigned int)low + (unsigned int)high)) >> 1;

所以解决方案是完全阅读和理解那篇文章。

Answer 4

>>>正如其他不是C运营商的答案中提到的那样。

但是，如果你想避免溢出C，你可以试试这个：

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