Электроника:Цифровая электроника/Двоичная арифметика/Двоичное переполнение

Содержание

Теория

Практика

Проверка знаний

Рецепты

Эксперименты

Резерв

Резерв

Резерв

Резерв

Перевод: Макаров В. (valemak)

Проверка/Оформление/Редактирование: Мякишев Е.А.

Двоичное переполнение

Одна из основных опасностей в отношении двоичных чисел со знаком заключается в переполнении, когда результат сложения или вычитания выходит за пределы диапазона величин, которые можно представить с помощью выделенного количества бит. Ведь как вы помните, что с самого начала зафиксировано место знакового экстрабита и выделено неизменяемое количество битов для величины представляемого числа.

В последнем примере из предыдущего раздела мы использовали пять двоичных битов для представления величины числа и крайний левый (шестой) бит как бит отрицательного веса и знака. С пятью битами для представления величины мы можем работать с числами, абсолютное значение которых не превышает 25, т.е. от 0 до 32 максимум. Это означает, что мы можем представить число в диапазоне от -32₁₀ (100000₂) до +31₁₀ (011111₂).

Ограничения для чисел с шестибитным полем

Если выполним операцию сложения над двумя двоичными числами (используя шестой бит для отрицательного веса и указания знака), и при этом итоговый результат будет либо больше +31₁₀, либо меньше -32₁₀, мы не получим правильный ответ с тем количеством битов, которые мы определили для работы с числами. Давайте попробуем сложить 17₁₀ и 19₁₀, чтобы увидеть, как возникает переполнение, дающее чрезмерно большое положительное число:

Переведём наши десятеричные числа в двоичную форму (где мы для представления величин чисел выделяем 5 битов + дополнительный шестой экстрабит для отрицательного веса и знака):

17₁₀ = 010001₂, 19₁₀ = 010011₂

Пока что всё нормально (нам хватает битов для представления этих чисел). Но давайте теперь сложим их столбиком:

Рис. 1. Шестибитное поле ограничивает представление чисел.

Итоговый ответ: 100100₂ = -28₁₀ (вместо правильного +36₁₀).

Шестой экстрабит (крайний слева), равный единице, интерпретируется как -32₁₀, потому что этот бит зарезервирован для обозначения отрицательного веса и указания знака. И полученный ответ будет преставлением числа -28₁₀, а не +36₁₀. Очевидно, что здесь неверный результат. Что пошло не так?

Ответ кроется в ограничениях шестибитного числового поля, с которым мы работаем. Поскольку величина правильной суммы (36₁₀) превышает допустимый предел для нашего назначенного битового поля, возникает ошибка переполнения.

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

Аналогичная ошибка происходит, когда мы складываем два отрицательных числа, получая сумму, которая слишком мала для нашего шестибитного двоичного поля. Давайте попробуем сложить -17₁₀ и -19₁₀ вместе, чтобы увидеть, как это работает (или не работает, в зависимости от обстоятельств!):

Переведём наши десятеричные числа в двоичную форму (где мы для представления величин чисел выделяем 5 битов + дополнительный шестой экстрабит для отрицательного веса и знака):

-17₁₀ = 101111₂, -19₁₀ = 101101₂

Опять пробуем сложить столбиком:

Рис. 2. Мы снова получили неверный ответ из-за ошибки переполнения.

Так как для представления чисел используются только 6 битов, а у нас в ответе их семь, то «лишний» седьмой бит (крайний слева) будет отброшен. И вместо ожидаемого 1011100₂ = -36₁₀ мы получим неверные 011100₂ = +28₁₀.

Итак, (неправильный) ответ – положительные двадцать восемь. Тот факт, что реальная сумма отрицательных семнадцати и отрицательных девятнадцати была слишком мала, чтобы быть должным образом представленной с помощью пятибитового поля для величины и шестого знакового бита, является основной причиной этого недоразумения.

Использование седьмого бита для знакового бита

Давайте попробуем решить эти две задачи ещё разок, вот только на этот раз мы будем использовать седьмой (а не шестой) экстрабит для знакового бита и 6 (а не 5) битов для представления самой величины числа:

Рис. 3. Использование седьмого бита для знакового бита даёт верные результаты.

Используя достаточно большие битовые поля, позволяющие обрабатывать итоговые величины сумм, приходим к правильным ответам. В этих примерах мы смогли обнаружить ошибки переполнения, выполнив сложения в десятеричной форме и сравнив результаты с двоичными ответами.

Например, складывая +17₁₀ и +19₁₀ вместе, мы знали, что ответ должен быть +36₁₀, поэтому, когда двоичная сумма оказалась равной -28₁₀, было очевидно, что где-то вкралась ошибка. Хотя это допустимый способ обнаружения переполнения, он не очень эффективен.

В конце концов, вся идея дополнения состоит в том, чтобы иметь возможность надёжно складывать двоичные числа вместе и не пришлось бы лично контролировать правильность результата, ведь мы же не будем каждый раз для проверки складывать числа в десятеричной форме! Это особенно актуально при построении электронных схем для сложения двоичных величин: схема должна иметь возможность самостоятельно проверять себя на переполнение без участия человека, который знает правильный ответ.

Нам нужен простой метод обнаружения ошибок, не требующий дополнительных арифметических действий. Возможно, самое элегантное решение – проверить знак суммы и сравнить его со знаками складываемых чисел.

Очевидно, что два положительных числа, сложенные вместе, должны дать положительное число, а два отрицательных числа, сложенные вместе, должны дать отрицательное число. Вы же наверняка заметили, что всякий раз, когда у нас возникло переполнение, знак суммы всегда был противоположен знакам слагаемых: +17₁₀ плюс +19₁₀, дало ошибочные -28₁₀, или -17₁₀ плюс -19₁₀ выдало неверные +28₁₀.

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

Ответ на этот вопрос гениален в своей простоте: при сложении двух чисел с противоположными знаками никогда не будет ошибки переполнения! Причина этого становится очевидной, если учесть сам характер такого явления, как переполнение. Оно происходит, когда величина числа превышает диапазон, разрешённый размером битового поля.

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

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