Метод дополнений

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

Дополнение до девяти числа, заданного в десятичном представлении, образуется путем замены каждой цифры на девять минус эта цифра. Чтобы вычесть десятичное число y ( вычитаемое ) из другого числа x ( уменьшаемое ), можно использовать два метода:

В первом методе дополнение x до девяти добавляется к y . Затем формируется дополнение полученного результата до девяти для получения желаемого результата.

Во втором методе дополнение y до девяти добавляется к x , а к сумме добавляется единица. Затем самая левая цифра '1' результата отбрасывается. Отбрасывание самой левой '1' особенно удобно на калькуляторах или компьютерах, которые используют фиксированное количество цифр: ее некуда девать, поэтому она просто теряется во время вычислений. Дополнение до девяти плюс один известно как дополнение до десятков.

Метод дополнений может быть распространен на другие системы счисления ( радике ); в частности, он используется на большинстве цифровых компьютеров для выполнения вычитания, представления отрицательных чисел в двоичной или двоичной арифметике и проверки переполнения при вычислениях. ^[1]

Дополнение по основанию -значного числа в системе счисления определяется как . На практике дополнение по основанию проще получить, прибавив 1 к уменьшенному дополнению по основанию , которое равно . Хотя это кажется столь же сложным для вычисления, как и дополнение по основанию, на самом деле это проще, поскольку это просто цифра, повторенная раз. Это потому, что (см. также Формула геометрической прогрессии ). Зная это, уменьшенное дополнение по основанию числа можно найти, дополняя каждую цифру относительно , ​​т.е. вычитая каждую цифру из .${\displaystyle n}$${\displaystyle у}$ ${\displaystyle б}$${\displaystyle b^{n}-y}$${\displaystyle \left(b^{n}-1\right)-y}$${\displaystyle \left(b^{n}-1\right)}$${\displaystyle б-1}$${\displaystyle n}$${\displaystyle b^{n}-1=(b-1)\left(b^{n-1}+b^{n-2}+\cdots +b+1\right)=(b-1)b^{n-1}+\cdots +(b-1)}$${\displaystyle б-1}$${\displaystyle у}$${\displaystyle б-1}$

Вычитание из с использованием уменьшенных дополнений к основанию может быть выполнено следующим образом. Добавьте уменьшенное дополнение к основанию к , чтобы получить или эквивалентно , которое является уменьшенным дополнением к основанию . Дальнейшее взятие уменьшенного дополнения к основанию приводит к желаемому ответу .${\displaystyle у}$${\displaystyle x}$${\displaystyle x}$${\displaystyle у}$${\displaystyle b^{n}-1-x+y}$${\displaystyle b^{n}-1-(xy)}$${\displaystyle xy}$${\displaystyle b^{n}-1-(xy)}$${\displaystyle xy}$

В качестве альтернативы, используя дополнение по основанию, можно получить, прибавив дополнение по основанию к , чтобы получить или . Предполагая , что результат будет больше или равен , и отбрасывание лидирующего знака из результата равносильно вычитанию , делая результат или просто желаемым результатом.${\displaystyle xy}$${\displaystyle у}$${\displaystyle x}$${\displaystyle x+b^{n}-y}$${\displaystyle x-y+b^{n}}$${\displaystyle y\leq x}$${\displaystyle б^{н}}$${\displaystyle 1}$${\displaystyle б^{н}}$${\displaystyle x-y+b^{n}-b^{n}}$${\displaystyle xy}$

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

Дополнение до девяти десятичной цифры — это число, которое нужно к ней прибавить, чтобы получить 9; дополнение до девяти 3 — это 6, дополнение до девяти 7 — это 2 и т. д., см. таблицу. Чтобы сформировать дополнение до девяти большего числа, каждая цифра заменяется своим дополнением до девяти.

Рассмотрим следующую задачу на вычитание:

 873 [x, уменьшаемое]- 218 [y, вычитаемое]

Вычислите дополнение уменьшаемого числа до девяти, 873. Добавьте это к вычитаемому 218, затем вычислите дополнение результата до девяти.

 126 [дополнение x до девяти = 999 - x]+ 218 [y, вычитаемое]————— 344 [999 - х + у]

Теперь вычислите дополнение результата до девяти.

 344 [результат] 655 [дополнение до девяти числа 344 = 999 - (999 - x + y) = x - y, правильный ответ]

Вычислите дополнение до девяти числа 218, которое равно 781. Поскольку число 218 состоит из трех цифр, это то же самое, что вычесть 218 из 999.

Далее берется сумма и дополнение до девяти :${\displaystyle x}$${\displaystyle у}$

 873 [х]+ 781 [дополнение y до девяти = 999 - y]————— 1654 [999 + х - у]

Затем первая цифра «1» отбрасывается, и получается 654.

1654-1000 [-(999 + 1)]————— 654 [-(999 + 1) + 999 + х - у]

Это пока не верно. На первом этапе к уравнению было добавлено 999. Затем 1000 было вычтено, когда была отброшена ведущая 1. Таким образом, полученный ответ (654) на единицу меньше правильного ответа . Чтобы исправить это, к ответу добавляется 1:${\displaystyle xy}$

 654+ 1————— 655 [х - у]

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

В следующем примере результат вычитания имеет меньше цифр, чем :${\displaystyle x}$

 123410 [x, уменьшаемое]- 123401 [y, вычитаемое]

Используя первый метод, сумма девяток-дополнений чисел и равна${\displaystyle x}$${\displaystyle у}$

 876589 [дополнение x до девяти]+ 123401 [г]———————— 999990

Дополнение числа 999990 до девяти равно 000009. Удаление начальных нулей дает 9 — желаемый результат.

Если вычитаемое, , имеет меньше цифр, чем уменьшаемое, , во втором методе необходимо добавить ведущие нули. Эти нули становятся ведущими девятками, когда берется дополнение. Например:${\displaystyle у}$${\displaystyle x}$

 48032 [х]- 391 [г]

можно переписать

 48032 [х]- 00391 [y с ведущими нулями]

Замена 00391 его дополнением до девяти и добавление 1 дает сумму:

 48032 [х]+ 99608 [дополнение y до девяти]+ 1——————— 147641

Отбрасывая первую цифру 1, получаем правильный ответ: 47641.

Метод дополнений особенно полезен в двоичной системе счисления (основание 2), поскольку дополнение до единиц очень легко получить путем инвертирования каждого бита (изменение '0' на '1' и наоборот). Добавление 1 для получения дополнения до двух можно выполнить путем имитации переноса в младший бит. Например:

 0110 0100 [x, равно десятичному 100]- 0001 0110 [y, равно десятичному 22]

становится суммой:

 0110 0100 [х]+ 1110 1001 [дополнение y до единицы = 1111 1111 - y]+ 1 [чтобы получить дополнение до двух = 1 0000 0000 - y]——————————— 10100 1110 [х + 1 0000 0000 - у]

Отбрасывая начальную «1», получаем ответ: 0100 1110 (равняется десятичному 78)

Метод дополнений обычно предполагает, что операнды положительны и что y ≤ x , логические ограничения, учитывая, что сложение и вычитание произвольных целых чисел обычно выполняется путем сравнения знаков, сложения двух чисел или вычитания меньшего из большего и присвоения результату правильного знака.

Давайте посмотрим, что произойдет, если x < y . В этом случае не будет цифры "1", которую нужно будет вычеркнуть после сложения, так как будет меньше . Например, (в десятичной системе):${\displaystyle x-y+b^{n}}$${\displaystyle б^{н}}$

 185 [х]- 329 [г]

Дополнение y и добавление дает:

 185 [х]+ 670 [дополнение y до девяти]+ 1————— 856

На этом этапе нет простого способа завершить вычисления вычитанием (в данном случае 1000); нельзя просто игнорировать ведущую 1. Ожидаемый ответ — −144, что не так уж и далеко, как кажется; 856 — это десятичный дополнительнй код числа 144. Эту проблему можно решить несколькими способами:${\displaystyle б^{н}}$

• Игнорируйте проблему. Это разумно, если человек работает с вычислительным устройством, которое не поддерживает отрицательные числа, поскольку сравнение двух операндов перед вычислением, чтобы их можно было ввести в правильном порядке, и проверка того, что результат является разумным, легко поддаются человеку.
• Используйте тот же метод, чтобы вычесть 856 из 1000, а затем добавьте к результату знак «минус».
• Представьте отрицательные числа в виде дополнений к положительным числам. Числа, меньшие, считаются положительными; остальные считаются отрицательными (и их величину можно получить, взяв дополнение к основанию). Это лучше всего работает для четных оснований, поскольку знак можно определить, посмотрев на первую цифру. Например, числа в записи с дополнением до десятков положительны, если первая цифра равна 0, 1, 2, 3 или 4, и отрицательны, если 5, 6, 7, 8 или 9. И это очень хорошо работает в двоичной системе, поскольку первый бит можно считать знаковым битом: число положительно, если знаковый бит равен 0, и отрицательно, если он равен 1. Действительно, дополнение до двух используется в большинстве современных компьютеров для представления знаковых чисел.${\displaystyle b^{n}/2}$
• Дополните результат, если нет переноса старшей цифры (указание на то, что x меньше y ). Это проще реализовать с помощью цифровых схем , чем сравнивать и менять местами операнды. Но поскольку взятие дополнения по основанию требует добавления 1, это трудно сделать напрямую. К счастью, можно использовать трюк, чтобы обойти это добавление: вместо того, чтобы всегда устанавливать перенос в младшей цифре при вычитании, перенос старшей цифры используется в качестве входного сигнала переноса в младшей цифре (операция, называемая переносом по концам ). Таким образом, если y ≤ x , добавляется перенос из старшей цифры, который обычно игнорируется, что дает правильный результат. А если нет, то 1 не добавляется, и результат на единицу меньше дополнения по основанию ответа или уменьшенного дополнения по основанию, которое не требует добавления для получения. Этот метод используется компьютерами, которые используют знак и величину для представления знаковых чисел.

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

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

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

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

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

Дополнение суммы удобно для кассиров, выдающих сдачу за покупку валюты в едином номинале 1, возведенном в целую степень основания валюты. Для десятичных валют это будет 10, 100, 1000 и т. д., например, купюра в 10 долларов.

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

• Курта