Как избежать переполнения в выражении? С++

Question

Довольно долго искал ошибку в коде. Спасибо отладчику VS. Ошибка в этой строке:

this->b = ((hh * mul) % (this->p - 1));

this->b - переменная типа int, 4 байта. hh, mul, this->p - аналогично. Проблема возникает, например, при числах:

hh = -2156842;
mul = 3059;
this->p = 3061;

Ошибка выходит в самом первом выражении. При перемножении отрицательного числа hh и положительным mul возникает большущее ПОЛОЖИТЕЛЬНОЕ число. Это переполнение? Как его избежать? Как выделяется память в выражениях?

Answer 1

Ну, конечно, переполнение, что же ещё)

Сделай все типы int64_t, его диапазон от -9 223 372 036 854 775 808 до 9 223 372 036 854 775 807. hh * mul = -6 597 779 678, это спокойно влезет в него, но не влезет в int, у которого диапазон от -2 147 483 648 до 2 147 483 647.

P.S. Правила приведения выражения к общему типу следующие:

Если два типа меньше int (int32_t - 4 байта), то они оба приводятся к нему

Например, int8_t * uint16_t = int32_t
Если типы больше или равны int:
1. Если типы одинаковой байтности, выбирается беззнаковый
  
  Например, int32_t * uint32_t = uint32_t
2. Если типы разной байтности, выбирается наибольший из них
  
  Например, uint32_t - int64_t = int64_t

Answer 2

Да, это является переполнением.

Чтобы избежать переполнения стоит воспользоваться одним замечательным свойством сравнений по модулю: числа a * b и (a % m) * (b % m) сравнимы по модулю m. Однако, нам не достаточно того, что они будут сравнимы и необходимо еще сохранить знак (я подразумеваю не выбор между -x или +x, а выбор между x и x - m, где 0 < x < m). Но оператор % его сохраняет.

Стало быть, можно написать следующее:

auto mod = this->p - 1;
auto mul1 = hh % mod;
auto mul2 = mul % mod;
this->b = (mul1 * mul2) % mod;

Однако, стоит помнить, что даже такой трюк не спасет, если модуль this->p - 1 будет слишком большим и числа hh, mul окажутся "плохими".

Память перед переменную выделяется ровно k бит. Если же при выполнении получается некоторое число, не влезающее в эти k бит, то "лишние" биты будут обрезаны. Для беззнаковых чисел это означает, что с точки зрения математики результат a * b, на самом деле, будет равен (a * b) % (2^k). Для беззнаковых же там всё чуточку сложнее. Всё связано с представлением отрицательных чисел. Подробнее про такое представление можно почитать, например, на википедии. Как знаковые, так и беззнаковые числа, зациклены. Это значит, что, если числа покрывают диапазом [L; R], то R + 1 = L, L - 1 = R. Для беззнаковых L = 0, R = 2^k - 1, для беззнаковых L = - 2^{k - 1}, R = 2^{k - 1} - 1. То есть, результат a * b, на самом деле, равен (a * b - L) % (R - L) + L.

БЛОГ НА HUSL

Как избежать переполнения в выражении? С++

Ответы (2 шт):