递归计算整数平方根的C代码输入3时异常的原因及修复方法

首先，先把你的代码贴出来方便分析：

int ft_sqrt(int nb){ 
    int smallcandidate; 
    int largecandidate; 
    if (nb < 0){ 
        return (0); 
    }else if (nb < 2){ 
        return (nb); 
    }else{ 
        smallcandidate = ft_sqrt(nb >> 2) << 1; 
        largecandidate = smallcandidate + 1; 
        if (largecandidate * largecandidate > nb){ 
            return (smallcandidate); 
        } else{ 
            return (largecandidate); 
        } 
    } 
}

输入3时的执行流程与结果说明 #

当你输入nb=3时，函数的执行步骤是这样的：

1. 3既不小于0，也不小于2，进入递归分支。
2. nb >> 2是把3右移2位，相当于整数除法3/4，结果是0。
3. 递归调用ft_sqrt(0)，因为0<2，直接返回0。
4. smallcandidate等于0 << 1（左移1位），结果还是0。
5. largecandidate是0+1，结果为1。
6. 判断1*1 > 3？显然不成立，所以返回largecandidate也就是1。

这里的“异常”其实是对整数平方根定义的误解。整数平方根的标准定义是：找到最大的整数x，使得x² ≤ n。对于3来说，1的平方是1≤3，而2的平方是4>3，所以正确结果就是1，你的函数返回完全符合预期。

代码的潜在问题（溢出） #

不过你的代码确实存在一个通用的隐患：当largecandidate数值较大时，largecandidate * largecandidate会超出int的取值范围，导致整数溢出，进而引发错误判断。比如当输入nb=INT_MAX（2147483647）时，largecandidate=46341，它的平方是2147488281，已经超过了int的最大值，会溢出成负数，此时负数 > INT_MAX的判断为假，函数会错误返回46341，但正确的整数平方根应该是46340。

溢出问题的修复方案 #

我们可以用除法代替乘法来避免溢出，因为largecandidate > nb / largecandidate和largecandidate*largecandidate > nb是等价的（当largecandidate>0时），修改后的代码如下：

int ft_sqrt(int nb){ 
    int smallcandidate; 
    int largecandidate; 
    if (nb < 0){ 
        return 0; 
    }else if (nb < 2){ 
        return nb; 
    }else{ 
        smallcandidate = ft_sqrt(nb >> 2) << 1; 
        largecandidate = smallcandidate + 1; 
        // 用除法判断，避免乘法溢出
        if (largecandidate > nb / largecandidate){ 
            return smallcandidate; 
        } else{ 
            return largecandidate; 
        } 
    } 
}

内容的提问来源于stack exchange，提问作者Gabe Spound