为什么 N!当 N>=34 时停止溢出 32 位输出变量？

Question

大数的变量溢出有限制吗？一本关于阶乘的 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("%u\n", fn);
        n++;
    }
}

注释行用于调试。

此代码打印从 n(1) 到 34 ('while(n!=34)') 的数字的阶乘，但如果将其增加到 36 之类的值，它只会在前 34 次输出后打印 0。我知道大部分输出都溢出了，我对这些大数字的控制很差。

但是，我想知道是什么限制导致了这些零的出现。

Answer 1

编辑，正如Eric所指出的，最大unsigned int值可能最容易显示为

printf("%u\n", UINT_MAX);

***** 上面的编辑 - 下面的原始答案 *****

fn 属于 unsigned int 类型，将具有最大值。

要找出一个unsigned int的最大值尝试

printf("%d",sizeof(unsigned int));

此命令将告诉您内存中分配给 unsigned int 的字节数 - 如果该数字是 n，则最大的 unsigned int 值将是 2^{8n}-1 - 或二的 8n 次方然后减去 1.

如果你想要更大的数字，那么你可以测试其他类型，比如 long。

如果您乐于获得近似值，那么您可以使用类型 double，它会比任何 int 类型高得多。

Answer 2

没有限制，溢出永远不会停止。
只是当n到达34时，fn溢出到数字0.

那么下一个数是35 * 0，下一个是36 * 35 * 0，依此类推。

没什么神秘的。

Answer 3

unsigned int、UINT_MAX = 4294967295 类型变量的最大值。在此过程中，找到 12! 后得到 overflowed。为了处理溢出，C 环绕也称为 modulo wrapping 的值。例如，

unsigned int x = 4294967295;
x += 1;
printf("%u", x)

输出：0

unsigned int x = 4294967295;
x += 2;
printf("%u", x)

输出：1

这意味着每当发生溢出时，C 环绕该值并且它永远不会溢出！

但是在这种情况下，同时找到了35！在此过程中的某处，模数变为零。因此，在 34! 之后总是 zero。所以，零不会出现溢出。

要找到 n! 所需的位，请使用公式 floor(log(n!))+1。然后使用所需的数据类型。

Answer 4

你抱怨

N! stops overflowing the 32 bits output variable when N>=34

表示在34!之后，结果一直保持为0。

嗯，答案是它不会停止溢出。发生的情况是显示的值，即从 N=34 开始的除法 N! / 2^32 的余数变为 0，并且永远不会改变。

为了理解它是如何发生的，让我们从一个使用十进制数的例子开始。我们将显示 N! 的结果。使用只有两位数字的显示器：

Factorial	Actual result	Displayed result	Notes
1!	1	01
2!	2	02
3!	6	06
4!	24	24
5!	120	20	Overflow!
6!	720	20	Overflow!
7!	5040	40	Overflow!
8!	40320	20	Overflow!
9!	362880	80	Overflow!
10!	3628800	00	Overflow and the shown value is 00!
11!	39916800	00	Overflow and the shown value is still 00!
12!	479001600	00	Overflow and the shown value is still 00!
..	..	00	The shown value will be 00 forever

如您所见，显示在 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）表示来完成相同的推理，但受 unsigned int 大小的限制。当结果开始具有 B^N = 2^32.

的公因数时，我们将达到全 0 条件

什么时候结果会变成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。

为什么 N!当 N>=34 时停止溢出 32 位输出变量？

Why does N! stop overflowing the 32 bits output variable when N>=34?

c

factorial