Перехват целочисленного переполнения в рекурсивной функции [C] - PullRequest
Новая
       60

Перехват целочисленного переполнения в рекурсивной функции [C]

4 голосов
/ 24 февраля 2012

ОБНОВЛЕНИЕ:

Спасибо за полезные комментарии и советы.Используя то, что вы, ребята, сказали, вот что я придумал: 

#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);, но это завершает всю программу или только функцию?

ORIGINAL:

Ваша функция должна использовать целочисленную арифметику, чтобы убедиться в точности результатов, а также обнаруживать любые целочисленные переполнения, вызванные превышениеммаксимально допустимые значения.

Я пытаюсь поймать целочисленное переполнение при вычислении биномиальных коэффициентов.Хотя простая концепция меня отталкивает, это то, что это не однократное дополнение, это рекурсивный алгоритм, который постоянно выполняет суммирование.

Это функция: 

// 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

    }
}

В соответствии с этой логикой я предполагаю, что перехват должен быть в операторе рекурсивного вызова.Что-то вроде:

if(binom(n-1, k-1) + binom(n-1,k)) causes overflow, return error, else proceed with binom(n-1, k-1) + binom(n-1,k)

Ответы [ 3 ]

3 голосов
/ 24 февраля 2012

Переполнение со знаком - неопределенное поведение, вы должны проверить переполнение, прежде чем оно может произойти. 

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 также будет переполнена.

0 голосов
/ 24 февраля 2012

Несколько предложений:

1) Вы используете целое число со знаком; если вы работаете со строго положительными величинами, вам, вероятно, следует использовать unsigned int или unsigned long long. В случае со знаком int, когда происходит арифметическое переполнение, оно переполняется до наибольшего возможного отрицательного числа

2) Компилятор определит символ препроцессора в соответствии с INT_MAX; Вы, вероятно, можете использовать его, например, примерно так: 

#inlcude <stdtypes.h>

uint32_t binom( uint32_t n, uint32_t k ){
  // (...)
  } else {
    int32_t   A = binom( n-1, k-1 )
            , B = binom( n-1, k );
    if( (double)A + (double)B > INT_MAX ){
      // error condition
    } else {
      retval = A+B;
    }
  }

  return retval;
}
0 голосов
/ 24 февраля 2012

сделать что-то вроде: 

long res=(long)binom(n - 1, k - 1) + binom(n - 1, k);
if (res>INT_MAX) {
 printf("int overflow\n");
 exit(1);
}
return (int)res;

(Предполагается, что long длиннее int в вашей системе. Если нет, используйте более широкий тип)

Редактировать: если вы не хотите exit при ошибке, вы должны решить значение (например, -1), чтобы представить ошибку. Кроме того, лучше (и корректор) использовать unsigned вместо long: 

int a=binom(n - 1, k - 1),b=binom(n - 1, k);
if (a<0 || b<0 || (unsigned)a+(unsigned)b>INT_MAX) return -1;
return a+b;
...