Введение

Метод вычитания

В математике и вычислительной технике метод дополнительных кодов — это техника кодирования симметричного диапазона положительных и отрицательных целых чисел таким образом, чтобы для сложения в этом диапазоне можно было использовать один и тот же алгоритм (или механизм). Для заданного количества разрядов половина всех возможных представлений чисел кодирует положительные числа, а другая половина — их соответствующие аддитивные инверсы. Пары взаимно аддитивных обратных чисел называются дополнительными кодами. Таким образом, вычитание любого числа реализуется путем добавления его дополнительного кода. Изменение знака любого числа кодируется путем генерации его дополнительного кода, что можно сделать с помощью очень простого и эффективного алгоритма. Этот метод широко использовался в механических калькуляторах и до сих пор применяется в современных компьютерах. Обобщенное понятие радикального дополнительного кода (как описано ниже) также ценно в теории чисел, например, в теореме Миди. Дополнительный код к девяти для числа, заданного в десятичном представлении, формируется путем замены каждой цифры на девять минус эту цифру. Чтобы вычесть десятичное число y (вычитаемое) из другого числа x (уменьшаемого), можно использовать два метода: в первом методе к y добавляется дополнительный код к девяти от x. Затем формируется дополнительный код к девяти от полученного результата, чтобы получить желаемый результат. Во втором методе дополнительный код к девяти от y добавляется к x, и к сумме добавляется единица. Крайняя левая цифра "1" результата затем отбрасывается. Отбрасывание самой левой "1" особенно удобно на калькуляторах или компьютерах, использующих фиксированное количество цифр: ей некуда деваться, поэтому она просто теряется в процессе вычисления. Дополнительный код к девяти плюс единица известен как дополнительный код к десяти. Метод дополнительных кодов может быть расширен на другие системы счисления (основания); в частности, он используется в большинстве цифровых компьютеров для выполнения вычитания, представления отрицательных чисел в двоичной системе счисления (основание 2) и проверки на переполнение и потерю значимости в вычислениях.

Числовые дополнения

Корневой комплемент числа из *n* цифр в системе счисления с основанием *r* определяется как . На практике корневой комплемент проще получить, прибавив 1 к уменьшенному корневому комплементу, который равен , хотя это кажется столь же сложным вычислением, как и корневой комплемент, на самом деле это проще, поскольку представляет собой просто цифру *r* - 1, повторенную *n* раз. Это связано с тем, что (см. также формулу геометрической прогрессии). Зная это, уменьшенный корневой комплемент числа можно найти, дополнив каждую цифру до *r* - 1, то есть вычитая каждую цифру числа из *r* - 1. Вычитание *b* из *a* с использованием уменьшенных корневых комплементов можно выполнить следующим образом: прибавьте уменьшенный корневой комплемент *b* к *a*, чтобы получить или, что эквивалентно, , который является уменьшенным корневым комплементом *a* - *b*. Дальнейшее взятие уменьшенного корневого комплемента результата дает желаемый ответ . В качестве альтернативы, используя корневой комплемент, *a* - *b* можно получить, прибавив корневой комплемент *b* к *a*, чтобы получить или . Предполагая, что *a* ≥ *b*, результат будет больше или равен *r*, и отбрасывание старшего разряда *r* из результата эквивалентно вычитанию *r*, делая результат или просто , желаемый результат. В десятичной системе счисления корневой комплемент называется дополнением до десяти, а уменьшенный корневой комплемент – дополнением до девяти. В двоичной системе корневой комплемент называется дополнением до двух, а уменьшенный корневой комплемент – дополнением до единицы. Названия комплементов в других системах счисления аналогичны. Некоторые специалисты, в частности Дональд Кнут, рекомендуют использовать положение апострофа для различения между корневым комплементом и уменьшенным корневым комплементом. В этом случае комплемент до четырех относится к корневому комплементу числа в системе с основанием четыре, а комплемент до четырех' – к уменьшенному корневому комплементу числа в системе с основанием пять. Однако это различие не имеет значения, когда основание системы счисления очевидно (что почти всегда так), и тонкая разница в положении апострофа не является общепринятой практикой. Большинство авторов используют термины "дополнение до единицы" и "дополнение до девяти", а многие руководства по стилю опускают апостроф, рекомендуя "дополнение до единицы" и "дополнение до девяти".

Практическое применение

Метод дополнительных кодов использовался во многих механических калькуляторах как альтернатива обращению шестерен. Например:

Калькулятор Паскаля имел два набора цифр результата, черный набор отображал нормальный результат, а красный – девятичный дополнительный код к нему. Горизонтальная планка использовалась для закрытия одного из наборов и отображения другого. Для вычитания красные цифры выставлялись и устанавливались в 0. Затем вводился девятичный дополнительный код к уменьшаемому. На некоторых машинах это можно было сделать, набирая уменьшаемое с помощью внутренних колес дополнительных кодов (то есть без необходимости мысленно вычислять девятичный дополнительный код к уменьшаемому). При отображении этих данных в окне дополнительного кода (красный набор) оператор мог видеть девятичный дополнительный код к девятичному дополнительному коду уменьшаемого, то есть само уменьшаемое. Затем планка перемещалась, чтобы отобразить черные цифры (которые теперь показывали девятичный дополнительный код к уменьшаемому), и вычитаемое прибавлялось путем его набора. Наконец, оператору приходилось снова перемещать планку, чтобы прочитать правильный ответ. В «Комптометре» цифры девятичного дополнительного кода печатались меньшим шрифтом вместе с обычными цифрами на каждой клавише. Для вычитания от оператора ожидалось, что он мысленно вычтет 1 из вычитаемого и введет результат, используя цифры меньшего размера. Поскольку вычитание 1 перед взятием дополнительного кода эквивалентно добавлению 1 после этого, оператор фактически прибавлял десятичный дополнительный код к вычитаемому. Оператору также требовалось удерживать «стопорный фиксатор вычитания», соответствующий самой левой цифре ответа. Этот фиксатор предотвращал перенос за его пределы, что являлось методом «Компотометра» для отбрасывания начальной 1 из результата. Калькулятор «Curta» использовал метод дополнительных кодов для вычитания и сумел скрыть это от пользователя. Числа вводились с помощью слайдов для ввода цифр сбоку устройства. Число на каждом слайде прибавлялось к счетчику результата с помощью зубчатого механизма, который включал кулачки на вращающемся «эшелонном барабане» (также известном как «ступенчатый барабан»). Барабан вращался с помощью рукоятки на верхней части прибора. Количество кулачков, с которыми сталкивалась каждая цифра при вращении рукоятки, определялось значением этой цифры. Например, если слайд установлен в положение «6», вокруг барабана будет ряд из 6 кулачков, соответствующих этому положению. Для вычитания барабан слегка сдвигался перед вращением, что перемещало другой ряд кулачков в положение. В этом альтернативном ряду содержались девятичные дополнительные коды к цифрам. Таким образом, ряд из 6 кулачков, который был готов для сложения, теперь имел ряд из 3 кулачков. Сдвинутый барабан также включал один дополнительный кулачок, который прибавлял 1 к результату (как того требует метод дополнительных кодов). Постоянно присутствующий десятичный дополнительный код «переполнение 1», который выходил за пределы наиболее значащей цифры регистра результатов, фактически отбрасывался.

В компьютерах

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

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

Ручное использование

Метод дополнений использовался для исправления ошибок при ведении бухгалтерских книг от руки. Чтобы исключить запись из столбца чисел, бухгалтер мог добавить новую запись, содержащую дополнение до основания вычитаемого числа. Над цифрами этой записи ставилась черта, чтобы указать на её особый статус. Затем можно было сложить весь столбец чисел, чтобы получить исправленный результат. Использование дополнения до основания удобно для кассиров при выдаче сдачи за покупку, используя купюры одного номинала, равного единице, возведенной в целую степень основания денежной системы. Для десятичных систем счисления это будут 10, 100, 1000 и т.д., например, банкнота в 10 долларов.

В начальной школе

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