Целочисленное деление переполнения

Эта проблема

Я думал о целочисленных (тип int) переполнениях, и мне пришло в голову, что деление может переполняться.

Пример: на моей текущей платформе у меня

INT_MIN == -INT_MAX - 1

и поэтому

INT_MIN < -INT_MAX

и поэтому

INT_MIN / -1 > -INT_MAX / -1

и поэтому

INT_MIN / -1 > INT_MAX.

Следовательно, деление (INT_MIN / -1) действительно переполняется.

Вопросы

Итак, у меня два вопроса:

  1. Какой (кросс-платформенный) код C можно было написать, чтобы предотвратить переполнение деления (для типа (подписанного) int)?

  2. Какие гарантии (в стандарте C или C ++) могут помочь при разработке кода?

Например, если стандарт гарантирует, что у нас есть либо

INT_MIN == -INT_MAX - 1

or

INT_MIN == -INT_MAX,

то появляется следующий код для предотвращения переполнения.

#include <limits.h>

/*
      Try to divide integer op1 by op2.
      Return
        0 (success) or
        1 (possibly overflow prevented).
      In case of success, write the quotient to res.
*/

int safe_int_div(int * res, int op1, int op2) {

  /*   assert(res != NULL);   */
  /*   assert(op2 != 0);      */

  if ( op1 == INT_MIN && op2 == -1 )  {
    return 1;
  }
  *res = op1 / op2;
  return 0;
}

c c++ cross-platform standards integer-overflow
person Anon    schedule 22.05.2015    source источник
comment
ОТ: Согласно соглашению, вы хотите вернуть -1 при ошибке.   -  person alk    schedule 22.05.2015
comment
@ Анон. Вы решите еще одну проблему с разделением, если добавите еще что-то вроде if (!op2) return 2 :)   -  person Sir Jo Black    schedule 22.05.2015
comment
это как-то связано с тем, как компьютер выполняет аппаратное разделение   -  person ThunderWiring    schedule 24.05.2015

Ответы (2)


arrow_upward
14
arrow_downward

Какие гарантии (в стандарте C или C ++) могут помочь при разработке кода?

C определяет целочисленное представление со знаком как использование одной из трех форм: знак и величина, дополнение до двух или дополнение до единиц. Учитывая эти формы, только деление на 0 и двойное дополнительное деление INT_MIN/-1 могут быть переполнены.

Какой (кросс-платформенный) код C можно было написать, чтобы предотвратить переполнение деления (для типа (подписанного) int)?

int safe_int_div(int * res, int op1, int op2) {
  if (op2 == 0) {
    return 1;
  }
  // 2's complement detection
  #if (INT_MIN != -INT_MAX) 
    if (op1 == INT_MIN && op2 == -1)  {
      return 1;
    }
  #endif
  *res = op1 / op2;
  return 0;
}
person chux - Reinstate Monica    schedule 22.05.2015
comment
Стоит упомянуть, что возможно, что HW (архитектура ЦП, FPGA или некоторый RTL) остановится, если вы попытаетесь разделить INT_MIN/-1 без вышеуказанных мер защиты. - person 0x90; 18.07.2016
comment
Или без надлежащей обработки исключения подчеркнутым ядром / прошивкой. - person 0x90; 19.07.2016

arrow_upward
0
arrow_downward

1) Как и для любой другой операции в C, приложение должно гарантировать, что:

  • тип, используемый для самого расчета, достаточно большой, и
  • тип переменной, в которой сохраняется результат, достаточно велик.

Способ гарантировать это - установить ограничения размера каждого операнда перед операцией. Какие пределы подходят, зависит от алгоритма и назначения переменных.

2) Если вы используете stdint.h стандарта C, вы получаете гарантии того, насколько велики переменные, переносимость. Никогда не используйте int при написании переносимого кода.

Что касается случая написания подпрограммы безопасного деления, то в качестве параметров потребуется 32-битные целые числа, затем выполнить вычисление для 64-битных целых чисел и вернуть результат как 32-битное целое число.

#include <stdint.h>
#include <stdbool.h>

/*
      Try to divide integer op1 by op2.
      Return
        true (success) or
        false (possibly overflow prevented).
      In case of success, write the quotient to res.
      In case of failure, res remains untouched.
*/

bool safe_int_div (int32_t* res, int32_t op1, int32_t op2) {

  if(op2 == 0)
    return false;

  int64_t res64 = (int64_t)op1 / (int64_t)op2;

  if(res64 > INT32_MAX || res64 < INT32_MIN)
    return false;

  *res = (int32_t)res64_t;

  return true;
}

Если требуется дополнительная информация о том, почему разделение не удалось, замените bool на enum.

person Lundin    schedule 22.05.2015