Формальные правила двоичной арифметики

↑

▷ Содержание

⇐ ПредыдущаяСтр 4 из 22Следующая ⇒

▷ Похожие статьи

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

В общем случае процедуры сложения и вычитания двух чисел

A B = C в любой позиционной системы счисления начинаются с младших разрядов.

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

a i + b i +1, где единица соответствует переносу из младшего (i - 1)-разряда в i -тый, если в младшем разряде код суммы получился больше или равным основанию системы счисления.

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

a i - b i -1, где единица соответствует заему, если он был, в младшие разряды величины, равной основанию системы счисления.

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

Теперь рассмотрим правила арифметики с числами, представленными в двоичном коде.

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

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0 и осуществляется перенос 1 в старший соседний разряд.

Например:

01012 = 510

+00112 = 310

10002 = 810

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

0 - 0 = 0

1 - 0 = 1

1 - 1 = 0

0 - 1 =1 после заема единицы из соседнего старшего разряда.

Например:

01102 = 610

-00112 = 310

00112 = 310

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

Умножение двоичных чисел производится путем образования про-межуточных произведений и последующего их суммирования. Промежуточные поразрядные произведения формируются по следующим правилам:

0 x 0 = 0 101 510 x 310 = 1510

0 x 1 = 0 11

1 x 0 = 0 101

1 x 1 = 1 + 101

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

Например:

110: 11 = 10 610: 310 = 210

11

00

Арифметические действия с двоичными числами подробно будут рассмотрены в дальнейшем.

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

ai HS S ci ai SM S ci

bi

bi P Pi Pi-1 P Pi

а) б)

Рис.2.1 Условное обозначение полусумматора (а)

и двоичного сумматора (б).

Здесь a i и b i это i -тые разряды чисел А и В, которые складываются, а c i - i -тый разряд суммы этих чисел, Pi - перенос из данного разряда в соседний следующий старший, Pi-1 - перенос из соседнего младшего в данный разряд.

Если для представления двоичных чисел А, В, С и их знаков выделена

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

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

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

A+B=C можно представить следующим образом:

A Pr

CM Pr

Pr C

B

где Рr - некоторые регистры, в которые записываются двоичные числа А, В и С; СM - сумматор, точнее группа сумматоров n SM, где n - длина разрядной сетки, отведенной для представления чисел А, В и С.

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

Кроме этих операций в цифровых автоматах, компьютерах, выполняется еще одна операция над двоичными числами - это сдвиг числа по разрядной сетке влево или вправо. В случае сдвига влево фактически осуществляется умножение двоичного числа на 2, а при сдвиге вправо - деление на 2, где - количество разрядов, на которое сдвигается двоичное число. Например: 0000112= 310 сдвинем влево на 2 разряда, получим 0011002 = 1210, т.е.

3х4(22) = 1210, а теперь 0010002 = 810 сдвинем на 2 разряда вправо, получим 0000102 = 210, т.е. 8:4(22) = 210.

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

Перевод числа из одной позиционной системы счисления в

Другую

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

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

Например

(3 0 5. 4)8 = 11000101.100(2);

011 000 101. 100

(7 B 2. E)16 = 11110110010.1110(2).

0111 1011 0010. 1110

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

Например:

1) перевод 1101111001.11012 в восьмеричное

001101111001. 110100 = 1571.648;

1 5 7 1 6 4

2) перевод 11111111011.100111(2) в шестнадцатеричное

011111111011. 10011100 = 7FB.9C(16).

7 F B 9 C

Двоично-десятичный код (D-код) ориентирован на наиболее удобную для человека десятичную систему счисления. В нем для записи чисел используются только двоичные цифры 0 и 1. Двоично-десятичный код образуется заменой каждого десятичного разряда в десятичном числе 4-х битовым двоичным представлением этого разряда.

Например,

0001 1001 1000 0100(D) = 1984(10)

0001100110000100

1 9 8 4

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

1) 53:2 = 26:2 = 13:2 = 6:2 = 3:2 = 1

(мл. раз.) 1 0 1 0 1 1 (ст. раз.)

n\t\ 53(10) = 110101(2).

2) 128:8 = 16:8 = 2

0 0 2

12810 = 2008

3) 128:16 = 8

0 8

12810 = 8016

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

Процедуру преобразования десятичной дроби в двоичную рассмотрим на примере преобразования числа 0,375.

1. Преобразование осуществляется умножением дроби на основание системы счисления, в которой дробь должна быть представлена. В данном случае умножаем на 2: 0,375 х 2 = 0.75. Окончательный результат формируется поразрядно, начиная со старшего разряда, к примеру, в некотором трехразрядном регистре С = 0.XXX, где XXX - разрядная сетка мантиссы этого регистра.

2. Если результат <1, то старшему значащему разряду присваивается значение 0; если больше 1, то присваивается 1. Поскольку 0,75<1, то в старший разряд регистра С записывается 0, т.е. С = 0,0XX.

3. Результат предыдущей операции умножения снова умножаем на 2. Заметим, что если бы результат предыдущей операции умножения был больше 1, то в данной операции умножения участвовала лишь его дробная часть. В данном случае 0,75 x 2 = 1,5.

4. Так как результат больше 1, то следующему значащему разряду регистра С присваивается значение 1, т.е. С = 0,01X.

5. Шаги описанной процедуры повторяются до тех пор, пока либо результат умножения не будет точно равен 1, либо не будет достигнута требуемая точность. В нашем примере после выполнения очередного шага результат равен 0,5 x 2 = 1,0. Поэтому очередному значащему разряду регистра С присваивается 1, т.е. окончательно получена двоичная дробь С = 0.0112.

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

Расмотрим еще пример: переведем число 0,3437510 в двоичное

2 x 0,34375 = 0,6875 0 (старший разряд - СЗР, результата перевода)

2 x 0,6875 = 1,375 1

2 x 0,375 = 0,75 0

2 x 0,75 = 1,5 1

2 x 0,5 = 1,0 1

2 x 0 = 0 0 (младший разряд - МЗР, результата перевода)

Ответ: 0,01011(2)

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

Например:

1) 0,0625 x 8 = 0,5 0

0,5 x 8 = 4 4

0,062510 = 0,048

2) 0,875 x 16 = 14(E)

0,87510 = 0,E16

Перевод двоичного числа в десятичный его эквивалент можно выполнить при помощи формулы (2.1):

1) 110101(2) = 125+ 124 + 023 + 122 + 021 + 120 =

132 + 116 + 08 + 14 + 02 + 11 = 32 + 16 + 4 + 1 = 53(10).

2) 2008 = 282+ 081 + 080 = 12810

3) 1F16 = 1161+ 15160 = 3110

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

Глава 3.

Познавательные статьи:



Техника прыжка в длину с разбега

Организация работы процедурного кабинета

Области применения синхронных машин

Оптимизация по Винеру и Калману