Вы когда-нибудь сталкивались с ситуацией, когда сложение двух положительных чисел приводило к отрицательному числу или наоборот? Вы видите такие нелепые результаты, когда переполнениепроисходит при арифметических операциях. Это когда результат арифметической операции не может уместиться в пределах размера слова типа данных.
Давайте проясним это на нескольких примерах.
Неподписанное дополнение
Допустим, у нас есть два 4-битных числа: 12 (в двоичном формате 1100) и 7 (в двоичном формате 0111). Сумма этих двух чисел 12 + 7 = 19 (в двоичном формате 10011) требует 5 бит для представления результата. Если мы усекаем биты с весом больше 2³, то есть если мы отбрасываем бит более высокого порядка, у нас остается 0011, что равно 3. Фактически это эквивалентно значению 19 mod 16 = 3.
В C и Java переполнение не считается ошибкой.
Дополнение до двух
Поскольку как положительные, так и отрицательные числа могут быть представлены в дополнении до двух, мы должны решить, что делать, когда результирующее значение сложения в дополнении до двух становится слишком большим или слишком маленьким для представления с заданным количеством битов. Как мы видели здесь, с w битами,
Когда сумма двух чисел превышает максимальное значение, мы называем это положительным переполнением, а когда результат меньше минимального значения, мы называем это отрицательное переполнение. Давайте посмотрим на это в действии с 4 битами.
Максимальное положительное значение, которое может быть представлено 4 битами в дополнительном представлении до двух, равно 7, а минимальное значение равно -8. В следующей таблице показаны два примера сценариев переполнения.
Беззнаковое умножение
Как и при сложении, при умножении также приходится иметь дело со сценариями переполнения. Например, с 4 битами для представления чисел 4 (в двоичном формате 0100) и 5 (в двоичном формате 0101) умножение (ожидаемое значение 20 [в двоичном формате 10100]) дает в результате 4 (в двоичном формате 0100). Это эквивалентно 4,5 по модулю 2⁴ = 20 по модулю 16 = 4.
Умножение с дополнением до двух
С числами в дополнении до двух мы можем получить результат умножения, выполнив следующие два шага.
Допустим, у нас есть два числа x и y, каждое из которых имеет w-биты, тогда
