某些数学表达式的简化形式是否有可能引发溢出错误，而复杂的数学表达式则不会？

Question

我正在尝试 leetcode 的#69 问题，其中涉及求给定数字的平方根。

我通过二分搜索方法进行。

int mySqrt(int x) {
    if (x==0 || x==1){
        return x;
    }
    int start =1;
    int end=x;
    int mid=-1;
    while(start<=end){
        mid=(end+start)/2;//the problem lies here
        long long square=static_cast<long long>(mid)*mid;
        if (square>x){
            end=mid-1;
        }
        else if(square==x){
            return mid;
        }
        else{
            start=mid+1;
        }
     }
     return static_cast<int>(round(end));
}

当我更改 mid=start+(end-start)/2; 测试用例运行良好，但是它对 x=2147483647 抛出“有符号整数溢出”，表示“运行时错误：有符号整数溢出：2147483647 + 1 无法在输入“int”。

Answer 1

直接回答这个问题：是的，数学上等价的不同表达式可以在程序中产生不同的结果。

在这种情况下，如果你先将

start

和

end

相加，然后除以2，如果它们的总和大于

INT_MAX

，就会出现整数溢出。但是，如果您从

start

中减去

end

，则不会出现溢出，因为您正在减去两个正数。

但是，如果数字可能为负数，即使这种方法也不完全正确。更喜欢使用 std::midpoint

 标头中的 

<numeric>（自 C++ 20 起）。

#include <numeric>
// ...
mid = std::midpoint(start, end);