由阶乘问题引发的关于数据溢出的讨论

为了对进程递归有更深入的理解，设计了一个计算输入数阶乘的小程序，该程序的最初版本如下（V1.0）：

//version: 1.0
#include <stdio.h>
#include <stdlib.h>

long factorial(int n)
{
	if(n == 0)
		return 1;
	if(n < 0)
	{
		printf("error\n");
		return -1;
	}
	else
	return n * factorial(n - 1);
}

int main(int argc, char** argv)
{
	int n = 0;

	if(argc != 2)
	{
		printf("Input format should be: ./factorial num\n");
		return 0;
	}

	n = atoi(argv[1]);

	if(factorial(n) > 0)
		printf("%d! = %ld\n", n, factorial(n));

	return 1;
}

V1.0看似没有问题，但在实际运行时出现了明显的错误。在计算至21!时，没有输出值。进而计算21之后的整数的阶乘，发现输出结果时有时无。

于是使用GDB调试逐步寻找，发现在计算21! 时，得到的factorial(21)值为负数，在第30行的if判断中得到假，进而跳过输出步骤。

根据调试得到的信息，可推测是由于数据溢出所致。用于记录阶乘结果的数据类型使用的是long型。在long型数据的比特表示中，最高位为0则为正数，为1则为负数，后面的63位用于记录数据的绝对值。在该程序执行过程中，由于阶乘增长速度很快，在计算至21!就已将long型数据的后63位占满，溢出至符号表示位。当factorial(n)的符号位为1时，值为负，所以根据算法没有输出。

根据已知错误的原因，对V1.0进行更改。将记录factorial(n)的数据类型改为unsigned long型（64位全部记录数字的值，没有正负区别），并删去判断factorial(n)正负的步骤。具体代码修改如下：

1. 第5行 long factorial(int n) 更改为 unsigned long factorial(int n)

2. 删去第30行 if(factorial(n) > 0)判断，直接输出结果

3. 原第31行printf中的 %ld 更改为 %lu

修改得到V2.0版本，解决了V1.0中遇到的问题，但在进一步验证中出现了非常特殊的情况，当计算大于等于66的整数的阶乘时，输出值恒为0。

输出值为0表明factorial(66)的数据中64位全部为0。于是提出推测：由于阶乘结果过大，数据溢出过多，导致64位表示中末尾的0的数量不断增加。在计算至66!时，刚好累加至64个0，导致输出结果为0。根据该程序阶乘的算法，在计算66之后的整数阶乘时会使用到66! = 0的结果，导致其输出结果全部为0.

为了验证上述推测，再次修改程序，在计算阶乘时将小于该数的正整数的阶乘依次输出，并且在十进制的表示结果后添加64位的二进制表示来展示factorial(n)的内部数据表示。编写一个函数tobin(unsigned long x)来实现64位二进制输出。用于测试的新文件FactorialTest如下：

//test version
#include <stdio.h>
#include <stdlib.h>

unsigned long factorial(int n)
{
	if(n == 0)
		return 1;
	if(n < 0)
	{
		printf("error\n");
		return -1;
	}
	else
		return n * factorial(n - 1);
}

void tobin(unsigned long x)
{
	int i;
	char bin[64];
	for(i = 63; i >= 0; i--)
	{
		bin[i] = x & 1;
		x = x >> 1;
	}
	for(i = 0; i < 64; i++)
		printf("%d", bin[i]);
	printf("\n\n");
}

int main(int argc, char** argv)
{
	int n = 0;
	if(argc != 2)
	{
		printf("Input format should be: ./Filename num\n");
return 0;
	}

	n = atoi(argv[1]);

	for(int i = 1; i <= n; i++)
	{
		printf("%d! = %lu\n", i, factorial(i));
		tobin(factorial(i));
	}
	return 1;
}

运行该文件，输入67进行测试，得到如下结果：

1! = 1
0000000000000000000000000000000000000000000000000000000000000001

2! = 2
0000000000000000000000000000000000000000000000000000000000000010

3! = 6
0000000000000000000000000000000000000000000000000000000000000110

4! = 24
0000000000000000000000000000000000000000000000000000000000011000

5! = 120
0000000000000000000000000000000000000000000000000000000001111000

6! = 720
0000000000000000000000000000000000000000000000000000001011010000

7! = 5040
0000000000000000000000000000000000000000000000000001001110110000

8! = 40320
0000000000000000000000000000000000000000000000001001110110000000

9! = 362880
0000000000000000000000000000000000000000000001011000100110000000

10! = 3628800
0000000000000000000000000000000000000000001101110101111100000000

11! = 39916800
0000000000000000000000000000000000000010011000010001010100000000

12! = 479001600
0000000000000000000000000000000000011100100011001111110000000000

13! = 6227020800
0000000000000000000000000000000101110011001010001100110000000000

14! = 87178291200
0000000000000000000000000001010001001100001110110010100000000000

15! = 1307674368000
0000000000000000000000010011000001110111011101110101100000000000

16! = 20922789888000
0000000000000000000100110000011101110111011101011000000000000000

17! = 355687428096000
0000000000000001010000110111111011101110110011011000000000000000

18! = 6402373705728000
0000000000010110101111101110110011001010011100110000000000000000

19! = 121645100408832000
0000000110110000001010111001001100000110100010010000000000000000

20! = 2432902008176640000
0010000111000011011001110111110010000010101101000000000000000000

21! = 14197454024290336768
1100010100000111011111010011011010111000110001000000000000000000

22! = 17196083355034583040
1110111010100100110000101011001111100000110110000000000000000000

23! = 8128291617894825984
0111000011001101011111100010100100110011011010000000000000000000

24! = 10611558092380307456
1001001101000011110100111101110011010001110000000000000000000000

25! = 7034535277573963776
0110000110011111101100001001000001111011110000000000000000000000

26! = 16877220553537093632
1110101000110111111011101010110010010001100000000000000000000000

27! = 12963097176472289280
1011001111100110001011000011001101011000100000000000000000000000

28! = 12478583540742619136
1010110100101100110101011001110110101110000000000000000000000000

29! = 11390785281054474240
1001111000010100001100101101110010110110000000000000000000000000

30! = 9682165104862298112
1000011001011101111101011101110101010100000000000000000000000000

31! = 4999213071378415616
0100010101100000110001011100110100101100000000000000000000000000

32! = 12400865694432886784
1010110000011000101110011010010110000000000000000000000000000000

33! = 3400198294675128320
0010111100101111111011100101010110000000000000000000000000000000

34! = 4926277576697053184
0100010001011101101001110101101100000000000000000000000000000000

35! = 6399018521010896896
0101100011001101111000010111000100000000000000000000000000000000

36! = 9003737871877668864
0111110011110011101100111110010000000000000000000000000000000000

37! = 1096907932701818880
0000111100111000111111111111010000000000000000000000000000000000

38! = 4789013295250014208
0100001001110101111111100011100000000000000000000000000000000000

39! = 2304077777655037952
0001111111111001101110101000100000000000000000000000000000000000

40! = 18376134811363311616
1111111100000101001001010100000000000000000000000000000000000000

41! = 15551764317513711616
1101011111010010111101110100000000000000000000000000000000000000

42! = 7538058755741581312
0110100010011100100100001000000000000000000000000000000000000000

43! = 10541877243825618944
1001001001001100010001011000000000000000000000000000000000000000

44! = 2673996885588443136
0010010100011011111100100000000000000000000000000000000000000000

45! = 9649395409222631424
1000010111101001100010100000000000000000000000000000000000000000

46! = 1150331055211806720
0000111111110110110011000000000000000000000000000000000000000000

47! = 17172071447535812608
1110111001001111011101000000000000000000000000000000000000000000

48! = 12602690238498734080
1010111011100101110000000000000000000000000000000000000000000000

49! = 8789267254022766592
0111100111111001110000000000000000000000000000000000000000000000

50! = 15188249005818642432
1101001011000111100000000000000000000000000000000000000000000000

51! = 18284192274659147776
1111110110111110100000000000000000000000000000000000000000000000

52! = 9994050523088551936
1000101010110010000000000000000000000000000000000000000000000000

53! = 13175843659825807360
1011011011011010000000000000000000000000000000000000000000000000

54! = 10519282829630636032
1001000111111100000000000000000000000000000000000000000000000000

55! = 6711489344688881664
0101110100100100000000000000000000000000000000000000000000000000

56! = 6908521828386340864
0101111111100000000000000000000000000000000000000000000000000000

57! = 6404118670120845312
0101100011100000000000000000000000000000000000000000000000000000

58! = 2504001392817995776
0010001011000000000000000000000000000000000000000000000000000000

59! = 162129586585337856
0000001001000000000000000000000000000000000000000000000000000000

60! = 9727775195120271360
1000011100000000000000000000000000000000000000000000000000000000

61! = 3098476543630901248
0010101100000000000000000000000000000000000000000000000000000000

62! = 7638104968020361216
0110101000000000000000000000000000000000000000000000000000000000

63! = 1585267068834414592
0001011000000000000000000000000000000000000000000000000000000000

64! = 9223372036854775808
1000000000000000000000000000000000000000000000000000000000000000

65! = 9223372036854775808
1000000000000000000000000000000000000000000000000000000000000000

66! = 0
0000000000000000000000000000000000000000000000000000000000000000

67! = 0
0000000000000000000000000000000000000000000000000000000000000000

通过该结果可以直观地看出数据的溢出量越来越大，末尾0的个数越来越多，最终在66!时全部归零。可见之前的推测正确，确实是由于阶乘结果过大，数据溢出过多，导致64位表示中末尾的0的数量不断增加。在计算至66!时，刚好累加至64个0，导致输出结果为0。

观察结果队列还可以发现，其中还有如下两个错误同样是由于数据溢出导致的：

1．在计算至20!时，得到结果20! = 2432902008176640000。由阶乘的定义可知，21!= 20! * 21。20!的值后四位为0，所以当其与21相乘时应该得到后4位同样为0的十进制数。但该程序中21!的计算结果是14197454024290336768。

2．根据阶乘的定义，阶乘的结果是单调递增的，但队列中有些结果却比先前还要小甚至相等，比如23! < 22!，59! < 58!，64! = 65!。

由FactorialTest1得到的数据可知：64位unsigned long型的表示范围是0 ~ 18446744073709551615，可表示的阶乘结果最高到20!，从21!开始发生数据溢出，持续到66!因数据溢出导致归零，之后的阶乘结果全部显示为0。

根据前两个版本的错误和测试结果，改进程序，提出最终版本如下：

//last version
#include <stdio.h>
#include <stdlib.h>

unsigned long factorial(int n)
{
	if(n == 0)
		return 1;
	if(n < 0 || n > 20)
	{
		printf("Input number should between 0 and 20\n");
		return 0;
	}
	else
		return n * factorial(n - 1);
}

int main(int argc, char** argv)
{
	int n = 0;
	unsigned long fact = 0;

	if(argc != 2)
	{
		printf("Input format should be: ./Filename num\n");
		return 0;
	}

	n = atoi(argv[1]);
	fact = factorial(n);

	if(fact > 0)
		printf("%d! = %lu\n", n, fact);

	return 1;
}

总结：该程序的计算范围为0 ~ 20，要计算更大整数的阶乘需要另外的方法实现，这里不再讨论。编程过程中要时刻注意数据的表示范围，防止数据溢出的发生。

原文链接：https://blog.csdn.net/ClarkCC/article/details/104029187

你可能也喜欢