Двоичная целочисленная арифметика

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

Двоичная и шестнадцатиричная системы счисления

Двоичная система счисления. Наша десятичная система счисления является позиционной в том смысле, что величина числа зависит от порядка цифр в нем. Например, число 534.686 в 10 раз больше, чем

53.4686, поскольку позиции одних и тех же цифр относительно десятичной точки различны. На самом деле, когда мы пишем 534.686, мы имеем в виду число

Статья 358 - Картинка 1

Положение цифры относительно десятичной точки определяет степень числа 10, на которую эта цифра будет умножена при вычислении суммы.

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

То, что мы используем десятичную систему, до некоторой степени является случайностью. Если бы у человека было 8 пальцев, а не 10, мы, вероятно, использовали бы восьмеричную систему, что, надо отметить, облегчило бы изобретение вычислительных машин и их изучение.

Информация в большинстве современных ЭВМ хранится и обрабатывается в двоичной форме. В двоичной системе существует всего две цифры, или бита, 0 и 1. Одной из причин использования именно этой системы в программировании является то, что обычные электронные переключатели могут находиться только в одном из двух состояний — включенном или выключенном. Кроме того, логика, которую мы используем, по своему существу является двоичной логикой: любое предложение в ней либо истинно, либо ложно. Таким образом, мы употребляем биты для обозначения 1 или 0, состояний «включено» или «выключено», истины или лжи.

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

Поскольку основанием двоичной системы является число 2, мы можем определить десятичное значение двоичного числа, расписывая двоичное число в виде суммы степеней двойки и вычисляя полученную сумму, используя десятичную арифметику. Например, для преобразования числа

11011.1001

в десятичную форму можно записать Статья 358 - Картинка 2

В результате мы получили

Статья 358 - Картинка 3

Иными словами, система, в которой записано число, определяется подстрочным указанием основания этой системы в конце числа.

Теперь рассмотрим обратное преобразованием дано десятичное число. Как перевести его в двоичную форму? Предлагаемый алгоритм очень напоминает алгоритм деления в столбик и может быть хорошо проиллюстрирован на примере.

Мы хотим перевести число Статья 358 - Картинка 4 в его двоичный эквивалент. Выполним преобразование в две стадии, преобразуя целую и дробную части исходного числа по отдельности.

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

Статья 358 - Картинка 5

Теперь для получения результата осталось лишь записать остатки в порядке «снизу вверх». Получим

Статья 358 - Картинка 6

(Проверьте этот результат, проделав обратное преобразование.)

Для соответствующего преобразования десятичной дроби в двоичную мы последовательно будем умножать десятичную дробь на 2, записывая 1 каждый раз при получении числа, по модулю большего 1 (перенос в целую часть), и 0 в противном случае. При последующих умножениях используется только дробная часть полученного числа. В нашем примере мы имеем Статья 358 - Картинка 7

Очевидно, этот процесс можно продолжить до бесконечности; двоичное представление десятичного числаСтатья 358 - Картинка 8является периодической дробью. Для получения ответа необходимо выписать все переносы в порядке «сверху вниз». То есть

Статья 358 - Картинка 9

и в конечном итоге мы получаем Статья 358 - Картинка 10

с бесконечной дробной частью.

Замечание по поводу полученного результата. Большинство десятичных дробей, например, такие, как 1, 2, 06, не могут быть представлены в виде конечных двоичных. Но ЭВМ оперируют лишь числами, представленными конечными наборами цифр. Это ведет к неизбежным ошибкам округления, возникающим при отбрасывании младших разрядов числа, необходимом для записи его в виде конечного машинного слова.

Чем больше разрядов используется для представления дробей, тем больше точность получаемого приближения. Так, используя всего 4 двоичных разряда для представления числа 2, мы имели бы

Статья 358 - Картинка 11

при использовании 8 битов мы получаем более точный результат

Статья 358 - Картинка 12

Шестнадцатеричная система счисления. Вы могли уже заметить, что перевод в двоичную систему несколько утомителен; для представления десятичной дроби в двоичном виде требуется приблизительно в три раза больше цифр. Поэтому для краткой записи двоичной информации в программировании используется система с большим основанием. Главным требованием, предъявляемым к такой системе, является то, что перевод из этой системы в двоичную и обратно должен быть достаточно прост, т. е. эта система и двоичная должны быть в некотором смысле эквивалентны.

Статья 358 - Картинка 13

Шестнадцатеричная система, или система с основанием 16, обладает этим свойством и широко используется в тех случаях, когда двоичная информация легко представима в виде групп по 4 бита в каждой. Поскольку основание системы равно 16, то в ней должны существовать 16 различных цифр. У нас есть 10 цифр нашей десятичной системы счисления, их мы и используем в качестве первых 10 цифр шестнадцатеричной системы. В качестве остальных шести цифр мы используем буквыА, В, С, D, Е, F.

На рис. 2.1 изображены первые десятичные числа и их двоичное и шестнадцатеричное представление. Отметим, что каждое 4-разрядное двоичное число соответствует определенной цифре шестнадцатеричной системы. Именно это позволяет легко проводить преобразования из одной системы в другую. Для преобразования двоичного числа в шестнадцатеричное нужно разбить двоичное число на группы, по 4 бита в каждой, двигаясь вправо и влево от десятичной точки. Затем нужно добавить к крайним группам нули для дополнения их до 4 разрядов,

Десят.

Двоичн.

Шестн.

0

0000

0

1

0001

1

2

0010

2

3

0011

3

4

0100

4

5

0101

5

6

0110

6

7

0111

7

8

1000

8

9

1001

9

10

1010

А

11

1011

в

12

1100

С.

13

1101

D

14

1110

Е

15

1111

F

16

10000

10

17

10001

11

18

10010

12

19

10011

13

20

10100

14

Рис. 2.1. Десятичные, двоичные и шестнадцатеричные числа.

если это потребуется. Например, для преобразования Статья 358 - Картинка 14

в шестнадцатеричное, нужно записать

Статья 358 - Картинка 15

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

Статья 358 - Картинка 16

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

Статья 358 - Картинка 17

Процесс преобразования из шестнадцатеричной системы в десятичную может быть осуществлен расписыванием исходного числа по степеням 16 и вычислением полученной суммы в десятичной системе. Так

Статья 358 - Картинка 18

Наконец, перевод десятичного целого в шестнадцатеричное может быть выполнен примерно так же, как и перевод десятичного целого в двоичное; разница заключается в том, что на каждом шаге мы делим десятичное число на 16 и записываем остатки в шестнадцатеричном виде.

Вот процесс перевода 638.0 в шестнадцатеричную форму:

Статья 358 - Картинка 19

И в результате получаем

Статья 358 - Картинка 20

Для перевода десятичной дроби в шестнадцатеричную форму обычно используется та же процедура, которую мы использовали для перевода десятичной дроби в двоичную, только теперь умножение производится на 16 и числа, получающиеся в целой части при умножении, записываются в шестнадцатеричной форме.

Умножение и деление на 16 гораздо более сложны, чем умножение и деление на 2. Поэтому для перевода десятичного числа в шестнадцатеричное гораздо удобнее сначала перевести десятичное число в двоичное и лишь затем перевести результат в шестнадцатеричную форму. Наиболее же просто можно произвести преобразования из десятичной системы в шестнадцатеричную, используя таблицы приложения 4 или справочные карты фирмы IBM.

Двоичная арифметика в дополнительных кодах

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

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

Статья 358 - Картинка 21

Если справедливость результатов таблицы вызывает сомнения, переведите все числа в десятичную систему, выполните указанные сложения и вновь переведите результаты в двоичную систему (это вообще один из возможных методов реализации двоичной арифметики). Сложим два двоичных целых

Статья 358 - Картинка 22

и

Статья 358 - Картинка 23

Получим

Статья 358 - Картинка 24

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

Статья 358 - Картинка 25

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

При проверке и отладке программ на языке ассемблера часто требуется сложение пар шестнадцатеричных чисел. При этом используется тот же алгоритм, что и в десятичной системе, только необходимо иметь в виду, что Статья 358 - Картинка 26, т. е. если имеет место перенос, то переносится число 16, а не 10. Рассмотрим простой пример и вычислим

Статья 358 - Картинка 27

Совершенно верным (и наиболее часто используемым опытными программистами) способом является следующий: шестнадцатеричные числа переводятся по столбцам в десятичные, выполняется сложение, и результат снова приводится к шестнадцатеричному виду с переносом единиц в старший разряд, если полученная сумма больше (десятичного) 16. Возвращаясь к нашему примеру, мы должны рассуждать так: «Статья 358 - Картинка 28естьСтатья 358 - Картинка 29,Статья 358 - Картинка 30естьСтатья 358 - Картинка 31, сумма равнаСтатья 358 - Картинка 32. Далее,Статья 358 - Картинка 33 больше Статья 358 - Картинка 34, поэтому мы должны вычесть из результатаСтатья 358 - Картинка 35, получим 2, но теперь необходимо произвести перенос 1, компенсируя таким образом вычитание 16». Рассмотрим более сложный пример: Статья 358 - Картинка 36

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

Статья 358 - Картинка 37

Статья 358 - Картинка 38

Мы могли бы так же использовать методы вычисления в десятичной системе для вычитания двоичных и шестнадцатеричных чисел. Необходимо было бы только помнить, что, занимая единицу старшего разряда для вычитания, мы занимаем соответственно 2 и 16, а не 10. Тем не менее на современных вычислительных машинах, и в частности на машинах Систем 360 и 370, операция вычитания выполняется совсем по-другому. Поскольку в дальнейшем мы будем тесно связаны с машинной арифметикой, познакомимся поближе с машинными методами выполнения арифметических операций.

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

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

В Системе 360 числа обычно хранятся и обрабатываются в форме полных слов. Каждое слово состоит из 32 двоичных разрядов, или битов. Таким образом, реальным содержимым ячейки, содержащей, например, число 5, будет

Статья 358 - Картинка 39

Отметим также, что мы можем представить содержимое ячейки в форме шестнадцатеричного числа, в нашем случае

00000005

Для представления отрицательных чисел используется так называемый дополнительный код. Покажем теперь, как определить дополнительный код для заданного числа и как выполняется сложение с его использованием. После этого будет показано, как можно применить это понятие при выполнении арифметических операций над целыми числами со знаками.

Для вычисления дополнительного кода целого числа получим сначала его логическое дополнение. Логическое дополнение (обратный код) числа получается заменой каждой 1 в машинном представлении этого числа на 0 и каждого 0 на 1. Терминология станет ясной, как только вы поймете, что логическим дополнением истины является ложь, и наоборот.

Таким образом, логическим дополнением слова 11010101110110100011100001010111

является слово

00101010001001011100011110101000

Дополнительный код целого числа получается добавлением 1 к обратному коду этого числа, т. е.

дополнительный код = обратный код + 1

Возвращаясь к нашему предыдущему примеру, мы увидим, что дополнительный код для слова, содержащего число 5, вычисляется так:

Статья 358 - Картинка 40

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

Статья 358 - Картинка 41

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

Утверждается, что дополнительный код некоторого числа при выполнении арифметических операций, если, конечно, эти операции выполняются правильно, ведет себя так же, как это число, взятое с обратным знаком. Продемонстрируем это на примере вычисления разности 13—13 с использованием дополнительного кода. Имеем Статья 358 - Картинка 42 в виде полного машинного слова, тогда как дополнительным кодом числа 13 (проверьте) является Статья 358 - Картинка 43

опять же в 32-разрядном машинном представлении.

Вычислим теперь сумму

Статья 358 - Картинка 44

Мы получили правильный ответ 0, но как быть с последней переносимой единицей, не умещающейся в 32-разрядное машинное слово? Ответ на этот вопрос таков:

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

Отсюда мы заключаем, что дополнительный код числа при выполнении арифметических операций ведет себя как это же число, взятое с обратным знаком. Почему это на самом деле так, легко понять, взглянув на вопрос с несколько иной точки зрения. Предположим, что мы имеем двоичное число А. Легко видеть, что дополнительный код Статья 358 - Картинка 45

В двоичном видеСтатья 358 - Картинка 46записывается как 1 с 32 нулями. Пытаясь теперь представитьСтатья 358 - Картинка 47в виде машинного слова, мы получим 32 нуля и 1, не вошедшую в разрядную сетку. Отбрасывая 1, мы получим, чтоСтатья 358 - Картинка 48представляется машинным 0. Теперь для вычисленияВ — А можно формально записать

1

Статья 358 - Картинка 49

Математик сказал бы нам, что наша арифметика в дополнительных кодах для 32-разрядных чисел есть не что иное, как арифметика по модулюСтатья 358 - Картинка 50

Абсолютная величина двоичного числа. Для суммирующей схемы не существует разницы между сложением и вычитанием. Знак операции определяют сами числа, подающиеся на вход схемы. Если второй операнд на самом деле является лишь дополнительным кодом истинного, результатом сложения будет разность двух чисел. Однако во многих других случаях, и в частности при интерпретации результатов арифметических операций, необходимо различать положительные и отрицательные числа и быть в состоянии вычислить их абсолютные значения, или модули.

Для определения знака числа необходимо посмотреть на первый(0-й) бит, или, как его часто называют, знаковый разряд числа. Если 1 знаковый разряд равен 0, то число положительно, т. е. если мы добавим его к другому числу, то результат будет больше исходного числа. Абсолютной величиной такого числа является просто оно само.

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

Абсолютной величиной отрицательного числа является его представление в дополнительном коде. В заключение надо сказать, что модуль числаА есть не что иное, как его абсолютная величина | А |.

ЕслиА — число, записанное в машинной форме, то

Статья 358 - Картинка 51

Переполнение. Мы видели, что в машине двоичные числа представлены в форме слов, содержащих 31 разряд и один знаковый разряд. Но что произойдет при сложении чисел, сумма которых не помещается в машинное слово, т. е. модуль которой больше чемСтатья 358 - Картинка 52—1? В этом

случае обычно фиксируется ошибка, ситуация, возникающая при этом, называется арифметическим переполнением. Предположим, что нам нужно вычислить

Статья 358 - Картинка 53

причем работает рассмотренное выше правило. Суммой этих двух положительных чисел будет отрицательное число

Статья 358 - Картинка 54

(подсчитайте его абсолютную величину). ЭВМ производит проверку и прекращает выполнение программы, если происходит переполнение.

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

Умножение и деление двоичных чисел производится так же, как умножение и деление десятичных, только сами арифметические действия производятся в двоичной системе. К примеру, для вычисления произведения Статья 358 - Картинка 55 наСтатья 358 - Картинка 56 необходимодействоватьтак: Статья 358 - Картинка 57

Отметим, что длина произведения равна сумме длин сомножителей. Следовательно, при умножении двух 32-разрядных слов может получиться 64-разрядный результат. Как мы увидим в дальнейшем, в действительности при выполнении операции умножения содержимое некоторого регистра умножается на содержимое другого регистра или слова памяти. Результат занимает два регистра, содержимое которых рассматривается как 64-разрядное двоичное число.

Деление двоичных целых чисел может выполняться с помощью хорошо известного алгоритма деления в столбик. Для выполнения деления 111011101 на 11011 можно записать:

Статья 358 - Картинка 58

То есть частное равноСтатья 358 - Картинка 59, остаток — Статья 358 - Картинка 60.

Частное и остаток при делении полных слов занимают по одному слову. Если делитель представляет собой полное слово, то мы имеем возможность разделить на него содержимое двух слов, рассматриваемых как единое 64-разрядное число. Как мы увидим позднее, такая возможность предусматривается командой деления.

На этом заканчивается наше формальное обсуждение двоичной целочисленной арифметики, хотя мы еще не раз встретимся с ней в примерах и упражнениях в других частях книги. Хорошее знание двоичной арифметики значительно облегчает составление и отладку программ. Проверьте себя, освоили ли вы простейшие арифметические действия в шестнадцатеричной "системе счисления и арифметику в дополнительных кодах.