Москва 2001 г тайный язык информатики Чарльз Петцольд ббк 32. 973. 26–018

170

Глава тринадцатая

253

–176

77

Как нам заставить набор вентилей разобраться в столь за-

путанной логике?

На самом деле, не стоит даже пробовать. Вместо этого мы

прибегнем к небольшой хитрости, которая позволит выпол-

нять вычитание без заимствования. Это порадовало бы Поло-

ния («Не занимай и не ссужай», — напутствовал он Лаэрта) да

и всех остальных. Кроме того, подробное исследование этого

способа вычитания полезно и с теоретической точки зрения,

так как он напрямую связан с методикой хранения двоичных

отрицательных чисел в компьютерах.

Для начала вспомним, что числа, участвующие в вычита-

нии, называются  уменьшаемым и  вычитаемым. Вычитаемое

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

Уменьшаемое

–Вычитаемое

Разность

Чтобы обойтись в вычитании без заимствования, во-пер-

вых, вычтем вычитаемое не из уменьшаемого, а из 999:

999

–176

823

Здесь мы используем 999, поскольку вычитаемое является трех-

значным числом. Если бы оно было четырехзначным, мы выч-

ли бы его из 9999. Результат вычитания числа из строки девя-

ток называется  дополнением до девяти (nines’ complement).

Дополнение до девяти числа 176 есть 823. Верно и обратное:

дополнение до девяти числа 823 есть 176. И что приятно: ка-

ким бы ни было вычитаемое, вычисление его дополнения до

девяти никогда не требует заимствования.

Вычислив дополнение числа до девяти, прибавьте к нему

уменьшаемое:

253

+823

1076

171

А как же вычитание?

Наконец, сложите результат с 1 и вычтите 1000:

1076

+1

–1000

77

Готово. Мы получили тот же результат, что и раньше, без еди-

ного заимствования.

Как это получилось? Исходная задача на вычитание выгля-

дит так:

253 – 176

К этому выражению можно прибавить и вычесть любое число

— результат от этого не изменится. Прибавим и вычтем 1000.

253 – 176 + 1000 – 1000

Это выражение эквивалентно выражению

253 – 176 + 999 + 1 – 1000

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

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

Это как раз и есть тот расчет, что я провел, используя допол-

нение вычитаемого до девяти. Мы заменили одно вычитание

двумя вычитаниями и двумя сложениями, попутно освободив-

шись от всех заимствований.

Что делать, если вычитаемое больше уменьшаемого? Ведь

задача на вычитание может выглядеть и так:

176

–253

???

Опытный математик, глядя на это, говорит: «Хммм. Я вижу, что

вычитаемое больше уменьшаемого. Я меняю числа местами и

произвожу вычитание, помня при этом, что результат будет

отрицательным». Ответ записывается следующим образом:

176

–253

–77

172

Глава тринадцатая

Чтобы выполнить такой расчет без заимствования, придет-

ся поступить несколько иначе, чем в предыдущем примере.

Начинаем опять с вычисления дополнения вычитаемого (253)

до девяти:

999

–253

746

Теперь складываем дополнение до девяти с уменьшаемым:

176

+746

922

В предыдущей задаче на этом этапе нужно было прибавить 1

и вычесть 1000, чтобы получить окончательный ответ. В дан-

ном случае эта стратегия не сработает. Пришлось бы вычесть

1000 из 923, а это в реальности оборачивается вычитанием 923

из 1000 и требует заимствований.

На самом деле, вычисляя дополнение вычитаемого до де-

вяти, мы фактически прибавили к нему 999, поэтому теперь

будем вычитать 999:

922

–999

???

Глядя на этот пример, мы понимаем, что ответ будет отрица-

тельным. Поэтому числа нужно поменять местами и вычесть

922 из 999. Это действие снова не требует заимствования. От-

вет, как мы и ожидали, равен –77:

922

–999

77

При вычитании двоичных чисел используется точно такой

же метод. Более того, он проще, чем в десятичном случае. По-

смотрим, как он работает.

Вот как выглядит наша задача на вычитание:

253

–176

???

173

А как же вычитание?

Записав эти числа в двоичном представлении, получаем зада-

чу такого вида:

11111101

–10110000

?????????

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

11111111

–10110000

01001111

Когда мы работали с десятичными числами, вычитаемое вы-

читалось из строки девяток, а результат назывался дополне-

нием до девяти. При расчетах с двоичными числами вычитае-

мое вычитается из строки единиц, и результат называется до-

полнением до единицы (ones’ complement). Но заметьте, чтобы

получить дополнение до единицы, вычитать на самом деле не

нужно. И вот почему: каждый 0 в исходном числе становится

1 в дополнении, а каждая 1 превращается в 0. Именно поэтому

дополнение до единицы иногда также называют отрицанием

(negation) или инверсией (inversion). Здесь уместно вспомнить,

что в главе 11 мы встречались с инвертором, который как раз

и меняет 0 на 1, а 1 на 0.

Шаг 2. Складываем дополнение вычитаемого до 1 с умень-

шаемым.

11111101

+01001111

101001100

Шаг 3. Прибавляем к результату 1.

101001100

+1

101001101

Шаг 4. Вычитаем 100000000 (т. е. 256).

101001101

–100000000

1001101

174

Глава тринадцатая

Этот результат соответствует десятичному числу 77.

Теперь повторим последовательность действий, выполнен-

ных для тех же чисел, но с заменой вычитаемого на уменьша-

емое. В десятичном виде эта задача записывалась так:

176

–253

???

В двоичном она выглядит так:

10110000

–11111101

?????????

Шаг 1. Вычитаем вычитаемое из 11111111, чтобы получить

его дополнение до единицы.

11111111

–11111101

00000010

Шаг 2. Прибавляем дополнение вычитаемого до единицы

к уменьшаемому.

10110000

–00000010

10110010

Теперь из результата нужно вычесть 11111111. Когда вы-

читаемое было меньше уменьшаемого, эта задача решалась

добавлением 1 и вычитанием 100000000. Теперь сделать это

без заимствования не удастся, поэтому мы вычитаем получен-

ный результат из 11111111:

11111111

–10110010

01001101

Как и ранее, это действие эквивалентно инвертированию.

В ответе получилось 77, но мы помним, что в действительнос-

ти это –77.

Теперь у нас есть все необходимые познания для модерни-

зации сумматора из предыдущей главы, чтобы он выполнял

не только сложение, но и вычитание. Чтобы не слишком ус-

175

А как же вычитание?

ложнять задачу, наша новая суммирующая и вычитающая

машина будет выполнять вычитание, только когда вычитае-

мое меньше уменьшаемого, т. е. когда результат положителен.

Основой суммирующей машины был 8-битовый сумма-

тор, собранный из логических вентилей:

Выход для переноса

8-битовый сумматор

Вход 

для 

переноса

Вход А

Вход В

Выход для суммы

CO

CI

A

7

...A

0

B

7

...B

0

S

7

...S

0

Как вы помните, входы с A

7

 по A

0

 и с B

7

 по B

0

 соединялись с

переключателями, задававшими два 8-битовых слагаемых. Вход

для переноса соединялся с землей. Выходы с S

7

 по S

0

 соединя-

лись с 8 лампочками, отображавшими результат сложения. По-

скольку результатом сложения могла быть 9-битовая величина,

выход для переноса соединялся с девятой лампочкой.

Пульт управления сумматором выглядел примерно так:

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

На этом рисунке переключатели установлены в положения,

соответствующие сложению 183 (10110111) и 22 (00010110).

Результат сложения, о чем свидетельствуют лампочки, равен

205 (11001101).

176

Глава тринадцатая

Вид пульта управления для сложения или вычитания двух

8-битовых чисел слегка иной. На нем появился дополнитель-

ный переключатель, с помощью которого можно задать дей-

ствие — вычитание или сложение.

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

Вычитание

Сложение

Переполнение/

Исчезновение

Если этот переключатель разомкнут, производится сложение,

если замкнут — вычитание. Кроме того, теперь для отображе-

ния результата используются только правые 8 лампочек. Де-

вятая лампочка подписана «Переполнение/Исчезновение». Она

сигнализирует, что вычисленное число не может быть пред-

ставлено только 8 лампочками. Это происходит, если сумма

больше 255 (переполнение разрядов) или если разность оказа-

лась отрицательной (исчезновение разрядов).

Основным новшеством в сумматоре станет схема, которая

вычисляет дополнение 8-разрядного числа до единицы. Как

вы помните, это эквивалентно инвертированию битов, так что

для вычисления дополнения 8-разрядного числа до единицы

можно использовать просто 8 инверторов.

Входы

Выходы

Но эта схема всегда инвертирует биты, поступающие на ее вхо-

ды, а в машине для сложения и вычитания нам нужно устрой-

177

А как же вычитание?

ство, которое инвертировало бы биты, только если произво-

дится вычитание. Более подходящая схема выглядит так:

Выходы

Входы

Инверсия

Сигнал Инверсия подается на входы всех девяти вентилей

Искл-ИЛИ. Напомню, что вентиль Искл-ИЛИ работает так:

Искл-ИЛИ

0

1

0

0

1

1

1

0

Если сигнал Инверсия равен 0, восемь выходов вентилей

Искл-ИЛИ повторяют сигнал на восьми их входах. Например,

если на вход подается число 01100001, на выходе также будет

01100001. Если же сигнал Инверсия равен 1, восемь входных

сигналов будут инвертироваться. Если на входе 01100001, на

выходе имеем 10011110.

Давайте поместим восемь вентилей Искл-ИЛИ в общий

прямоугольник под названием дополнение до единицы (ones’

complement):

Инверсия

Дополнение до единицы

Вх

7

Вх

6

Вх

5

Вх

4

Вх

3

Вх

2

Вх

1

Вх

0

Вых

7

Вых

6

Вых

5

Вых

4

Вых

3

Вых

2

Вых

1

Вых

0

Теперь вентиль «дополнение до единицы», 8-битовый сумматор

и выходной вентиль Искл-ИЛИ можно собрать в единую схему:

178

Глава тринадцатая

Выч

Выч

CO

8-битовый сумматор

CI

Вход А

Вход В

Выход для суммы

Инверсия

Дополнение до единицы

Выч

Переполнение/

Исчезновение

A

7

...A

0

B

7

...B

0

S

7

...S

0

Обратите внимание на сигнал Выч, идущий с переключа-

теля «Сложение/Вычитание». Этот сигнал равен 0, если нужно

выполнить сложение, и 1, если нужно выполнить вычитание.

При вычитании входы В (второй ряд переключателей) перед

сумматором инвертируются схемой «дополнение до единицы»,

а к результату сумматора прибавляется 1, для чего его вход CI

установлен в 1. При сложении схема «дополнение до едини-

цы» не делает ничего; сигнал на входе CI равен 0.

Сигнал Выч и выход CO (выход для переноса) сумматора

также поступают в вентиль Искл-ИЛИ, который управляет

включением лампочки «Переполнение/Исчезновение». При

равенстве 0 сигнала Выч (выполняется сложение) лампочка

горит, если сигнал CO сумматора равен 1, т. е. результат сло-

жения оказался больше 255.

Пусть вас не смущает, что выход CO сумматора равен 1,

если выполняется вычитание и вычитаемое (переключатели

B) меньше уменьшаемого (переключатели А). Так проявляет-

ся число 100000000, которое в этом случае должно вычитаться

на заключительном шаге. Лампочка «Переполнение/Исчезно-

вение» горит, только если выход CO сумматора равен 0. Это

179

А как же вычитание?

означает, что вычитаемое больше уменьшаемого и результат

отрицателен. Отображение отрицательных чисел в нашем ус-

тройстве не предусмотрено.

Теперь вы, верно, радуетесь, что спросили: «А как же вы-

читание?»

Я в этой главе уже неоднократно говорил об отрицатель-

ных числах, но все еще не показал, на что они похожи в двоич-

ном представлении. Можно, конечно, обозначать отрицатель-

ные двоичные числа знаком «минус», как и в десятичной сис-

теме, скажем, записать число –77 как –1001101. Но одна из це-

лей введения двоичных чисел в том, чтобы представлять в виде

нулей и единиц все что угодно, в том числе и знак «минус» пе-

ред отрицательным числом.

Признаком знака может служить и дополнительный бит,

который, например, равнялся бы 1 у отрицательных чисел и 0

у положительных. Однако есть другой способ представления

отрицательных чисел, который позволяет без особых хлопот

складывать отрицательные и положительные числа. Недоста-

ток его лишь в том, что вы должны заранее решить, сколько

цифр понадобится для представления чисел, с которыми вам

предстоит иметь дело.

Давайте малость подумаем. Преимущество стандартного

способа записи положительных и отрицательных чисел в том,

что он не накладывает никаких ограничений на их величины.

Как отрицательные, так и положительные числа расходятся от

0 до бесконечности.

… –1000000 –999999 … –3 –2 –1 0 1 2 3 … 999999

1000000 …

Но допустим, что бесконечный числовой ряд нам не ну-

жен, так как мы заранее знаем, что все числа, с которыми мы

столкнемся, заключены в определенных пределах.

Рассмотрим в качестве примера чековый банковский счет,

где нам иногда приходится на практике сталкиваться с отри-

цательными числами. Предположим, что мы никогда не дер-

жали на счете больше 500 долларов и что банк разрешает крат-

ковременный перерасход также на 500 долларов. Это значит,

что баланс нашего чекового счета всегда заключен между 499

долларами и –500 долларами. Допустим также, что мы никог-

да не вносим на счет больше 500 долларов, никогда не выпи-

180

Глава тринадцатая

сываем чеки больше, чем на 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) на единицу

меньше 0. Если прибавить к 999 единицу, мы получим 1000,

181

А как же вычитание?

но поскольку мы имеем дело только с тремя цифрами, в дей-

ствительности получаем 000.

Такой способ обозначения отрицательных чисел называ-

ется дополнением до десяти (ten’s complement). Чтобы преоб-

разовать трехзначное отрицательное число в дополнение до

10, вычитаем его из 999 и добавляем 1. Иными словами, до-

полнение до десяти — это дополнение до девяти плюс 1. На-

пример, чтобы переделать –255 в дополнение до десяти, выч-

тем его из 999, получив 744, и прибавим 1, что дает 745.

Вам, вероятно, приходилось слышать, что «вычитание —

это просто сложение с отрицательным числом». На это вы ско-

рее всего отвечали: «Да, но при этом оно остается вычитани-

ем». Дополнение до десяти позволяет избавиться от вычита-

ния, полностью заменив его сложением.

Пусть на вашем счете 143 доллара. Вы выписали чек на 78

долларов. Это означает, что к 143 нужно прибавить –78. До-

полнение –78 до десяти равно 999 – 078 + 1, или 922. Таким

образом, ваш баланс составляет 143 + 922, что равно 65 долла-

рам (без учета переполнения). Если вы после этого выпишете

чек на 150 долларов, то должны будете прибавить к балансу

число –150, дополнение которого до десяти равно 850. Сумма

предыдущего баланса 065 и 850 равна 915. В обычном пред-

ставлении число 915 эквивалентно –85 долларам — вашему

новому балансу.

Аналогичная система в двоичном счислении называется

дополнением до двух (two’s complement). Предположим, что мы

работаем только с 8-битовыми числами, заключенными в пре-

делах от 00000000 до 11111111, или от 0 до 255 в десятичной

системе. Чтобы отображать с их помощью также и отрицатель-

ные числа, придется отдать в отрицательную область все 8-

битовые числа, начинающиеся с 1, как показано в таблице.

Двоичное

Десятичное

10000000

–128

10000001

–127

10000010

–126

10000011

–125

…

11111101

–3

182

Глава тринадцатая

Двоичное

Десятичное

11111110

–2

11111111

–1

00000000

0

00000001

1

00000010

2

…

01111100

124

01111101

125

01111110

126

01111111

127

Диапазон чисел, которые вы теперь можете представить, огра-

ничен пределами от –128 до +127. Старший значащий бит

(крайний слева) называется знаковым разрядом (sign bit). Зна-

ковый разряд равен 1 для отрицательных чисел и 0 для поло-

жительных.

Чтобы вычислить дополнение до двух, нужно посчитать

дополнение до единицы и прибавить 1 или, что эквивалентно,

инвертировать все цифры и прибавить 1. Например, десятич-

ное число 125 в двоичной системе выглядит как 01111101. Что-

бы представить –125 в виде дополнения до двух, инвертируем

цифры в числе 01111101, получая в результате 10000010, а за-

тем прибавляем единицу, что дает 10000011. Проверьте резуль-

тат по таблице. Чтобы проделать обратную операцию, нужно

сделать то же самое — инвертировать все биты и прибавить 1.

Эта система позволяет выражать положительные и отри-

цательные числа без знака «минус», а также складывать поло-

жительные и отрицательные числа, используя только правила

сложения. Давайте в качестве примера сложим двоичные эк-

виваленты –127 и 124. Используя предыдущую таблицу как

шпаргалку, запишем

10000001

+01111100

11111101

Этот результат эквивалентен десятичному числу –3.

(продолжение)

183

А как же вычитание?

При этом необходимо следить за переполнением или ис-

чезновением разрядов. Такое случится, если результат сложе-

ния окажется больше 127 или меньше –128. Допустим, мы хо-

тим сложить число 125 с ним самим.

01111101

+01111101

11111010

Старший бит равен 1, т. е. результат интерпретируется как от-

рицательное число и становится равным –6. То же самое про-

исходит, если с самим собой вы сложите число –125.

10000011

+10000011

100000110

Мы условились в начале, что ограничимся 8-битовыми числа-

ми, поэтому крайнюю левую цифру результата приходится

игнорировать. Правые же 8 битов эквивалентны +6.

Вообще результат сложения положительных и отрицатель-

ных чисел неверен, если знаковые разряды двух операндов

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

Итак, есть два способа использования двоичных чисел.

Двоичное число может быть со знаком (signed) или без знака

(unsigned). 8-битовые числа без знака попадают в диапазон от

0 до 255. 8-битовые числа со знаком попадают в диапазон от

–128 до 127. Только по виду числа вы не сможете определить,

является оно числом со знаком или без знака. Например, кто-

то скажет вам: «У меня есть 8-битовое двоичное число, равное

10110110. Каков его десятичный эквивалент?» Вам придется

осведомиться: «Со знаком или без знака? Это может быть либо

–74, либо 182».

Вот такие они, биты — всего лишь нули и единицы, кото-

рые ничего не говорят вам о себе.

жүктеу/скачать 3,29 Mb.

Достарыңызбен бөлісу: