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

Дополнять числа на счетной машине c. 1910. Меньшие числа, используемые при вычитании, представляют собой дополнение до девяти больших чисел, которые используются при сложении.

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

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

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

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

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

• 1 Числовые дополнения
• 2 Пример десятичной дроби
  • 2.1 Первый способ
  • 2.2 Второй способ
  • 2.3 Величина чисел
• 3 Бинарный метод
• 4 Представления отрицательных чисел
• 5 Практическое использование
  • 5.1 В компьютерах
  • 5.2 Использование вручную
• 6 В начальной школе
• 7 См. Также
• 8 ссылки

Radix дополнение из п числа цифр у в поразрядном Ь, по определению,. Радикс комплемент наиболее легко получить путем добавления 1 к уменьшенному натальному комплементу, которая. Поскольку цифра повторяется n раз (потому что ; см. Также Формулу геометрического ряда ), уменьшенное дополнение основания числа находится путем дополнения каждой цифры относительно (то есть, вычитая каждую цифру в y из). ${\ displaystyle b ^ {n} -y}$${\ displaystyle \ left (b ^ {n} -1 \ right) -y}$${\ Displaystyle \ влево (Ь ^ {п} -1 \ вправо)}$${\ displaystyle b-1}$${\ displaystyle b ^ {n} -1 = (b-1) \ left (b ^ {n-1} + b ^ {n-2} + \ cdots + b + 1 \ right) = (b-1) б ^ {п-1} + \ cdots + (б-1)}$ ${\ displaystyle b-1}$${\ displaystyle b-1}$

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

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

Цифра	Дополнение девяток
0	9
1	8
2	7
3	6
4	5
5	4
6	3
7	2
8	1
9	0

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

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

 873 [x, the minuend] - 218 [y, the subtrahend]

Первый способ

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

 126 [nines' complement of x = 999 - x] + 218 [y, the subtrahend]

знак равно

 344 [999 - x + y]

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

 344 [result] 655 [nine's complement of 344 = 999 - (999 - x + y) = x - y, the correct answer]

Второй способ

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

Затем берется сумма x и девятки дополнения к y:

 873 [x] + 781 [nines' complement of y = 999 - y]

знак равно

 1654 [999 + x - y]

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

 1654 -1000 [-(999 + 1)]

знак равно

 654 [x - y - 1]

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

 654 + 1

знак равно

 655 [x - y]

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

Величина чисел

В следующем примере результат вычитания содержит меньше цифр, чем x:

 123410 [x, the minuend] - 123401 [y, the subtrahend]

Используя первый метод, сумма дополнений до девяти x и y равна

 876589 [nines' complement of x] + 123401 [y]

знак равно

 999990

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

Если вычитаемое значение y содержит меньше цифр, чем минимальное значение x, во втором методе необходимо добавить начальные нули. Эти нули становятся ведущими девятками при взятии дополнения. Например:

 48032 [x] - 391 [y]

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

 48032 [x] - 00391 [y with leading zeros]

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

 48032 [x] + 99608 [nines' complement of y] + 1

знак равно

 147641

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

Двоичная цифра	Ones' дополнение
0	1
1	0

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

 0110 0100 [x, equals decimal 100] - 0001 0110 [y, equals decimal 22]

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

 0110 0100 [x] + 1110 1001 [ones' complement of y = 1111 1111 - y] + 1 [to get the two's complement = 1 0000 0000 - y] =========== 10100 1110 [x + 1 0000 0000 - y]

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

Основная статья: Представления чисел со знаком

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

Посмотрим, что будет, если x lt; y. В этом случае цифра «1» после добавления не будет зачеркнута, так как она будет меньше. Например (в десятичном формате): ${\ Displaystyle х-у + Ь ^ {п}}$${\ displaystyle b ^ {n}}$

 185 [x] - 329 [y]

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

 185 [x] + 670 [nines' complement of y] + 1

знак равно

 856

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

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

Комптометр 1920-х годов, с добавлением девяти на каждой клавише

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

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

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

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

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

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

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

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

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

• Дополнение до двух - особый случай для двоичных компьютеров

1. ^ Флоридский технический
2. ^ Простые инструкции по эксплуатации управляемого ключевого комптометра, Comptometer Division, Felt and Tarrant Mfg. Co., Чикаго, 1917, стр. 12
3. ^ Карл Barnett Allendoerfer (1971). Основы арифметики и геометрии для учителей начальной школы. Макмиллан.