Переполнение целых чисел
Переполнение целых чисел
Вы уже знаете, что при сложении целых может происходить переполнение. Загвоздка в том, что компьютер не выдаёт предупреждения при переполнении: программа продолжит работать с неверными данными. Более того, поведение при переполнении определено только для целых без знака.
Переполнение может привести к серьёзным проблемам: обнулению и потере данных, возможным эксплойтам, трудноуловимым ошибкам, которые будут накапливаться с течением времени.
Рассмотрим несколько приёмов отслеживания переполнения целых со знаком и переполнения целых без знака.
1. Предварительная проверка данных. Мы знаем, из файла limits.h, максимальное и минимальное значение для чисел типа int. Если оба числа положительные, то их сумма не превысит INT_MAX, если разность INT_MAX и одного из чисел меньше второго числа. Если оба числа отрицательные, то разность INT_MIN и одного из чисел должна быть больше другого. Если же оба числа имеют разные знаки, то однозначно их сумма не превысит INT_MAX или INT_MIN.
int sum1(int a, int b, int *overflow) { int c = 0; if (a > 0 && b > 0 && (INT_MAX - b < a) || a < 0 && b < 0 && (INT_MIN - b > a)) { *overflow = 1; } else { *overflow = 0; c = a + b; } return c; }
В этой функции переменной overflow будет присвоено значение 1, если было переполнение. Функция возвращает сумму, независимо от результата сложения.
2. Второй способ проверки – взять для суммы тип, максимальное (и минимальное) значение которого заведомо больше суммы двух целых. После сложения необходимо проверить, чтобы сумма была не больше , чем INT_MAX и не меньше INT_MIN.
int sum2(int a, int b, int *overflow) { signed long long c = (signed long long) a + (signed long long) b; if (c < INT_MAX && c > INT_MIN) { *overflow = 0; c = a + b; } else { *overflow = 1; } return (int) c; }
Обратите внимание на явное приведение типов. Без него сначала произойдёт переполнение, и неправильное число будет записано в переменную c.
3. Третий способ проверки платформозависимый, более того, его реализация будет разной для разных компиляторов. При переполнении целых (обычно) поднимается флаг переполнения в регистре флагов. Можно на ассемблере проверить значение флага сразу же после выполнения суммирования.
int sum3(int a, int b, int *overflow) { int noOverflow = 1; int c = a + b; __asm { jno NO_OVERFLOW mov noOverflow, 0 NO_OVERFLOW: } if (noOverflow) { *overflow = 0; } else { *overflow = 1; } return c; }
Здесь переменная noOverflow равна 1, если нет переполнения. jno (jump if no overflow) выполняет переход к метке NO_OVERFLOW, если переполнения не было. Если же переполнение было, то выполняется
mov noOverflow, 0По адресу переменной noOverflow записывается нуль.
Работа с числами без знака гораздо проще: при переполнении происходит обнуление и известно, что получившееся число заведомо будет меньше каждого из слагаемых.
unsigned usumm(unsigned a, unsigned b, int *overflow) { unsigned c = a + b; if (c < a || c < b) { *overflow = 1; } else { *overflow = 0; } return c; }
Вот полный код, с проверками.
#include <conio.h> #include <stdio.h> #include <limits.h> int sum1(int a, int b, int *overflow) { int c = 0; if (a > 0 && b > 0 && (INT_MAX - b < a) || a < 0 && b < 0 && (INT_MIN - b > a)) { *overflow = 1; } else { *overflow = 0; c = a + b; } return c; } int sum2(int a, int b, int *overflow) { signed long long c = (signed long long) a + (signed long long) b; if (c < INT_MAX && c > INT_MIN) { *overflow = 0; c = a + b; } else { *overflow = 1; } return (int) c; } int sum3(int a, int b, int *overflow) { int noOverflow = 1; int c = a + b; __asm { jno NO_OVERFLOW mov noOverflow, 0 NO_OVERFLOW: } if (noOverflow) { *overflow = 0; } else { *overflow = 1; } return c; } unsigned usumm(unsigned a, unsigned b, int *overflow) { unsigned c = a + b; if (c < a || c < b) { *overflow = 1; } else { *overflow = 0; } return c; } void main() { int overflow; int sum; unsigned usum; //sum1 sum = sum1(3, 5, &overflow); printf("%d + %d = %d (%d)\n", 3, 5, sum, overflow); sum = sum1(INT_MAX, 5, &overflow); printf("%d + %d = %d (%d)\n", INT_MAX, 5, sum, overflow); sum = sum1(INT_MIN, -5, &overflow); printf("%d + %d = %d (%d)\n", INT_MIN, -5, sum, overflow); sum = sum1(INT_MAX, INT_MIN, &overflow); printf("%d + %d = %d (%d)\n", INT_MAX, INT_MIN, sum, overflow); sum = sum1(-10, -20, &overflow); printf("%d + %d = %d (%d)\n", -10, -20, sum, overflow); //sum2 sum = sum2(3, 5, &overflow); printf("%d + %d = %d (%d)\n", 3, 5, sum, overflow); sum = sum2(INT_MAX, 5, &overflow); printf("%d + %d = %d (%d)\n", INT_MAX, 5, sum, overflow); sum = sum2(INT_MIN, -5, &overflow); printf("%d + %d = %d (%d)\n", INT_MIN, -5, sum, overflow); sum = sum2(INT_MAX, INT_MIN, &overflow); printf("%d + %d = %d (%d)\n", INT_MAX, INT_MIN, sum, overflow); sum = sum2(-10, -20, &overflow); printf("%d + %d = %d (%d)\n", -10, -20, sum, overflow); //sum3 sum = sum3(3, 5, &overflow); printf("%d + %d = %d (%d)\n", 3, 5, sum, overflow); sum = sum3(INT_MAX, 5, &overflow); printf("%d + %d = %d (%d)\n", INT_MAX, 5, sum, overflow); sum = sum3(INT_MIN, -5, &overflow); printf("%d + %d = %d (%d)\n", INT_MIN, -5, sum, overflow); sum = sum3(INT_MAX, INT_MIN, &overflow); printf("%d + %d = %d (%d)\n", INT_MAX, INT_MIN, sum, overflow); sum = sum3(-10, -20, &overflow); printf("%d + %d = %d (%d)\n", -10, -20, sum, overflow); //usum usum = usumm(10u, 20u, &overflow); printf("%u + %u = %u (%d)\n", 10u, 20u, usum, overflow); usum = usumm(UINT_MAX, 20u, &overflow); printf("%u + %u = %u (%d)\n", UINT_MAX, 20u, usum, overflow); usum = usumm(20u, UINT_MAX, &overflow); printf("%u + %u = %u (%d)\n", 20u, UINT_MAX, usum, overflow); getch(); }
