累积和的溢出
累积和的溢出
假设我想要计算1+11+111+...重复相加n次的结果。
很明显,从某个n值开始,累加和可能会溢出。
假设我使用下面这个非常简单的函数来计算上述的和:
int calcSum(int num) { int sum = 0, sequnt = 1, i; for (i = 0; i < num; i++) { sum += sequnt; sequnt = (sequnt * 10) + 1; } return sum; }
我想在这个函数中添加一个溢出检查。
我已经尝试在这里获取一些帮助 How to check if a number overflows an 'int',但我必须承认这让我感到困惑,而且我在实现这个任务时仍然遇到一些困难。
任何帮助将不胜感激。
整理如下:
累积和溢出问题的原因:在给定的代码中,当累积和超过INT_MAX时,会发生溢出。此外,由于变量sequnt是通过乘以10并加1来更新的,当sequnt超过INT_MAX/10时,也会发生溢出。
解决方法:可以通过在累积和超过INT_MAX之前检查累积和的值来解决溢出问题。如果累积和超过INT_MAX,则退出程序。同样,可以通过在sequnt更新之前检查sequnt的值是否超过INT_MAX/10来解决溢出问题。如果sequnt超过INT_MAX/10,则退出程序。
以下是修改后的代码:
#includeint calcSum(int num) { int sum = 0, sequnt = 1, i; for (i = 0; i < num; i++) { if (INT_MAX - sequnt < sum) exit(1); // 溢出检查 sum += sequnt; if (INT_MAX/10 <= sequnt) exit(1); // 溢出检查 sequnt *= 10; sequnt++; } return sum; }
上述代码中的解决方法可以确保累积和和sequnt不会发生溢出。
累积和溢出(overflow of cummulative sum)的问题是指在计算累积和时可能发生的溢出错误。溢出错误可能发生在两个加法运算或乘法运算中的任意一个。为了解决这个问题,代码中使用了一个安全的溢出检查器(overflow checker)函数来检查每个加法或乘法运算的结果是否会导致溢出。
在代码中,使用了<limits.h>
头文件中的常量来指导范围检查。为了检查加法是否会导致溢出,使用了is_undefined_add()
函数。该函数接受两个整数参数a
和b
,如果a
为负数,则判断b
是否小于INT_MIN - a
;如果a
为非负数,则判断b
是否大于INT_MAX - a
。类似地,为了检查乘法是否会导致溢出,使用了is_undefined_mult()
函数。该函数接受两个整数参数a
和b
,根据a
和b
的正负情况进行不同的判断。
在calcSum()
函数中,使用了一个循环来计算累积和。在每次循环中,首先调用is_undefined_add()
函数来检查累积和与当前序列值相加的结果是否会导致溢出。如果检测到溢出,将进行相应的溢出处理。然后,将当前序列值与累积和相加,并使用is_undefined_mult()
函数检查序列值乘以10的结果是否会溢出。再然后,将序列值加1,并使用is_undefined_add()
函数检查加1后的结果是否会溢出。最后,返回累积和。
is_undefined_add()
和is_undefined_mult()
函数适用于所有int a, int b
的组合,可以有效地检查加法和乘法运算是否会导致溢出。通过这些溢出检查器函数,可以避免累积和溢出的问题。
溢出累加的问题通常出现在使用带符号的二进制补码整数时。如果要解决这个问题,可以采取以下方法:
1. 首先,要确保使用的是二进制补码的有符号整数。可以根据以下规则进行检查: 两个正数相加的结果必须是正数,两个负数相加的结果必须是负数。在一个求和中,不可能出现两次溢出,所以如果要进行正数相加,当结果第一次为负数时,就会发生溢出。
2. 无论哪种情况,如果希望代码具有可移植性,可以参考以下建议:
#include... if ((a > 0 && b > 0 && MAX_INT - a > b) || (a < 0 && b < 0 && MIN_INT - a < b)) { /* 溢出 a + b 将发生 */ ... }
3. 如果操作数的符号不同,那么 `a + b
` 不可能比 `a
` 或 `b
` 的绝对值大,因此溢出是不可能发生的。
4. 对于无符号整数,可以采用类似的方法(虽然只需要进行一半的测试,因为操作数只能为正数)。这种情况下,第一种方法始终有效(因为标准规定,无符号加法被认为是模2^n
的求和,其中n
是位大小),此时可以进行求和,然后检查结果是否小于任何一个操作数(如果两个操作数都为正数,则求和必须大于或等于任何一个操作数):
unsigned a, b; ... unsigned sum = a + b; if (sum < a || sum < b) { /* 溢出 a + b 已经发生 */ ... }
此外,还需要检查整数乘法溢出。如果要计算 `a` 和 `b` 的乘积,那么 `a*b` 可能会溢出。但这次问题更复杂,因为溢出可能发生多次,而且不能事后处理。在这种情况下,乘积会根据操作数的符号进行加法运算,如果两个符号相同,乘积将为正数,溢出将发生:
if (MAX_INT/b < a) { /* 溢出 */ }
如果符号不同,乘积应为负数,然后:
if (MIN_INT/b < a) { /* 溢出 */ }
如果其中一个操作数为0,则乘法不会溢出,因为结果为0。
需要注意的是,“如果要进行正数相加,当结果第一次为负数时,就会发生溢出”这种说法可能在某些平台上是正确的,但从标准的角度来看是错误的。当发生溢出时,从标准的角度来看,行为是不确定的,并且使用结果是没有意义的。
很抱歉,我之前的回答有误,我可以确定我在某个地方看到过这个说法。现在已经对回答进行了编辑。