Чарльз Петцольд - Код. Тайный язык информатики

Давайте рассмотрим типичную задачу на вычитание с заимствованием.

Начнем решение с крайнего правого столбца. Сначала мы замечаем, что 6 больше 3, поэтому нам нужно занять 1 у 5, а затем вычесть 6 из 13, в результате чего получается 7. Мы помним, что заняли 1 у 5, поэтому вместо 5 имеем 4, что меньше 7, поэтому занимаем 1 у 2, вычитаем 7 из 14 и получаем 7. Мы заняли 1 у 2, поэтому у нас есть только единица, из которой вычитаем 1 и получаем 0. Наш ответ — 77.

Как же заставить группу логических вентилей следовать такой странной логике?

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

Числа, участвующие в операции вычитания, называются уменьшаемым и вычитаемым . Вычитаемое вычитается из уменьшаемого, результатом является разность .

Чтобы произвести вычитание без заимствования, сначала нужно вычесть вычитаемое из 999, а не из уменьшаемого.

В данном случае используем число 999, поскольку числа, участвующие в операции, состоят из трех цифр. Если бы они были четырехзначными, мы бы использовали число 9999. При вычитании числа из строки девяток получаем число, называемое дополнением до девяти . Дополнение числа 176 до девяти — 823. Это работает и в обратную сторону: дополнение числа 823 до девяти — 176. Вся прелесть в том, что вне зависимости от значения вычитаемого вычисление его дополнения до девяти никогда не требует заимствования .

После вычисления дополнения вычитаемого до девяти нужно прибавить к нему исходное уменьшаемое.

Наконец, прибавить 1 и вычесть 1000.

Вот и всё. Мы получили такой же результат, как и раньше, ни разу не прибегнув к заимствованию.

Почему это работает? Исходная задача на вычитание такова:

253 – 176.

Если к этому выражению прибавить и вычесть любое число, результат останется прежним. Так что давайте прибавим и вычтем 1000:

253 – 176 + 1000 – 1000.

Выражение эквивалентно следующему:

253 – 176 + 999 + 1 – 1000.

Теперь числа можно перегруппировать:

253 + (999 – 176) + 1 – 1000.

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

А если вычитаемое больше уменьшаемого? Рассмотрим такой пример.

Обычно вы смотрите на подобную задачу и думаете: «Хм, вычитаемое больше уменьшаемого, поэтому придется поменять числа местами, выполнить вычитание и не забыть о том, что результат будет отрицательным». Вы можете произвести перестановку чисел в голове и записать ответ следующим образом.

Процесс выполнения данного расчета без заимствований несколько отличается от предыдущего примера. Как и раньше, мы начинаем с вычитания вычитаемого (253) из 999 для получения дополнения до девяти.

Теперь прибавим дополнение до девяти к исходному уменьшаемому.

На этом этапе в более раннем примере для получения окончательного результата мы могли прибавить 1 и вычесть 1000. Однако в данном случае эта стратегия не сработала бы, поскольку нам пришлось бы вычесть 1000 из 923, что в действительности потребовало бы вычесть 923 из 1000, и без заимствований мы бы не обошлись.

Вместо этого, по аналогии с прибавлением 999, вычтем 999.

Сразу становится очевидным, что наш ответ будет отрицательным, поэтому следует поменять числа местами и вычесть 922 из 999. Это опять же не требует заимствований, а ответ совпадает с ожидаемым.