Лекция №3
.pdf
58(10) 0011 1010(2) |
- ПК |
–23(10) 1001 0111(2) |
- ПК |
1110 1001(2) |
- ДК |
Число отрицательное - необходимо перевести в ДК (быстрый перевод)
0011 1010 |
Перенос из знакового разряда отбрасываем. Число является |
|
+ |
||
положительным в ПК. |
||
1110 1001 |
||
|
||
1 0010 0011(2) (ПК) = 35(10) |
||
перенос |
|
|
Заметим еще раз, что прямой, обратный и дополнительный коды положительных чисел совпадают. Поэтому многие не делают различий между ними, полагая, что положительное число имеет единственное изображение в ЭВМ – прямой код.
При алгебраическом сложении двух чисел с одинаковыми знаками возможно переполнение разрядной сетки. Признаком переполнения является наличие переноса в знаковый разряд суммы при отсутствии переноса из знакового разряда (положительное переполнение) или наличие переноса из знакового разряда суммы при отсутствии переноса в знаковый разряд (отрицательное переполнение).
Рассмотрим простейшие примеры с трехбитовыми словами. Диапазон чисел, которые они представляют, равен от –4 до +3. В рассматриваемых словах 1 бит знака и 2 информационных бита.
Пример 1: Вычислить алгебраическую сумму 2 + 1.
2+1=3 |
|
|
010(2) |
|
|
|
010(2) |
|
|
|
|
2(10) |
ПК |
+ |
001(2) |
|
|
|
001(2) |
|
|
|
|
1(10) |
ПК |
0 011(2) |
ПК = 3(10) |
||
|
|
|
|||
0
перенос
Так как перенос в знаковый разряд или из знакового разряда суммы отсутствует, то переполнения нет. Результат – положительное число в ПК, равное 3.
Пример 2: Алгебраическое суммирование с двумя переносами.
-3-1=-4 |
|
|
101(2) |
|
|
|
111(2) |
ПК 101(2) |
|
|
|
-3(10) |
ДК |
+ |
|
||
|
101(2) |
ПК 111(2) |
|
111(2) |
|
-1(10) |
ДК |
1 100(2) |
ДК=-4(10) |
||
|
|
|
|
||
|
|
|
|
1 |
|
|
|
|
|
перенос |
|
Имеются переносы в знаковый разряд и из знакового разряда вычисляемой суммы, поэтому переполнения нет. Результат – отрицательное число в ДК, равное -4.
Пример 3: Алгебраическое суммирование с одним переносом. (Положительное переполнение).
2+2=4 |
|
010(2) |
|
|
|
010(2) |
|
|
|
2(10) |
ПК |
+ |
|
|
|
010(2) |
|
010(2) |
|
2(10) |
ПК |
0 100(2) |
ДК = ?(10) |
|
|
|
|
||
|
|
|
1 |
|
|
|
|
перенос |
|
При суммировании есть перенос в знаковый разряд суммы, а перенос из знакового разряда отсутствует, т.е. имеет место положительное переполнение. Формальный результат равен –4.
Пример 4: Алгебраическое суммирование с одним переносом. (Отрицательное переполнение).
-3-2=-5 |
|
|
101(2) |
|
|
|
111(2) |
ПК 101(2) |
|
|
|
-3(10) |
ДК |
+ |
|
||
|
010(2) |
ПК 110(2) |
|
110(2) |
|
-2(10) |
ДК |
1 011(2) |
ДК=?(10) |
||
|
|
|
|
||
0перенос
Число -5 нельзя представить 3-битовой комбинацией. Формальный результат равен +3. Для обнаружения переполнения разрядной сетки можно использовать модифицированные коды. Модифицированные коды отличаются от обычных кодов тем, что знак числа кодируется двумя разрядами. Знак «+» в этих кодах кодируется двумя нулевыми знаковыми разрядами, а знак «-» – двумя единичными разрядами. При выполнении алгебраического сложения или вычитания два знаковых разряда участвуют в операции как равноправные цифровые разряды. После выполнения операции содержимое знаковых разрядов определяет знак результата (левый знаковый разряд) и наличие переполнения (несовпадение знаковых разрядов): комбинация 01 фиксирует переполнение при сложении положительных чисел (положительное переполнение), а 10 – отрицательных (отрицательное переполнение).
А=+0,101 |
[A] МДК = 00,101 |
B=+0,110 |
[B] МДК = 00,110 |
[A] МДК +[B] МДК = 01,011 |
|
А=-0,101 |
[A] МДК = 11,011 |
B=-0,110 |
[B] МДК = 11,010 |
[A] МДК +[B] МДК = 10,101
Из рассмотренных ранее примеров видно, что операция алгебраического сложения в дополнительном коде выполняются достаточно просто. Необходимо только не упускать из виду то, с какими числами происходит работа в данный момент – без знака или со знаком.
В ряде вычислительных задач, например экономического, статистического характера содержащих достаточно много численных данных и относительно простую арифметику, операции, связанные с переводом чисел из десятичной системы в двоичную существенно превысили бы время выполнения операций по обработке информации.
Для преодоления этого пользуются простым и оригинальным приемом: предварительно в двоичную ПСС переводят не все число, а поразрядно все его цифры – в результате получается некоторый смешанный двоично-десятичный код десятичного числа (BCD, Binary Coded Decimals). Можно отметить, что двоично-десятичное представление чисел используется и в тех случаях, когда предъявляются повышенные требования к точности вычислений.
Двоично-десятичный код может быть упакованным, когда в одном байте хранятся две десятичные цифры, либо неупакованным – по одной цифре в байте. Двоично-десятичное число в упакованном формате образуется следующим образом: каждая цифра десятичного
числа заменяется тетрадой. При обратном преобразовании необходимо каждую тетраду заменить эквивалентной ей десятичной цифрой:
9 8, 31 0 1 0 0 1 1 0 0 0 , 0 0 1 1 B C D .
Для некоторых типов ЭВМ в АЛУ имеются специальные блоки десятичной арифметики, выполняющие операции над числами в двоично-десятичном коде. Это позволяет в ряде случаев существенно повышать производительность ЭВМ. Эта система при представлении каждой тетрады имеет веса разрядов равные 8,4,2,1. Поэтому код BCD иногда обозначают как код «8421».
Положение десятичной точки и знака при двоично-десятичном кодировании может быть самым различным. Например, десятичная точка может находиться после третьего слева разряда числа. При выполнении алгебраического сложения многоразрядных чисел при двочно-десятичном кодировании используется дополнительный код, при этом, самый левый байт может использоваться для знака.
В современных процессорах фирмы Intel и большинстве других используется упакованный BCD код следующего формата: для хранения числа отводится 10 байт, причем крайний левый байт предназначен для хранения знака, а в остальных девяти байтах записаны по две тетрады числа. Этот формат позволяет оперировать восемнадцатиразрядными десятичными числами, что вполне достаточно для экономических расчетов.
Преимуществом работы с двоично-десятичными числами является возможность получения результатов с абсолютной точностью. Недостатком – большой объем памяти, необходимый для записи двоично-десятичных чисел, и пониженная скорость выполнения арифметических операций.
Если |
числа |
X1 |
и Х2 представлены в форме |
с |
плавающей запятой, т.е. |
Х 1 m 1 P1 , |
Х 2 |
m 2 P2 |
то для их сложения необходимо Х1 |
и Х2 |
привести к общему порядку |
Pобщ. Далее можно общий множитель вынести за скобки и провести сложение мантисс:
X 1 X 2 2 Pо б щ ( m1 m 2' ).
Очевидно, при конечной длине поля цифр мантиссы Робщ необходимо выбирать из условия Робщ = max{P1,P2}, так как в противном случае произойдет переполнение разрядной сетки. В ЭВМ определен следующий порядок выполнения операции сложения чисел, представленных в форме с плавающей запятой:
1.Вычитание порядков складываемых чисел. Если разность порядков равна нулю (порядки равны), то перейти к пункту 3. Если порядки не равны, то осуществить выравнивание порядков (пункт 2).
2.Увеличение меньшего из порядков до большего. Мантисса числа с меньшим порядком сдвигается вправо на число разрядов, равное разности порядков.
3.Сложение мантисс. Если не произошло переполнения разрядной сетки мантиссы и сумма получена в нормализованном виде, то вычисления закончить. Сумма мантисс является мантиссой суммы чисел, а порядок суммы чисел равен порядку большего числа (или общему порядку). В противном случае перейти к пункту 4.
4.Нормализация полученной суммы вправо (при переполнении разрядной сетки мантиссы) или влево (при наличии в мантиссе нулей). При нормализации вправо мантиссу суммы сдвинуть вправо на один разряд, а порядок суммы увеличить на единицу. При нормализации влево мантиссу суммы сдвинуть влево до первой значащей цифры, а порядок суммы уменьшить на такое же количество единиц.
2.5.Выполнение операций умножения и деления в ЭВМ.
Как и в десятичной системе счисления, операция умножения двоичных многоразрядных чисел производится путем образования частичных произведений и последующего их суммирования. Частичные произведения формируются в результате умножения множимого на каждый разряд множителя, начиная с младшего (старшего) разряда. Каждое частичное произведение смещено относительно предыдущего на один разряд. Поскольку умножение идет в двоичной системе счисления, каждое частичное произведение равно либо 0 (если в соответствующем разряде множителя стоит 0), либо является копией множимого, смещенного на соответствующее число разрядов влево (если в разряде множителя стоит 1) или вправо. Поэтому умножение двоичных чисел идет путем сдвига и сложения.
Таким образом, количество частичных произведений определяется количеством единиц в множителе, а количество сдвигов – положением единиц. Рассмотрим подробнее некоторые алгоритмы умножения в прямом коде.
Пусть нам нужно перемножить два целых числа (напомним, что в большинстве случаев они хранятся в ЭВМ как правильные дроби): X 0 , x1 x 2 ...x m 1 x m , Y 0 , y1 y 2 ... y n 1 y n . Тогда
возможны следующие варианты алгоритмов, часть из которых основана на преобразовании по схеме Горнера, позволяющей минимизировать количество операций умножения и суммирования:
1) Умножение с младших разрядов со сдвигом частичных сумм вправо.
X Y = 0 , x |
x |
2 |
x |
m |
y |
1 |
2 |
1 y |
2 |
2 |
2 y |
n |
2 n 0 X y |
1 |
2 1 |
X y |
n 1 |
2 n 1 |
X y |
n |
2 n |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
0 X y n 2 n X y n 1 2 n + 1 X y 1 2 1 0 X y n 2 1 X y n 1 2 1 X y 1 2 1
2) Умножение с младших разрядов со сдвигом частичных произведений влево.
X Y = 0 , x |
1 |
x |
2 |
x |
m |
y |
1 |
2 1 |
y |
2 |
2 |
2 y |
n |
2 |
n X y |
n |
2 |
n X y |
n 1 |
2 n + 1 X y |
1 |
2 1 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
0 X y |
n |
|
X y |
n 1 |
2 2 X y |
1 |
2 n 1 2 n |
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
3) Умножение со старших разрядов со сдвигом частичных сумм влево.
X Y = 0 , x1 x 2 x m y 1 2 1 y 2 2 2 y n 2 n X ( y 1 2 n 1 y 2 2 n 2 y n ) 2 n( X y 1 2 n 1 X y 2 2 n 2 X y n ) 2 n 0 X y 1 2 X y 2 2 X y n ) 2 n
4) Умножение со старших разрядов со сдвигом частичных произведений вправо.
X Y = 0, x1 x 2 x m y 1 2 1 y 2 2 2 y n 2 n 0 X y 1 2 1 X y 2 2 2 X y n 2 n
Таким образом, например, для умножения по алгоритму номер один, должна выполняться следующая последовательность действий:
1.Значению суммы присваивается ноль. Начиная с младшей цифры множителя:
2.Аанализируется цифра множителя. Если она равна единице, то множимое участвует в формировании части произведения. В противном случае – не участвует.
3.К сумме прибавляют множимое. Полученная (частичная) сумма сдвигается вправо на один разряд.
4.Операции по пунктам 2 и 3 выполняются до старшего разряда.
Конечно, за рамками рассмотрения остаются вопросы переполнения разрядной сетки (в общем случае для размещения произведения нужно m+n разрядов), возможные варианты ускорения алгоритмов и ряд других очень важных вопросов. И естественно, указанными алгоритмами не исчерпывается весь список применяемых на сегодня алгоритмов умножения целых чисел в ЭВМ.
Алгоритм умножения чисел, представленных в форме с плавающей запятой, определяется следующим соотношением: ( X 1 2 P1 m 1 ) ( X 2 2 P2 m 2 ) ( m 1 m 2 ) 2 P1 P2 . При реализации
операции умножения над числами с плавающей запятой в ЭВМ выделяют следующие этапы:
1.определение знака произведения путем сложения по модулю два знаков мантисс операндов;
2.перемножение модулей мантисс по правилам умножения дробных чисел с фиксированной запятой;
3.определение порядка произведения путем алгебраического сложения порядков сомножителей;
4.нормализация результата (так как сомножители нормализованы, то денормализация возможна только на 1 разряд и только вправо) и округление мантиссы в случае необходимости.
Если умножение выполняется путем многократных сдвигов и сложений, то деление, будучи операцией обратной умножению – путем многократных сдвигов и вычитаний. При представлении чисел с фиксированной запятой деление возможно, если делимое по модулю меньше делителя, в противном случае произойдет переполнение разрядной сетки. Рассмотрим пример деления «ручным» способом.
Пример: Вычислить 1100,011(2)/10,01(2).
-1100011 10010
10010 101,1
-11011 10010
-10010
10010
0
Здесь после каждого вычитания делитель сдвигается вправо по отношению к делимому. Если остаток после вычитания получился положительный, в разряд частного записывается 1, если отрицательный – 0.
При выполнении операции деления над числами с плавающей запятой мантисса частного определяется как результат деления мантиссы делимого на мантиссу делителя, а порядок частного в результате вычитания кода порядка делителя из кода порядка делимого, так как
( X 1 2 P1 m 1 ) : ( X 2 2 P2 m 2 ) ( m 1 : m 2 ) 2 P1 P2 .
Ограничимся приведенными фактами при рассмотрении вопроса о делении двоичных чисел.