Проверка переполнения в C

Question

Дайте нам

int a, b, c; // may be char or float, anything actually
c = a + b;

пусть тип int будет представлен 4 байтами. Допустим, a + b требует на 1 бит больше, чем 4 байта (то есть, скажем, результат равен 1 00 .... 0 (32 ноля, в двоичном виде)). Это приведет к C = 0, и я уверен, что микропроцессор компьютера установит какой-нибудь флаг переполнения. Есть ли встроенный метод, чтобы проверить это в C?

На самом деле я работаю над созданием числового типа длиной 1024 бита (например, int - это встроенный числовой тип длиной 32 бита). Я попытался сделать это, используя массивы типа unsigned char со 128 элементами. Мне также нужно определить операции сложения и вычитания для этих чисел. Я написал код для сложения, но у меня проблема с вычитанием. Мне не нужно беспокоиться о получении отрицательных результатов, поскольку способ, которым я буду вызывать функцию вычитания, всегда гарантирует, что результат вычитания всегда будет положительным, но для реализации функции вычитания мне нужно каким-то образом получить дополнение 2 к вычитаемому, которое Это мой собственный 1024-битный номер.

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

#define NUM_OF_WORDS 128

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

PS: Я не вижу, как загружать вложения на этом форуме, поэтому я направляю вас на другой сайт. Мой код можно найти там

нажмите для загрузки на этой странице

Кстати, я нашел это Я намереваюсь заменить INT_MAX by UCHAR_MAX, так как мои 1024-битные числа состоят из массива типов символов (8-битная переменная) Достаточно ли этой проверки для всех случаев?

Обновление:

Да, я работаю над криптографией.
Мне нужно реализовать процедуру умножения Монтгомери для 1024-битных целых чисел.
Я также подумывал об использовании библиотеки GMP, но не смог выяснить, как ее использовать.
Я просмотрел учебник и после нескольких небольших изменений смог создать файл проекта GMP в VC ++ 6, что привело к большому количеству файлов .obj, но теперь я не уверен, что с ними делать.
Тем не менее, было бы хорошо, если бы я мог писать свои собственные типы данных, поскольку это даст мне полный контроль над тем, как работают арифметические операции с моим пользовательским типом данных, и мне также нужно иметь возможность расширять его с 1024 бит до больших чисел в будущее.

Answer 1

Если вы добавляете числа без знака, вы можете сделать это

c = a+b;
if (c<a) {
  // you'll get here if and only if overflow has occurred
}

и вы даже можете обнаружить, что ваш компилятор достаточно умен, чтобы реализовать его, проверив флаг переполнения или переноса вместо дополнительного сравнения. Например, я только что передал это gcc -O3 -S:

unsigned int foo() {
  unsigned int x=g(), y=h();
  unsigned int z = x+y;
  return z<0 ? 0 : z;
}

и получил это для ключевого бита кода:

movl  $0,   %edx
addl  %ebx, %eax
cmovb %edx, %eax

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

Answer 2

Вопреки распространенному мнению, переполнение int приводит к неопределенному поведению. Это означает, что после переполнения a + b не имеет смысла использовать это значение (или делать что-либо еще, в этом отношении). Обтекание - это то, что происходит с большинством машин в случае переполнения, но они также могут взорваться.

Чтобы проверить, не произойдет ли переполнение int при добавлении двух неотрицательных целых чисел a и b, вы можете сделать следующее:

if (INT_MAX - b < a) {
        /* int overflow when evaluating a+b */
}

Это связано с тем, что если a + b > INT_MAX, то INT_MAX - b < a, но INT_MAX - b не может переполниться.

Вам придется обратить особое внимание на случай, когда b отрицателен, что оставлено в качестве упражнения для читателя;)

Относительно вашей реальной цели: 1024-разрядные числа страдают от тех же общих проблем, что и 32-разрядные числа. Может быть более перспективным выбрать совершенно другой подход, например, представление чисел в виде, скажем, связанных списков цифр с использованием очень большой базы B. Обычно B выбирается таким образом, что B = sqrt(INT_MAX), поэтому умножение цифр не переполняет тип int машины.

Таким образом, вы можете представлять произвольно большие числа, где «произвольно» означает «ограничено только объемом доступной основной памяти».

Answer 3

Информация, которая может быть полезна в этой теме:

1. Безопасное кодирование на C и C ++
2. Библиотека IntSafe

Answer 4

Если вы работаете с номерами без знака, то если a <= UINT_MAX, b <= UINT_MAX и a + b >= UINT_MAX, то c = (a + b) % UINT_MAX всегда будет меньше, чем a и b. И это единственный случай, когда это может произойти.

Таким образом, вы можете обнаружить переполнение таким образом.

int add_return_overflow(unsigned int a, unsigned int b, unsigned int* c) {
    *c = a + b;
    return *c < a && *c < b;
}

Answer 5

Просто xor MSB обоих операндов и результата. Результатом этой операции является флаг переполнения.

Но это не покажет вам, если результат правильный или нет. (это может быть правильным результатом даже при переполнении), например, 3 + (-1) равно переполнению 2.

Чтобы понять, что используя подписанную арифметику, вам нужно проверить, были ли обе оперды одинаковыми (xor of MSB).

Answer 6

Вы можете основывать решение на определенной функции языка C. Согласно спецификации, когда вы добавляете два беззнаковых целых числа, «значение результата совпадает с модулем 2 ^ n истинного результата» («Справочное руководство C - A» Харбисона и Стила). Это означает, что вы можете использовать несколько простых арифметических проверок для обнаружения переполнения:

#include <stdio.h>

int main() {
    unsigned int a, b, c;
    char *overflow;

    a = (unsigned int)-1;
    for (b = 0; b < 3; b++) {
        c = a + b;
        overflow = (a < b) ? "yes" : "no";
        printf("%u + %u = %u, %s overflow\n", a, b, c, overflow);
    }

    return 0;
}

Answer 7

Как только вы добавите 1 к INT_MAX, вы получите INT_MIN (то есть переполнение).
В C нет надежного способа проверки на переполнение, потому что все 32 байта используются для представления целого числа (а не состояния)флаг).Вы можете проверить только, чтобы увидеть, будет ли число, которое вы получаете, в пределах допустимого диапазона, как в вашей ссылке.

Вы получите ответы, предлагающие вам проверить if (c < a), однако обратите внимание, что вы можете переполнитьзначение a и / или b до точки, где их сложение образует число, большее, чем a (но все еще переполненное)