c++ - 使用 l+(r-l)/2 避免溢出

Question

当我学习合并排序实现时，我遇到了下面的代码:

// Same as (l+r)/2, but avoids overflow for 
// large l and h 
int m = l+(r-l)/2;

1. (l+r)/2 与 l+(r-l)/2 有何相同之处？后者计算为 r/2。

2. (l+r)/2 是如何导致溢出的，l+(r-l)/2 是如何解决问题的？

3. h 是什么？ (我认为这是一个错字，应该是 r)

Answer 1

1. 请再次检查 - 它扩展为 l + r/2 - l/2 即 l/2 + r/2。请注意，我们不能只使用 l/2 + r/2 因为会有整数截断，所以 3/2 + 5/2 = 1 + 2 = 3，但所需的值为 4。

2. 假设l和r都是int类型的正值。

如果我们有:

int l = INT_MAX - 2;
int r = INT_MAX;

那么l + r部分就是INT_MAX - 2 + INT_MAX，这是整数溢出。 INT_MAX - 2 + (INT_MAX - (INT_MAX - 2))/2 没有整数溢出，因为每个子表达式都保持在 INT_MIN 和 INT_MAX 之间.

1. 是的，打错了!