Текст книги "Код. Тайный язык информатики"
Автор книги: Чарльз Петцольд
Жанр: Компьютеры: прочее, Компьютеры
Возрастные ограничения: +16
сообщить о неприемлемом содержимом
Текущая страница: 8 (всего у книги 25 страниц) [доступный отрывок для чтения: 8 страниц]
Глава 12. Двоичный сумматор
Сложение – простейшая арифметическая операция. Если мы хотим создать компьютер (а именно в этом заключается цель этой книги), сначала нужно найти способ создания устройства, складывающего два числа. По сути, компьютеры выполняют только операцию сложения. Если нам удастся сконструировать механизм, умеющий складывать, мы окажемся способны создать устройство, использующее операцию сложения для того, чтобы вычитать, умножать, делить, рассчитывать платежи по ипотеке, отправлять ракеты на Марс, играть в шахматы и вносить путаницу в наши телефонные счета.
Сумматор, который мы построим, будет большим, нескладным, медленным и шумным по сравнению с современными калькуляторами и компьютерами. Самое интересное заключается в том, что мы соберем эту машину из простых электрических устройств, о которых говорили в предыдущих главах, – переключателей, лампочек, проводов, батарейки и реле, объединенных в различные логические вентили. Этот сумматор будет состоять исключительно из деталей, которые уже были изобретены 120 лет назад. Особенно хорошо то, что нам не нужно ничего собирать в своей гостиной; вместо этого мы можем конструировать на бумаге и в уме.
Эта машина будет работать исключительно с двоичными числами, в ней будут отсутствовать некоторые современные функции. Вы не сможете использовать клавиатуру для ввода чисел, подлежащих сложению; вместо этого будет ряд переключателей. Роль дисплея для отображения результатов в этом сумматоре исполнит ряд лампочек.
Однако машина сумеет сложить два числа, и она сделает это фактически как компьютер.
Сложение двоичных чисел похоже на сложение десятичных. Если хотите сложить два десятичных числа, например 245 и 673, вы разбиваете задачу на более простые этапы. На каждом этапе складываете две десятичные цифры. В данном примере начинаете со сложения 5 и 3. Эта задача решается быстрее, если вы знаете таблицу сложения.
Большая разница между сложением десятичных и двоичных чисел заключается в том, что в случае с двоичными числами используется более простая таблица.
Если вы выросли среди дельфинов, вероятно, вы в школе учили эту таблицу, громко произнося:
0 плюс 0 равно 0,
0 плюс 1 равно 1,
1 плюс 0 равно 1,
1 плюс 1 равно 0, 1 в уме.
Вы можете добавить в эту таблицу нули так, чтобы каждый результат представлял 2-битное значение.
Таким образом, результатом сложения пары двоичных чисел являются два бита, которые называются разрядом суммы и разрядом переноса (1 плюс 1 равно 0, 1 в уме). Теперь мы можем разделить таблицу сложения двоичных чисел на две таблицы. Первая – для разряда суммы.
Вторая – для разряда переноса.
Сложение двоичных чисел удобно рассматривать так, поскольку наш сумматор выполняет операции суммирования и переноса отдельно. Для создания двоичного сумматора потребуется сконструировать схему, выполняющую эти операции. Работа исключительно в двоичной системе счисления значительно упрощает задачу, поскольку все части схемы – переключатели, лампочки и провода – могут представлять двоичные цифры.
Как и при сложении десятичных чисел, мы складываем двоичные числа столбец за столбцом, начиная с крайнего правого.
Обратите внимание: при сложении значений в третьем столбце справа 1 переносится в следующий столбец. Это происходит снова в шестом, седьмом и восьмом столбцах справа.
Какого размера двоичные числа мы хотим сложить? Поскольку мы создаем сумматор прямо в уме, то можем сделать так, чтобы он складывал очень длинные числа. Однако давайте будем благоразумными и ограничимся двоичными числами длиной до восьми бит, то есть будем складывать двоичные числа в диапазоне от 0000 0000 до 1111 1111 (десятичные от 0 до 255). Сумма двух 8-битных чисел может достигать двоичного значения 1 1111 1110 (десятичного значения 510).
Пульт управления нашим двоичным сумматором может выглядеть так.
На этом пульте есть два ряда по восемь переключателей. Этот набор переключателей – устройство ввода, которое мы будем использовать для ввода двух 8-битных значений. В этом устройстве выключенный переключатель (положение вниз) соответствует значению 0, а включенный (положение вверх) – 1, как в случае с настенными переключателями в вашем доме. Устройство вывода в нижней части пульта – ряд из девяти лампочек, которые отобразят результат сложения. Негорящая лампочка соответствует значению 0, горящая – 1. Нам требуется девять лампочек, поскольку сумма двух 8-битных чисел может быть 9-битным числом.
В остальном сумматор будет состоять из логических вентилей, соединенных различными способами. Переключатели будут активировать реле в логических вентилях, которые, в свою очередь, будут зажигать нужные лампочки. Например, если мы хотим сложить числа 0110 0101 и 1011 0110 (из предыдущего примера), включаем соответствующие переключатели.
Загоревшиеся лампочки показывают результат: 1 0001 1011. По крайней мере, мы на это надеемся. Мы ведь еще не собрали устройство!
В предыдущей главе я упомянул, что в этой книге буду использовать множество реле. Для 8-битного сумматора, который мы создаем, требуется не менее 144 реле – по восемнадцать для каждой из восьми пар битов, которые складываем. Если бы я показал готовую схему, вы бы наверняка испугались. Никому не под силу разобраться в схеме, состоящей из ста сорока четырех хитро соединенных реле. Вместо этого мы будем решать такую задачу поэтапно, используя логические вентили.
Возможно, вы сразу заметили связь между логическими вентилями и сложением двоичных чисел, когда увидели таблицу для разряда переноса, который возникает в результате сложения двух однобитных чисел.
Вероятно, вы узнали в ней результат работы вентиля И.
Таким образом, вентиль И вычисляет значение разряда переноса при сложении двух двоичных цифр.
Ага! Мы определенно делаем успехи. Наш следующий шаг, похоже, заключается в том, чтобы убедить некоторые реле вести себя так:
Это вторая часть задачи при сложении пары двоичных цифр. Вычислить значение разряда суммы оказывается не так просто, как значение разряда переноса, но мы справимся и с этой сложностью.
Первое, что нужно понять, – это то, что результат работы вентиля ИЛИ близок к тому, что нам нужно, за исключением значения в правом нижнем углу.
Результат работы вентиля И-НЕ также близок к тому, что нам требуется, за исключением значения в верхнем левом углу:
Итак, давайте подключим вентили ИЛИ и И-НЕ к одним и тем же входам.
В следующей таблице представлены выходные сигналы вентилей ИЛИ и И-НЕ и их сравнение с тем, что мы хотим получить от сумматора.
Заметьте, что мы хотим получить значение 1, только если выходные сигналы обоих вентилей ИЛИ и И-НЕ равны 1. Это говорит о том, что эти два выходных сигнала могут являться входными сигналами для вентиля И.
То, что нужно.
Обратите внимание: во всей этой схеме по-прежнему есть только два входа и один выход. Два входа относятся к обоим вентилям ИЛИ и И-НЕ. Выходные сигналы вентилей ИЛИ и И-НЕ подаются на вход вентиля И, и это дает именно тот результат, к которому мы стремимся.
На самом деле у этой схемы есть название: вентиль исключающее ИЛИ (Искл-ИЛИ, оно же – сложение по модулю 2). Она называется так потому, что выход равен 1, если вход A равен 1 или вход B равен 1, но не оба одновременно. Вместо того чтобы рисовать вентили ИЛИ, И-НЕ и И, мы можем использовать обозначение, которым инженеры-электрики показывают вентиль Искл-ИЛИ.
Это обозначение очень похоже на обозначение вентиля ИЛИ, но имеет дополнительную кривую линию со стороны входа.
Вентиль Искл-ИЛИ – это последний логический элемент, который будет подробно описан в этой книге. Иногда в электротехнике используется шестой вентиль, называющийся вентилем совпадения или эквивалентности, поскольку выход равен 1 только при одинаковых сигналах на входе. Вентиль совпадения на выходе действует противоположно вентилю Искл-ИЛИ, поэтому его обозначение аналогично обозначению вентиля Искл-ИЛИ, но дополнено кружком со стороны выхода[17]17
В общем случае кружок со стороны выхода означает инверсию результата операции. Прим. науч. ред.
[Закрыть].
Давайте повторим все, что уже знаем. При сложении двух двоичных чисел получается бит суммы и бит переноса.
Для получения этих результатов можно использовать следующие два вентиля.
Разряд суммы двух двоичных чисел задается выходом вентиля Искл-ИЛИ, а разряд переноса – выходом вентиля И, поэтому можно комбинировать вентили И и Искл-ИЛИ для сложения двух двоичных цифр A и B.
Вместо многократного перерисовывания вентилей И и Искл-ИЛИ можно просто нарисовать схему, подобную следующей.
Существует причина, по которой эта схема называется полусумматором. Разумеется, она складывает две двоичные цифры и выдает бит суммы и бит переноса. Однако длина подавляющего большинства двоичных чисел превышает один бит. То, что полусумматор не может сделать, так это прибавить возможный бит переноса, получившийся в результате предыдущей операции сложения. Представьте, что складываем два двоичных числа.
Мы можем использовать полусумматор только для сложения цифр в правом крайнем столбце: 1 плюс 1 равно 0, 1 переносится. В случае со вторым столбцом справа нам, по сути, нужно сложить три двоичные цифры из-за переноса. И это касается всех остальных столбцов. Каждая последующая операция сложения двух двоичных цифр может включать бит переноса из предыдущего столбца.
Для сложения трех двоичных цифр понадобятся два полусумматора и вентиль ИЛИ, соединенные следующим образом.
Чтобы разобраться в этой схеме, начнем со входов A и B первого полусумматора слева. Результат – бит суммы и бит переноса. Эта сумма должна быть добавлена к переносу из предыдущего столбца, поэтому они являются входами для второго полусумматора. Сумма, полученная от второго полусумматора, – окончательная. Два переноса из полусумматоров – входы для вентиля ИЛИ. Может показаться, что здесь нужен второй полусумматор, и такая схема, безусловно, сработала бы. Однако если вы проанализируете все возможности, то обнаружите, что оба переноса из двух полусумматоров никогда не равны 1. Вентиля ИЛИ достаточно для их сложения, поскольку он действует так же, как вентиль Искл-ИЛИ, если оба входных сигнала одновременно не равны 1.
Вместо многократного перерисовывания этой схемы можем просто назвать ее полным сумматором.
В следующей таблице представлены все возможные комбинации входов для полного сумматора и результирующие выходы.
В начале этой главы я сказал, что для создания сумматора потребуются 144 реле. Вот как я это понял: для каждого вентиля И, ИЛИ и И-НЕ требуются по два реле. Таким образом, вентиль Искл-ИЛИ состоит из шести реле. Полусумматор – это вентиль Искл-ИЛИ и вентиль И, поэтому для его создания необходимы восемь реле. Каждый полный сумматор – два полусумматора и вентиль ИЛИ, то есть 18 реле. Нам нужны восемь полных сумматоров для создания 8-битной машины, или 144 реле.
Вспомните наш исходный пульт управления с переключателями и лампочками.
Теперь мы можем начать присоединять переключатели и лампочки к полному сумматору.
Сначала подключим два крайних правых переключателя и крайнюю правую лампочку к полному сумматору.
Когда вы начинаете складывать два двоичных числа, первый столбец цифр отличается от остальных тем, что не может содержать бит переноса из предыдущего столбца. В первом столбце нет бита переноса, поэтому вход для переноса полного сумматора соединяется с землей, то есть его значением является 0 бит. Разумеется, в результате сложения первой пары двоичных цифр может получиться бит переноса. Этот выход переноса – вход для следующего столбца.
Для следующих двух цифр и лампочки вы используете полный сумматор, подключенный так.
Выход переноса, полученный от первого полного сумматора, является входом для второго полного сумматора. Каждый последующий столбец цифр складывается по той же схеме. Каждый разряд переноса из одного столбца подается на вход для переноса следующего столбца.
Наконец, восьмая и последняя пара переключателей подключена к последнему полному сумматору.
Здесь последний выход для переноса подключен к девятой лампочке.
Вот еще один способ изобразить схему из восьми полных сумматоров (full adder, FA), в которой каждый выход для переноса (CO) подключен к следующему входу для переноса (CI).
Представим единое обозначение 8-битного сумматора, входы обозначим буквами от A0 до A7 и от B0 до B7, выходы – буквами от S0 до S7 (от sum – «сумма»).
Это распространенный способ обозначения отдельных битов многобитного числа. Биты A0, B0 и S0 являются младшими, а биты A7, B7 и S7 – старшими. Например, вот как с помощью этих букв с индексами можно было бы представить двоичное число 0110 1001.
Индексы начинаются с 0 и увеличиваются по мере перехода ко все более значимым цифрам, поскольку они соответствуют показателю степени двойки.
Если вы умножите каждую степень двойки на цифру, расположенную под ней, и сложите результаты, получите десятичный эквивалент числа 0110 1001, который равен 64 + 32 + 8 + 1, или 105.
По-другому 8-битный сумматор можно изобразить так.
Восьмерки внутри стрелок указывают на то, что каждая из них – это группа из восьми отдельных сигналов. Индексы символов A7 … A0, B7 … B0 и S7 … S0 также обозначают восьмиразрядность числа.
Как только соберете один 8-битный сумматор, вы сможете создать второй. Их легко расположить каскадом, чтобы сложить два 16-битных числа.
Выход для переноса правого сумматора связан со входом для переноса левого. Левый сумматор в качестве входных значений принимает самые старшие восемь цифр двух слагаемых и в качестве выходного значения выдает самые старшие восемь цифр.
Теперь вы можете спросить: «Неужели компьютеры действительно складывают числа именно так?»
В принципе да. Но не совсем.
Во-первых, сумматоры могут быть быстрее тех, которые мы описали. Если вы посмотрите на то, как работает эта схема, то поймете, что выход переноса от младшей пары цифр необходим для сложения со следующей парой, выход переноса от второй пары цифр – для сложения с третьей парой и т. д. Общая скорость сумматора равна количеству битов, умноженному на скорость одного полного сумматора. Это называется сквозным переносом. Быстрые сумматоры используют дополнительные схемы ускоренного переноса.
Во-вторых (и это самое главное), компьютерам больше не нужно реле! Однако первые цифровые компьютеры, созданные в начале 1930-х годов, использовали реле, позднее – вакуумные лампы. Современные компьютеры создаются на основе транзисторов. Транзисторы в основном функционируют так же, как и реле, однако (как мы увидим далее) они намного быстрее, компактнее, тише, дешевле и потребляют гораздо меньше энергии. Для построения 8-битного сумматора по-прежнему требуются 144 транзистора (или больше, если вы хотите заменить сквозной перенос схемой ускоренного переноса), однако при этом размер схемы микроскопический.
Глава 13. А как насчет вычитания?
Убедившись в том, что реле действительно можно соединить для сложения двоичных чисел, зададимся вопросом: «А как насчет вычитания?» Не бойтесь показаться смешным, задавая его. На самом деле вы довольно проницательны. Сложение и вычитание в некотором смысле дополняют друг друга, однако механика у этих операций разная. Сложение предполагает последовательное продвижение от крайнего правого столбца цифр до крайнего левого. Каждое значение, перенесенное из одного столбца, прибавляется к следующему. При вычитании мы ничего не переносим; мы заимствуем, а это действие предполагает использование довольно запутанного механизма.
Давайте рассмотрим типичную задачу на вычитание с заимствованием.
Начнем решение с крайнего правого столбца. Сначала мы замечаем, что 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.)
Шаг 2. Прибавить дополнение вычитаемого до единицы к уменьшаемому.
Шаг 3. Прибавить к результату 1.
Шаг 4. Вычесть 100000000 (что соответствует 256).
Результат эквивалентен десятичному числу 77.
Давайте попробуем еще раз, поменяв числа местами. В десятичной системе счисления задача на вычитание выглядит так.
В двоичной системе – так.
Шаг 1. Вычесть вычитаемое из 11111111, чтобы получить дополнение до единицы.
Шаг 2. Прибавить дополнение вычитаемого до единицы к уменьшаемому.
Теперь нужно как-то вычесть из результата число 11111111. Когда исходное вычитаемое меньше уменьшаемого, для этого достаточно прибавить 1 и вычесть 100000000. Однако эту операцию нельзя выполнить без заимствования. Вместо этого мы вычитаем результат из числа 11111111.
Опять же, такая стратегия на самом деле означает, что для получения результата мы выполняем простое инвертирование. Ответ снова равен 77, а на самом деле −77.
Теперь у нас есть необходимые знания для оснащения собранного в предыдущей главе сумматора функцией вычитания. Чтобы не слишком усложнять эту счетную машину, сделаем так, чтобы она выполняла вычитание только тогда, когда вычитаемое меньше уменьшаемого, когда в результате получается положительное число.
Основой этой счетной машины являлся 8-разрядный сумматор, собранный из логических вентилей.
Вероятно, вы помните, что входы с A0 по A7 и с B0 по B7 были подключены к переключателям, с помощью которых вводились два 8-битных числа, подлежащие сложению. Вход для переноса соединялся с землей, выходы с S0 по S7 – с восемью лампочками, отображающими результат сложения. Поскольку в итоге могло получиться 9-битное значение, выход для переноса был подключен к девятой лампочке.
Пульт управления выглядел так.
Положения переключателей на этом изображении соответствуют сложению чисел 183 (10110111) и 22 (00010110), в результате которого получается 205, или 11001101, что и отражено рядом лампочек.
Новый пульт управления для сложения и вычитания двух 8-битных чисел имеет несколько иной вид. Он предусматривает дополнительный переключатель, позволяющий выбрать между сложением и вычитанием.
Подписи подсказывают, что размыкание этого переключателя соответствует сложению, а замыкание – вычитанию. Кроме того, для отображения результатов используются только восемь крайних лампочек справа. Девятая лампочка обозначена словами «Переполнение/Исчезновение». Она загорается, когда полученное число не может быть представлено восемью лампочками. Так происходит, если в результате сложения получается число, превышающее 255 (это называется переполнением), или если результат вычитания – отрицательное число – исчезновение порядка, то есть если вычитаемое больше уменьшаемого.
Главное нововведение в счетной машине – схема, которая вычисляет дополнение до единицы для 8-битного числа. Напомним, что вычисление дополнения до единицы эквивалентно инвертированию битов, поэтому устройство для произведения этой операции могло бы состоять просто из восьми инверторов.
Проблема этой схемы заключается в том, что она всегда инвертирует поступающие в нее биты. Наша цель – создать машину, которая выполняет как сложение, так и вычитание, поэтому эта схема должна инвертировать биты только при выполнении вычитания. Вот более подходящая схема.
Сигнал «Инверсия» поступает на каждый из восьми вентилей Искл-ИЛИ (исключающее ИЛИ). Напомним, вентиль Искл-ИЛИ работает так.
Если сигнал «Инверсия» равен 0, то сигналы на восьми выходах вентилей Искл-ИЛИ совпадают с сигналами на их входах. Например, если на вход подается значение 01100001, то выходным значением также является 01100001. Если сигнал «Инверсия» равен 1, то восемь входных сигналов будут инвертированы. Если на вход подается значение 01100001, то выходное – 10011110.
Давайте поместим эти восемь вентилей Искл-ИЛИ в прямоугольник под названием «Дополнение до единицы».
Теперь устройство для дополнения числа до единицы, 8-битный сумматор и последний вентиль Искл-ИЛИ можно объединить в схему.
Обратите внимание на три сигнала, обозначенные как «Выч.». Они поступают от переключателя «Сложение/вычитание». Этот сигнал равен 0, если необходимо выполнить сложение, и 1, если вычитание. При вычитании сигналы на входах B (второй ряд переключателей) инвертируются схемой «Дополнение до единицы» перед попаданием в сумматор. Кроме того, при вычитании к результату сложения прибавляется 1 за счет подачи на вход сумматора CI (вход для переноса) значения 1. При сложении схема «Дополнение до единицы» не оказывает никакого эффекта, а вход CI равен 0.
Сигнал «Выч.» и выходной сигнал сумматора CO (выход для переноса) также подаются на вход вентиля Искл-ИЛИ, который используется для включения лампочки «Переполнение/Исчезновение». Если сигнал «Выч.» равен 0 (выполняется сложение), лампочка будет гореть при выходном сигнале сумматора CO, равном 1. Это означает, что результат сложения превышает 255.
При выполнении вычитания, когда вычитаемое (переключатели B) меньше уменьшаемого (переключатели A), выходной сигнал сумматора CO бывает равен 1. Это нормально и означает, что на последнем этапе необходимо вычесть 100000000. Таким образом, лампа «Переполнение/Исчезновение» горит только тогда, когда выход сумматора CO равен 0, то есть вычитаемое больше уменьшаемого и результат отрицательный. Описанная выше машина не предназначена для отображения отрицательных чисел.
Сейчас вы, вероятно, рады, что спросили: «А как насчет вычитания?»
В этой главе я говорил об отрицательных числах, но все еще не показал, как выглядят отрицательные двоичные числа. Вы можете предположить, что традиционный знак «–» используется с двоичными числами так же, как и с десятичными. Например, число –77 в двоичном формате записывается –1001101. Конечно, вы можете так его записать, однако одна из целей использования двоичных чисел заключается в том, чтобы представлять всё с помощью нулей и единиц, включая такие символы, как «–» перед отрицательным числом.
Можно просто использовать еще один бит для знака «–». Его значение 1 может соответствовать отрицательному числу, а 0 – положительному, и это будет работать, хотя мало что даст. Существует еще одно решение для представления отрицательных чисел, которое также предусматривает простой способ сложения отрицательных и положительных чисел. Недостаток этого метода – необходимость заранее решить, сколько цифр требуется для представления чисел, с которыми мы будем работать.
Давайте подумаем. Преимущество обычного способа представления положительных и отрицательных чисел заключается в том, что они могут иметь бесконечную длину. Мы представляем 0 как точку, от которой в одну сторону в бесконечность уходят положительные числа, а в другую – отрицательные.
… –1 000 000–999 999 … – 3–2 –1 0 1 2 3 … 999 999 1 000 000 …
Однако представьте, что нам не нужно бесконечное количество чисел: с самого начала известно, что каждое число, которое встретится, будет находиться в определенном диапазоне.
Рассмотрим чековый банковский счет, в котором мы иногда сталкиваемся с отрицательными числами. Предположим, что баланс нашего счета никогда не превышал 500 долларов, и банк установил лимит перерасхода на те же 500 долларов. Это значит, что баланс нашего счета всегда находится в диапазоне от 499 до – 500 долларов. При этом мы никогда не кладем на счет более 499 долларов, никогда не выписываем чек на сумму более 500 долларов и имеем дело только с долларами, центы же не учитываем.
Этот набор условий указывает, что при использовании нашего счета мы имеем дело с числами в диапазоне от – 500 до 499. Это всего 1000 чисел. Такое ограничение подразумевает, что для представления всех нужных чисел мы должны использовать только три десятичные цифры и обходиться без знака «–». Хитрость в том, что нам не нужны положительные числа от 500 до 999, поскольку мы уже решили, что максимальным положительным числом для нас является 499. Таким образом, трехзначные числа от 500 до 999 фактически можно использовать для представления отрицательных чисел. Вот как это работает.
Вместо –500 используем 500.
Вместо –499 используем 501.
Вместо –498 используем 502.
…
Вместо –2 используем 998.
Вместо –1 используем 999.
Вместо 0 используем 000.
Вместо 1 используем 001.
Вместо 2 используем 002.
…
Вместо 497 используем 497.
Вместо 498 используем 498.
Вместо 499 используем 499.
Другими словами, каждое трехзначное число, которое начинается с цифры 5, 6, 7, 8 или 9, фактически является отрицательным. Вместо того чтобы записывать эти числа как:
– 500–499 –498 … – 4–3 –2–1 0 1 2 3 4 … 497 498 499,
запишем их:
500 501 502 … 996 997 998 999 000 001 002 003 004 … 497 498 499.
Обратите внимание: числа идут по кругу. Наименьшее отрицательное число (500) как бы следует за наибольшим положительным числом (499). А число 999 (которое фактически равно –1) на единицу меньше нуля. Если мы прибавим 1 к 999, то в обычных условиях получим 1000. Но поскольку мы имеем дело только с тремя цифрами, в результате будет 000.
Такой способ записи отрицательных чисел называется дополнением до десяти. Чтобы преобразовать трехзначное отрицательное число в дополнение до десяти, вычитаем его из 999 и прибавляем 1. Другими словами, дополнение до десяти – это дополнение до девяти плюс один. Например, чтобы найти дополнение числа –255 до десяти, нужно вычесть его из 999, получив 744, а затем прибавить 1, что в результате даст 745.
Вероятно, вы слышали утверждение, что вычитание – это просто прибавление отрицательных чисел. На что вы, вероятно, отвечали: «Да, но числа все равно приходится вычитать». Используя дополнение до десяти, вы вообще ничего не вычитаете. Все сводится к сложению.
Предположим, у вас на счету 143 доллара. Вы выписываете чек на 78 долларов. Это означает, что вы должны прибавить –78 к 143. Дополнение числа –78 до десяти равно 999–078 + 1, то есть 922. Таким образом, ваш баланс теперь составляет 143 + 922, или 65 долларов (без учета переполнения). Если после этого вы выпишете чек на 150 долларов, придется прибавить число –150, дополнение которого до десяти равно 850. Итак, прибавим 850 к предыдущему балансу 065 и получим 915 – новый баланс. Это число фактически эквивалентно –85.
В двоичном формате подобная система называется дополнением до двух. Предположим, что мы работаем с 8-битными числами в диапазоне от 00000000 до 11111111, которые соответствуют десятичным числам от 0 до 255. Если вам требуется использовать отрицательные числа, то каждое 8-битное число, начинающееся с 1, фактически будет отрицательным:
Внимание! Это не конец книги.
Если начало книги вам понравилось, то полную версию можно приобрести у нашего партнёра - распространителя легального контента. Поддержите автора!Правообладателям!
Данное произведение размещено по согласованию с ООО "ЛитРес" (20% исходного текста). Если размещение книги нарушает чьи-либо права, то сообщите об этом.Читателям!
Оплатили, но не знаете что делать дальше?
