LeetCode第69题：为何简化数学表达式会触发溢出，复杂表达式却不会？

我在解决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;//问题出在这里
        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));
}

当输入x=2147483647时，使用mid=(end+start)/2会触发有符号整数溢出错误，提示“runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'”；而改用mid=start+(end-start)/2时，所有测试用例均可正常运行。

问题原因解析 #

虽然(a+b)/2和a+(b-a)/2在数学上是完全等价的表达式，但在计算机的整数运算中，两者的计算顺序和中间结果的取值范围有本质区别：

• (end+start)/2的溢出风险：
  C中int类型的取值范围是[-2^31, 2^31-1]（即[-2147483648, 2147483647]）。当输入x=2147483647时，二分查找的后期阶段，start和end会逼近2147483647，此时end+start的结果会超过int类型的最大值，触发有符号整数溢出。而有符号整数溢出在C中属于未定义行为，直接导致运行时错误。

• start+(end-start)/2的安全性：
  这个表达式的计算顺序是先算end-start，由于二分查找的循环条件是start<=end，所以end-start的结果是非负的，且最大值为2147483647-1=2147483646，完全在int类型的取值范围内。将这个差值除以2后，结果依然在int范围内，最后加上start，总和也不会超过int的最大值，因此不会触发溢出。

简单来说，数学等价的表达式在计算机整数运算中，因中间步骤的取值范围不同，可能一个触发溢出，一个安全。处理整数运算时，必须优先选择能避免中间结果超出类型范围的写法。

内容的提问来源于stack exchange，提问作者Yogesh Yadav