c - 如何确定程序可以使用 unsigned long long 计算阶乘的最大值？

Question

如何在 C 中编写适当的算法来确定程序可以使用 unsigned long long int 计算阶乘的最大值？

我的例子不能正常工作。使用 Linux/64 位和 GCC，它给了我 65 次迭代。

#include <stdio.h>

int main() {
    unsigned long long int num, i;
    unsigned long long int factorial = 1;
    num = 1;
    for (i = 1; i <= num; i++) {
        factorial = factorial * i;
        num++;
        if (factorial <= 0) {
           printf("\nMaximum number is: %d\n", i - 1);
           break;
        }
    }
}

Answer 1

您的程序无法正常运行，因为:

• factorial 总是 >= 0 因为它有一个无符号类型。程序停止的唯一原因是 factorial 在您乘以 2 或 2 的倍数足够多的次数后最终变为 0。
• 您无法通过测试结果值来可靠地检测溢出:无符号算术以值位数的 2 为模执行，因此您可以将结果与前一个阶乘进行比较，如果较小则中断。但是请注意，有符号算术溢出实际上具有未定义的行为，因此测试结果是否定的总是错误的。

更可靠的方法是在执行乘法之前检查溢出:

#include <limits.h>
#include <stdio.h>

int main(void) {
    unsigned long long int i, factorial;
    for (i = factorial = 1; factorial <= ULLONG_MAX / i; i++) {
        factorial = factorial * i;
    }
    printf("\nMaximum number is: %llu! = %llu\n", i - 1, factorial);
    return 0;
}

输出:

Maximum number is: 20! = 2432902008176640000