为何计算组合数时int64_t结果错误，而double结果正确？

先看你给出的代码：

using integer = int64_t; 
integer factorial(integer number) { 
    return number <= 0 ? 1 : number * factorial(number - 1); 
} 
integer binomial_coefficent(integer n, integer r) { 
    return factorial(n) / (factorial(r) * factorial(n - r)); 
} 
int main() { 
    using namespace std; 
    cout << binomial_coefficent(40, 20) << endl; 
    return 0; 
}

运行后输出0完全是整数溢出导致的未定义行为，咱们一步步拆解原因：

1. int64_t的容量撑不住40的阶乘 #

int64_t是64位有符号整数，它能表示的最大值是9223372036854775807（大概9×10¹⁸），但40的阶乘40!约等于8×10⁴⁷——这比int64_t的上限大了好几个数量级！

当你计算factorial(40)时，递归过程中早就超过了int64_t的最大值，触发了有符号整数溢出。根据C++标准，有符号整数溢出属于未定义行为，此时计算出来的阶乘值已经是一个混乱的负数或者无意义的数，后续用这个乱码值做除法，结果自然是0（或者其他错误值）。

2. 为什么double能得到正确结果？ #

double是64位浮点数，它的可表示范围极大（能到约1×10³⁰⁸），完全装得下40!的数值。而且你要计算的组合数C(40,20)是137846528820，这个数远小于2⁵³（约9×10¹⁵）——而double对小于2⁵³的整数可以做到精确表示。

虽然计算40!时double会损失一些精度，但最终通过除法得到的组合数刚好落在了double的精确表示范围内，所以能输出正确的近似值（1.37847e+11）。

3. 怎么用整数类型正确计算组合数？ #

如果想继续用int64_t得到精确结果，别先算超大的阶乘，换一种计算方式：利用组合数的递推公式，并且每一步先乘后除（保证每一步都是整数运算），同时利用对称性减少计算量（比如C(n,r)=C(n,n-r)，当r>n/2时，计算C(n,n-r)更高效）：

using integer = int64_t;
integer binomial_coefficient(integer n, integer r) {
    if (r > n - r) {
        r = n - r; // 取较小的那个r，减少循环次数
    }
    integer result = 1;
    for (integer i = 1; i <= r; ++i) {
        // 先乘再除，保证每一步结果都是整数，避免溢出
        result = result * (n - r + i) / i;
    }
    return result;
}

用这个函数计算binomial_coefficient(40,20)，会得到精确的137846528820，而且全程不会触发int64_t的溢出。

内容的提问来源于stack exchange，提问作者unknown.prince