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

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

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

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

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

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

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

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

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

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

11011.1001

в десятичную форму можно записать

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

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

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

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

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

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

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

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

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

и в конечном итоге мы получаем

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

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

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

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

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

 

Шестнадцатеричная система, или система с основанием 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. Десятичные, двоичные и шестнадцатеричные числа.

если это потребуется. Например, для преобразования

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

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

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

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

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

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

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

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

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

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

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

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

и

Получим

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

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

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

Совершенно верным (и наиболее часто используемым опытными программистами) способом является следующий: шестнадцатеричные числа переводятся по столбцам в десятичные, выполняется сложение, и результат снова приводится к шестнадцатеричному виду с переносом единиц в старший разряд, если полученная сумма больше (десятичного) 16. Возвращаясь к нашему примеру, мы должны рассуждать так: «есть,есть, сумма равна. Далее, больше , поэтому мы должны вычесть из результата, получим 2, но теперь необходимо произвести перенос 1, компенсируя таким образом вычитание 16». Рассмотрим более сложный пример:

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

 

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

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

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

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

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

00000005

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

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

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

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

00101010001001011100011110101000

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

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

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

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

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

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

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

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

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

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

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

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

1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

То есть частное равно,     остаток    — .

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

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

 
Статьи раздела