为何10位整数运算溢出而18位整数正常？C++生日悖论计算问题

问题描述 #

我用C++实现生日悖论的扩展计算（数学作业），代码如下：

#include <bits/stdc++.h>
using namespace std;
unsigned long long findPeople(double p){
   return ceil(sqrt(2*143545666897673985*log(1/(1-p))));
}
int main(){
   printf("%lld",findPeople(0.5));
}

当使用18位数值143545666897673985时程序运行正常，但换成10位数值1842350265时，编译器抛出警告：

warning: integer overflow in expression of type ‘int’ results in ‘-610266766’ [-Woverflow]
    4 |    return ceil(sqrt(2*1842350265*log(1/(1-p))));
      |                     ~^~~~~~~~~~~

我试过改用unsigned long long类型，但问题没解决，求帮助。

原因分析 #

问题出在整数运算的类型提升规则上：

• 18位的143545666897673985远超过32位int的最大值（2147483647），编译器会自动把它识别为unsigned long long类型。此时乘法2*143545666897673985中，2会被提升为unsigned long long，整个运算在64位无符号整型下进行，不会溢出。
• 10位的1842350265本身小于32位int的最大值，所以编译器把它和2都当作int类型处理。但两者相乘的结果3684700530超过了32位int的范围，触发整数溢出，这就是警告的来源。你之前尝试用unsigned long long类型，但没修改乘法表达式里的操作数类型，所以没用。

解决方案 #

只要把乘法表达式中的任意一个操作数显式声明为unsigned long long，就能让整个运算以64位整型进行，避免溢出。修改后的代码如下：

#include <bits/stdc++.h>
using namespace std;
unsigned long long findPeople(double p){
   // 把2改成2ULL，显式指定为unsigned long long类型
   return ceil(sqrt(2ULL * 1842350265 * log(1/(1-p))));
}
int main(){
   printf("%lld",findPeople(0.5));
}

或者也可以给1842350265加上ULL后缀，效果一样：

return ceil(sqrt(2 * 1842350265ULL * log(1/(1-p))));

内容的提问来源于stack exchange，提问作者Mapk 46