gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-11-30 03:19:10 25 4
gpt4 key购买 nike

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

// 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)

最佳答案

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

  2. 假设lr都是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_MININT_MAX 之间.

  1. 是的,打错了!

关于c++ - 使用 l+(r-l)/2 避免溢出,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53939514/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com