Книга Код. Тайный язык информатики, страница 36. Автор книги Чарльз Петцольд

Разделитель для чтения книг в онлайн библиотеке

Онлайн книга «Код. Тайный язык информатики»

Cтраница 36

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

Код. Тайный язык информатики

Начнем решение с крайнего правого столбца. Сначала мы замечаем, что 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. Это опять же не требует заимствований, а ответ совпадает с ожидаемым.

Код. Тайный язык информатики

Этот метод применим и к двоичным числам, работать с которыми оказывается проще, чем с десятичными. Давайте посмотрим, как это работает.

Вот исходная задача на вычитание.

Код. Тайный язык информатики

После преобразования чисел в двоичные получаем следующую задачу.

Код. Тайный язык информатики

Шаг 1. Вычесть вычитаемое из 11111111 (что соответствует 255).

Код. Тайный язык информатики

При работе с десятичными числами вычитаемое вычиталось из строки девяток, а результат назывался дополнением до девяти. При работе с двоичными числами вычитаемое вычитается из строки единиц, результат — дополнение до единицы. Заметьте, что нам на самом деле не нужно выполнять вычитание, чтобы вычислить дополнение до единицы, поскольку каждый 0 в исходном числе превращается в 1 в дополнении до единицы, а каждая 1 превращается в 0. По этой причине дополнение до единицы иногда также называется отрицанием или инверсией. (Сейчас вы, вероятно, вспомнили о том, что в главе 11 мы конструировали устройство, называемое инвертором, которое меняло 0 на 1, а 1 на 0.)

Вход
Поиск по сайту
Ищем:
Календарь
Навигация