为什么左+(右 - 左)/ 2不会溢出？

Question

本文内容:http://googleresearch.blogspot.sg/2006/06/extra-extra-read-all-about-it-nearly.html,它提到最快速排序算法有一个bug(左+右)/ 2 ,它指出解决方案是使用left+(right-left)/2而不是(left+right)/2.在快速排序示例(K&R C book)中也给出了问题Bug的解决方案？

我的问题是为什么left+(right-left)/2可以避免溢出？怎么证明呢？提前致谢.

Answer 1

你有left < right定义.

因此,right - left > 0并且left + (right - left) = right(从基本代数开始).

因此left + (right - left) / 2 <= right.因此,不会发生溢出,因为操作的每一步都受到值的限制right.

相比之下,考虑有缺陷的表达,(left + right) / 2.left + right >= right,因为我们不知道的价值观left和right,这是完全可能的,该值溢出.

Answer 2

基本逻辑。

1. 根据定义left <= MAX_INT
2. 根据定义right <= MAX_INT
3. left+(right-left)等于right，这已经是<= MAX_INT#2
4. 因此也left+(right-left)/2 必须<= MAX_INT如此，因为x/2总是小于x。

与原版比较

1. 根据定义left <= MAX_INT
2. 根据定义right <= MAX_INT
3. 所以left+right <= MAX_INT
4. 所以(left+right)/2 <= MAX_INT

其中语句 3 显然是错误的，因为leftcan 是MAX_INT（语句 1），所以也可以right（语句 2）。

Answer 3

一个简单的例子将展示它。为简单起见，假设数字溢出到上面999。如果我们有：

left = 997
right = 999

然后：

left + right = 1996

在我们到达之前它已经溢出了/2。然而：

right - left = 2
(right-left)/2 = 1
left + (right-left)/2 = 997 + 1 = 998

所以我们避免了溢出。

更一般地说（正如其他人所说）：如果 和 都left在right范围内（并假设right > left，那么也(right-left)/2将在范围内，因此也必须在范围内，left + (right-left)/2因为这必须小于right（因为您已经增加了left它和 之间的差距的一半right。

Answer 4

假设（为了使示例更容易）最大整数是 100、left = 50、 和right = 80。如果您使用朴素的公式：

int mid = (left + right)/2;

添加将导致130，溢出。

如果你这样做：

int mid = left + (right - left)/2;

你不能溢出，(right - left)因为你从一个较大的数字中减去一个较小的数字。这总是导致一个更小的数字，所以它不可能超过最大值。例如80 - 50 = 30。

而且，由于该结果是平均的left和right，一定是他们之间。由于它们都小于最大整数，因此它们之间的任何值也都小于最大值，因此没有溢出。

Answer 5

由于 Java 中 int 数据类型是 32 位（假设编程语言），任何超过 32 位的值都会被翻转。从数值角度来说，这意味着 Integer.MAX_VALUE (2147483647) 加 1 后，返回值将为 -2147483648。

回到上面的问题，让我们假设以下内容：

int left = 1;
int right = Integer.MAX_VALUE;
int mid;

情况1：

mid = (left +right)/2; 
//Here the value of left + right would be -2147483648 which would overflow.

案例2：

mid = left + (right - left)/2;
//This would not have the same problem as above as the value would never exceed "right".

理论上：

两个值都与left + (right - left)/2 = (2*left + right - left)/2 = (left + right)/2相同

希望这能回答您的问题。