在递归函数中捕获整数溢出 [C]

Question

更新:

感谢您提供有用的意见和建议。使用你们所说的，这就是我想出的:

#include <limits.h>
  ...
  else {
     int a = binom(n - 1, k - 1);
     int b = binom(n - 1, k);
     if(a > 0) {
         if (b > INT_MAX - a) {          // case 1: integer overflow
             printf("int overflow\n");
             return;
         }
     }
     else if (b < INT_MIN - a) {         // case 2: integer overflow
         printf("int overflow\n");
         return;
     }
     int c = a + b;
     return c;
}

我还有一个问题。在上面的代码中，当我发现整数溢出时，我没有返回值——它只是 return;。

下面的评论之一建议return -1;，但是考虑到 -1 仍然是一个有效的整数，这是行不通的，对吗？

我不确定该怎么做，因为我的函数的返回类型是 int。 return; 有效还是有更好的方法？还建议使用 exit(1);，但这会退出整个程序还是仅退出函数？

---

原文:

您的函数应该使用整数运算来确保结果准确且还可以检测由超过最大允许值引起的任何整数溢出。

我在计算二项式系数时试图捕获整数溢出。虽然这是一个简单的概念，但让我失望的是这不仅仅是一次性加法，它是一种不断执行求和的递归算法。

这是函数:

// recursive function to calculate binomial coefficients
int binom(int n, int k){
    if(k == 0){         // base case
         return 1;
    }
    else if (n == 0){
         return 0;
    }
    else{
         return binom(n - 1, k - 1) + binom(n - 1, k);  // recursive call

    }
}

根据这个逻辑，我假设 catch 应该在递归调用语句中。像这样的东西:

if(binom(n-1, k-1) + binom(n-1,k)) 导致溢出，返回错误，否则继续 binom(n-1, k-1) + binom( n-1,k)

Answer 1

有符号溢出是未定义的行为，您必须在溢出发生之前对其进行检查。

int a, b;
int c;

...

/* Compute a + b and store the result in c */

if (a > 0) {
    if (b > INT_MAX - a) {
        // a + b overflows (i.e., would be > INT_MAX)
    }
} else if (b < INT_MIN - a) {
        // a + b overflows (i.e., would be < INT_MIN)
}

c = a + b;

所以对于递归函数:

a = binom(n - 1, k - 1);
b = binom(n - 1, k);

// if no overflow
c = a + b;

return c;

在您的示例中，您还必须检查 n 和 k 不是 == INT_MIN 否则 - 1操作也会溢出。