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

Question

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

mid = (low + high)/2

会导致溢出。我已经阅读了很多文档(如 this )，以下内容可以防止出现问题:

mid = (low + high) >>> 1 

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

Answer 1

>>>> 是 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;

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