为什么N！当N>=34时停止溢出32位输出变量？
大数字的变量溢出是否有任何限制？一本关于阶乘的 C 书中有一个练习。
我的代码：
#include <stdio.h>
int main(void) {
unsigned int n, fn, counter;
//puts("enter nonnegative int");
//scanf("%u", &n);
n = 1;
while (n != 34) {
fn = n;
counter = n - 1;
while (counter > 0) {
fn *= counter;
counter--;
}
printf("%un", fn);
n++;
}
}
注释行用于调试。
此代码打印从 n(1) 到 34 ( 'while(n!=34)')的数字的阶乘，但如果将其增加到 36 之类的值，它将在前 34 个输出后仅打印 0。我知道大部分输出都溢出了，并且对这些大数字的控制非常糟糕。
但是，我想知道导致这些零发生的限制是什么。
回答
你抱怨说
N!停止溢出 32 位输出变量时N>=34
这意味着，在 之后34!，结果保持为 0。
嗯，答案是它不会停止溢出。发生的情况是显示的值，即N! / 2^32从 N=34 开始的除法的余数变为 0，并且永远不会改变。
为了理解它是如何发生的，让我们从一个使用十进制数的例子开始。我们将显示 N 的结果！使用只有两位数字的显示器：
| 阶乘 | 实际结果 | 显示结果 | 笔记 |
|---|---|---|---|
| 1！ | 1 | 01 | |
| 2！ | 2 | 02 | |
| 3！ | 6 | 06 | |
| 4！ | 24 | 24 | |
| 5！ | 120 | 20 | 溢出！ |
| 6！ | 720 | 20 | 溢出！ |
| 7！ | 5040 | 40 | 溢出！ |
| 8！ | 40320 | 20 | 溢出！ |
| 9！ | 362880 | 80 | 溢出！ |
| 10！ | 3628800 | 00 | 溢出，显示值为00！ |
| 11！ | 39916800 | 00 | 溢出，显示值还是00！ |
| 12！ | 479001600 | 00 | 溢出，显示值还是00！ |
| .. | .. | 00 | 显示的值将永远为 00 |
如您所见，显示溢出的5!位置我们还可以注意到结果是 的倍数5*2=10。由于显而易见的原因所有后续的结果将是多5*2=10那么他们将有一个尾随0。
但是，当我们到达10!时一个特殊的条件：结果变成的倍数(5^2)*(2^2)=10^2=100因此，无论是我们事后进行的显示值将始终乘法是00。
请记住此信息：当结果开始具有 B^N 的公因数时，我们达到了全 0 条件，其中
B是表示的基础 (10)N是显示的位数 (2)
所以，在这种情况下， 10^2.
使用二进制（base-2）表示可以完成相同的推理，受 a 的大小限制unsigned int。当结果开始具有 的公因数时，我们将达到全 0 条件B^N = 2^32。
结果什么时候会变成 的倍数2^32？让我们计算引入 2 的幂的乘法：
2!将添加因子 2（总共 2^1）4!将增加一个因子 2^2（总共 2^3）6!将添加因子 2（总共 2^4）8!将增加一个因子 2^3（总共 2^7）10!将添加因子 2（总共 2^8）12!将增加一个因子 2^2（总共 2^10）14!将增加一个因子 2（总共 2^11）16!将增加一个因子 2^4（总共 2^15）18!将添加因子 2（总共 2^16）20!将增加一个因子 2^2（总共 2^18）22!将增加一个因子 2（总共 2^19）24!将增加一个因子 2^3（总共 2^22）26!将添加一个因子 2（总共 2^23）28!将增加一个因子 2^2（总共 2^25）30!将增加一个因子 2（总共 2^26）32!将增加一个因子 2^5（总共 2^31）34!将添加一个因子 2（总共 2^32）
从现在开始，阶乘将始终是 的倍数2^32，因此显示的结果， 的余数N! / 2^32将始终为 0。