Компьютерная арифметика icon

Компьютерная арифметика


3 чел. помогло.
Смотрите также:
Компьютерная арифметика...
Исследовательская работа по предмету Математика Тема: «Арифметика наука о числе»...
Арифметика Диофанта...
Областное Государственное учреждение Региональный центр развития образования моу средняя...
Реферат по дисциплине: Информационные технологии в социальной сфере на тему: Компьютерная...
Урок английского языка в 3 классе по теме: “...
Методика рейтингового контроля знаний студентов по дисциплине опд...
Математические основы криптографии с открытым ключом. Теория делимости, алгоритм Евклида...
Рабочая программа дисциплины начертательная геометрия. Инженерная и компьютерная графика...
Компьютерная лингвистика: моделирование языкового общения...
Моу «сош ст. Евсино» Учебно-методический комплекс «Компьютерная графика Adobe PhotoShop»...
Рабочая программа учебной дисциплины ф тпу 1-21/01 утверждаю...



Загрузка...
скачать

КОМПЬЮТЕРНАЯ АРИФМЕТИКА



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

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





^

1. СИСТЕМЫ СЧИСЛЕНИЯ, ИСПОЛЬЗУЕМЫЕ НА КОМПЬЮТЕРЕ

1.1 Двоичная система счисления



В повседневной жизни мы используем десятичную систему счисления. В ней, как известно, используется 10 цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. С их помощью и записывают любые цифры, при этом позиция цифры в числе означает количество единиц, десяток, сотен и т.д. Например, число 4728 означает:

4728 = 4*1000 + 7*100 + 2*10 +8 или 4728 = 4*103 + 7*102 + 2*101 +8*100

Можно сказать, что цифры числа (разряды) нумеруются справа налево, причем счет идет с нуля. В данном примере, 8 – нулевой разряд, 2 – первый, 7 – второй, 4 – третий.

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

472.83 = = 4*102 + 7*101 + 2*100 +8*10–1 +3*10–2

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

Цифры 0 и 1 в двоичной системе означают то же, что и в десятичной:

02 = 010 , 12 = 110 . И далее также используется позиционная система:

102 = 1*21 + 0*20 = 210 ; 112 = 1*21 + 1*20 = 310 ; 1002 =1*22 +0*21 + 0*20 = 410

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

1001.1012 = 23 + 20 + 2–1 + 2–3 = 9.62510 .

Но как преобразовать из десятичной в двоичную систему?

Целая и дробная части представления преобразуются раздельно.


Целую часть последовательно делим на 2 и выписываем остатки в обратном порядке. Это и даст нам двоичное представление числа.

Таким образом, 1110 = 10112 .

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

Например, преобразуем число 0.8110 в двоичную систему.

Т
аким образом, 0.8110 = 0.1100112 (приблизительно).

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

Например, десятичное число –1.312510 в двоичном виде будет выглядеть как – 1001.01012 . Но в компьютере мы не можем хранить и обрабатывать символы знака и разделяющей точки – для машинного представления могут использоваться только двоичные цифры (0 и 1). Если операции выполняются только с неотрицательными числами, то формат представления очевиден. В машинном слове из 8 бит можно представить число в интервале от 0 до 255:

00000000 = 0

00000001 = 1

………..

00101001 = 41



10000000 = 128



11111111 = 255

Порядок работы с отрицательными числами рассмотрим в разделе 2.
    1. ^

      Шестнадцатиричная система счисления



Поскольку современная электронно-вычислительная техника принципиально построена на двоичных элементах, любые данные в ней представляются только двоичными кодами. Но пользователю применять начертание кода в виде длинных последовательностей нулей и единиц очень неудобно. Поэтому специалисты используют для работы с двоичными кодами «на бумаге» более компактное их представление. Такую компактную форму дает шестнадцатиричная система счисления. Для преобразования из двоичного представления в 16-ричное двоичные цифры группируются по четыре (как говорят, разбивают на тетрады), и каждая четырехзначная комбинация заменяется шестнадцатиричной цифрой:

0000 = 0 1000 = 8

0001 = 1 1001 = 9

0010 = 2 1010 = A (десятичное 10)

0011 = 3 1011 = B (десятичное 11)

0100 = 4 1100 = C (десятичное 12)

0101 = 5 1101 = D (десятичное 13)

0110 = 6 1110 = E (десятичное 14)

0111 = 7 1111 = F (десятичное 15)

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

Например, как записано выше 25510 = 111111112 . Здесь имеем две тетрады: 1111 1111. Значит, 25510 = 111111112 = FF16 . Проверим правильность – переведем в десятичную систему из 16-ричной: FF16 = F*161 + F*160 = 15*16 + 15*1 = 240 + 15 = 25510 ,т.е. все верно.

Другой пример: 10 1111 1000 0101 1001. Видно, что впереди необходимо добавить два нуля: 0010 1111 1000 0101 1001.

2 F 8 5 9

Тогда имеем: 10 1111 1000 0101 10012 = 2F85916 . Проверим, пересчитав в 10-й системе:

10 1111 1000 0101 10012 = 217+215+214+213+212+211+26+24 +23 +1 = 19464910 .

2F85916 = 2*164 + F*163 + 8*162 +5*161 + 9 = 2*65536+15*4096+8*256+89 = 19464910 . Видим, что все верно.

Рассмотрим пример числа с дробной частью.

10011110001,11001100001. Здесь необходимо приписать нуль впереди целой части и нуль позади дробной части (для получения тетрад):

0100 1111 0001,1100 1100 0010. В результате имеем 4F1,CC216 .

Ясно, что перевести целое число из 10-й системы в 16-ричную можно также последовательным делением десятичного числа на 16 и выписыванием остатков в обратном порядке (уже в 16-ричном виде). Дробь же переводится последовательным умножением на 16 и выписыванием целых частей произведений в правильном порядке (т.е. все так же, как и для двоичных чисел).


^ ЗАДАНИЯ РАЗДЕЛА 1.


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

Зад.1 Получить десятичный эквивалент следующих двоичных чисел

Зад.2 Получить десятичный эквивалент следующих 16-ричных чисел

Зад.3 Перевести числа из десятичной системы в двоичную

Зад.4 Перевести числа из десятичной системы в шестнадцатиричную

Зад.5 Перевести числа из двоичной системы в шестнадцатиричную

При выполнении заданий 3 – 5 следует проводить проверку с использованием десятичной системы счисления.


Вариант

Задание 1

Задание 2

Задание 3

Задание 4

Задание 5

1

1001010

15B

43

7501

111011110011,10011

2

110010011

CD1

24

3765

0,110111001

3

111000

16

416

908

10011110001,11001100001

4

111011110011,10011

4AD

253,2

9854

1001010

5

101111100001011001

0,81

794,15

77659

110010011

6

0,110111001

998C

6,4

4591

111000

7

10011110001,11001100001

FF77

439

692,54

11001100001

8

110111001

DA0774

8419

7428,41

10011110001

9

10011110001

B4AA

692,54

196,7591

111011110011

10

11001100001

FF9A3

7428,41

794,15

101111100001011001



^

2. АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ В ДВОИЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ

2.1 Прямой код



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

Простейшим форматом, который использует знаковый разряд является прямой код. Например, при 8-разрядном представлении

+18 = 00010010

–18 = 10010010

Однако, прямой код неудобен при использовании в вычислениях. Во-первых, сложение и вычитание положительных и отрицательных чисел выполняется по-разному, а потому требуется анализировать знаковые разряды операндов (слагаемых). Во-вторых, в прямом коде числу 0 соответствует две комбинации:

+0 = 00000000

–0 = 10000000

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

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

^

2.2 Обратный и дополнительный код



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

^ Об­рат­ный код положительного числа остается неизменным. А обратный код отрицательного двоичного числа формируется дополнением модуля исходного числа нулями до самого старшего разряда модуля, а затем поразрядной заменой всех нулей числа на единицу и всех единиц на нули. В знаковом разряде обратного кода у положительных чисел будет 0, а у отрицательных – 1. В общем случае обратный код является дополнением модуля исходного числа до наибольшего числа без знака, помещенного в разрядную сетку.

Например, при 8-разрядном представлении числа +2810 имеем:

+2810 = 000111002

Если же возьмем –2810 , то в обратном коде имеем:

–2810 = 111000112

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

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

Например, –510 преобразуем в дополнительный код.

5 в двоичном виде дает (при 4-разрядном двоичном представлении) 0101, тогда –5 даст 1101 (впереди 1 – знак минус). Получаем обратный код: 1010, затем добавляем в младший разряд единицу: 1011 – это и есть дополнительный код –5. Итак, –510 = 10112

Итак, рассмотрим n-разрядное двоичное число A в дополнительном коде. Если заданное число A положительное, то в значащих разрядах представляется абсолютная величина числа точно так же, как и в прямом коде:



Если же число отрицательное, то для него соблюдается соотношение



Если рассмотреть конкретно 4-разрядные целые числа, то представление их в прямом и дополнительном коде можно записать в виде таблицы:


Таблица 1.

^ Десятичное представление

Прямой код

Дополнительный код

+7

0111

0111

+6

0110

0110

+5

0101

0101

+4

0100

0100

+3

0011

0011

+2

0010

0010

+1

0001

0001

+0

0000

0000

–0

1000



–1

1001

1111

–2

1010

1110

–3

1011

1101

–4

1100

1100

–5

1101

1011

–6

1110

1010

–7

1111

1001

–8



1000


Видим, что в дополнительном коде, по крайней мере, исчезла проблема двух нулей.

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

+18 в прямом коде на 8 разрядов 00010010

+18 в прямом коде на 16 разрядов 00000000 00010010

–18 в прямом коде на 8 разрядов 10010010

–18 в прямом коде на 16 разрядов 10000000 00010010

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

+18 в дополнительном коде на 8 разрядов 00010010

+18 в дополнительном коде на 16 разрядов 00000000 00010010

–18 в дополнительном коде на 8 разрядов 11101110

–18 в дополнительном коде на 16 разрядов 11111111 11101110

Формально справедливость этого правила доказывается так. Рассмотрим n-разрядную последовательность двоичных цифр an-1 an-2…a1 a0 , которая интерпретируется как представление в дополнительном коде числа A:



Сразу видно, что если число A положительно, правило справедливо. Если е число A отрицательно, нужно сформировать m-разрядное его представление (m>n), такое, что



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



Т
.к. число отрицательное, крайние левые разряды равны единице

Тогда




или





О
тсюда следует, что

В каждом из приведенных соотношений соблюдается условие неизменности младших n–1 разрядов представления. Последнее соотношение справедливо только в том случае, когда коды во всех разрядах от n–1 до m–2 равны 1. Тем самым подтверждается справедливость сформулированного выше правила расширения знака.

^

Арифметические операции с целыми числами


Рассмотрим алгоритмы выполнения основных арифметических операций над целыми числами, представленными в дополнительном коде.


Сложение и вычитание


Рассмотрим эти операции на примерах.


а) –7 = 1001 б) –4 = 1100

+5 = + 0101 +4 = + 0100

1110 = –2 10000 = 0


в) +3 = 0011 г) –4 = 1100

+4 = + 0100 –1 = + 1111

0111 = 7 11011 = –5


д) +5 = 0101 е) –7 = 1001

+4 = + 0100 –6 = + 1010

1001 переполнение 10011 переполнение


Первые четыре примера демонстрируют успешное выполнение операций. Если результат операции должен быть положительным, получается код положительного числа в дополнительном коде, а если отрицательным – код отрицательного числа в дополнительном коде (сравни со значениями в Таблице 1). Обратим внимание, что в примере г) формируется перенос из старшего (знакового) разряда, который игнорируется.

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

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

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

Рассмотрим операцию вычитания. Она выполняется по следующему правилу:

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

Проиллюстрируем также на примерах. В них символом М обозначено уменьшаемое, а символом S – вычитаемое.


а) M= 2 = 0010 б) M= 5 = 0101

S = 7 = 0111 S = 2 = 0010

–S = 1001 –S = 1110


0010 0101

+ 1001 + 1110

1011 = –5 10011 = 3


в) M= –5 = 1011 г) M= 5 = 0101

S = 2 = 0010 S= –2 = 1110

–S = 1110 –S = 0010


1011 0101

+ 1110 + 0010

11001 = –7 0111 = 7


д) M= 7 = 0111 е) M= –6 = 1010

S = –7 = 1001 S = 4 = 0100

–S = 0111 –S = 1100


0111 1010

+ 0111 + 1100

1110 переполнение 10110 переполнение


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


ЗАДАНИЯ


Ниже предложены варианты заданий (см. табл.). Каждое задание состоит из трех этапов.

А) Числа X и Y представлены в форме короткого целого. Вычислить X+Y

Б) Вычислить X – Y

В) Числа A и B в формате короткого вещественного слова. Выполнить операцию A+B

Номер варианта

Числа

X

Y

A

B

1

10236

-18758

724,71

-10,83

2

-3876

14932

116,03

-494,4

3

-19392

24076

-376,47

21,001

4

-13704

-23800

-19,865

119,1

5

-21005

12037

-275,5

24,75

6

876

-14731

325,11

-36,55

7

-734

18005

610,44

-3,175

8

16538

-11010

327,93

-1,172

9

-12709

25068

505,4

-26,43

10

-10736

19805

99,031

-17,666



^ Методические рекомендации.

В формате короткого целого число состоит из 32 двоичных разрядов, их нумерация начинается с нуля, тогда крайний слева (31-й разряд) является знаковым (0 – плюс, 1 – минус).

Как показано ранее, для перевода десятичного числа в двоичную систему счисления целесообразно вначале перевести число в 16-ричную систему (методом деления), а затем в двоичную. Это упрощает процедуру перевода, так как для перевода из 16-ричной системы в двоичную достаточно записать каждую цифру 16-ричного числа в виде соответствующей двоичной тетрады (четырехзначного двоичного числа). Кроме того, необходимо помнить, что положительные числа хранятся в памяти компьютера в прямом коде, а отрицательные – в дополнительном.

Этапы А и Б.

Пример. Показать изображение чисел X=18730 и Y=–16273 в формате короткого целого и выполнить над ними действия X+Y и X–Y

X =(18730)10 = (492A)16 =(100 1001 0010 1010)2

Y= (–16273)10 = (-3F91)16 = (–11 1111 1001 0001)2

Представим эти же числа в виде двоичных слов (заданного формата):

X2 =0000 0000 0000 0000 0100 1001 0010 1010 – прямой код

Y2= 1111 1111 1111 1111 1100 0000 0110 1111 – дополнительный код

При выполнении операций сложения операнды складываются в тех кодах, в которых они хранятся в памяти:

X = 0000 0000 0000 0000 0100 1001 0010 1010

+

Y = 1111 1111 1111 1111 1100 0000 0110 1111

X+Y = 0000 0000 0000 0000 0000 1001 1001 1001 или 1001 1001 1001

Сделаем проверку:

(X+Y)10 = (18730)10 + (-16273)10 = (2457)10

А мы получили в двоичном виде: X+Y = (1001 1001 1001)2 . Выполним перевод в десятичную систему счисления:

X+Y = 1* 211 + 1* 28 + 1* 27 + 1* 24 + 1* 23 + 1* 20 = 2048 + 256 + 128 + 16 + 8 + 1 = 2457. Т.е. все верно.

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

Код вычитаемого Y после указанного действия:

–Y = 0000 0000 0000 0000 0011 1111 1001 0001

Тогда

X = 0000 0000 0000 0000 0100 1001 0010 1010

+

–Y = 0000 0000 0000 0000 0011 1111 1001 0001

X – Y = 0000 0000 0000 0000 1000 1000 1011 1011 или

Результат получен в прямом коде: (X – Y)2 = (1000 1000 1011 1011)2

Проверка:

(X – Y)10 =(18730)10 – (–16273)10 = (35003)10

Нами же получено: (X – Y)2 = (1000 1000 1011 1011)2 =1*215 +1*211 + 1* 27 + 1*25 + 1*24 + 1*23 + 1*21 +1*20 = 32768+2048+128+32+16+8+2+1 = 35003, т.е. все верно.


Этап В.

В формате короткого вещественного представляются числа с плавающей точкой, старший разряд является знаковым, один байт отводится под смещенный порядок (смещение N=27 = 128 прибавляется к порядку числа, что упрощает действия над порядками), а двоичная мантисса занимает 23 разряда; числа в памяти хранятся в нормализованном виде, т.е. в старшем порядке мантиссы записана 1:

знак

Смещенный порядок

Двоичная мантисса

31

30 23

22 0


^ Пример. Представить в форме с плавающей точкой числа A=314,51, B= –16,22 и выполнить операцию A+B

Переведем эти числа в двоичную систему счисления (целая часть переводится методом деления на 2, дробная – методом умножения на 2):

A = 100111010,10000010100011*20 = 0,10011101010000010100011*29

B=–10000,001110000101000111*20 = –0,10000001110000101000111*25

Смещенный порядок числа A будет равен

P*A = PA + N = 9 + 128 = 13710 = 1000 10012 ,

Смещенный порядок числа B будет равен

P*B = PB + N = 5 + 128 = 13310 = 1000 01012

Запишем числа в заданном формате

A: 0.10001001.10011101010000010100011

B: 1.10000101.10000001110000101000111

Для выполнения операции сложения необходимо выровнять порядки чисел, т.е. принять порядок меньшего числа (B) равным порядку большего числа (A), уменьшив мантиссу меньшего числа путем сдвига вправо на число разрядов, равное разности порядков чисел (PA – PB =4) :

B: 1.10001001.00001000000111000010100

Мантиссу отрицательного числа MB представляем в дополнительном коде, положительного MA – в прямом. Тогда

MA =0.10011101010000010100011

+

MB =1.11110111111000111101100

MA + MB =0.10010101001001010001111

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

A+B : 0.10001001.10010101001001010001111

Проверка.

Рассчитаем порядок. 10001001 = 27 +23 + 20 = 128 +8 + 1 = 13710 Или с учетом смещения 137 – 128 = 9.

Тогда, т.к. мантисса имеет вид: 0.10010101001001010001111, то с учетом порядка имеем: 100101010.01001010001111 (сдвинули дес.точку на 9 позиций)

Значит, целая часть результата:

28 + 25 + 23 + 21 =256+32+8+2 = 298

Дробная часть результата:

2–2 + 2–5 + 2–7 + 2–11 + 2–12 + 2–13 + 2–14 = 0,28997802734375  0,29

Эти же числа сложим в десятичной системе:

314,51

+

–16,22

298,29

Видим, что все верно.




Скачать 163,2 Kb.
оставить комментарий
Дата02.10.2011
Размер163,2 Kb.
ТипДокументы, Образовательные материалы
Добавить документ в свой блог или на сайт

плохо
  1
средне
  1
отлично
  3
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх