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

1. Образовательные программы «Бизнес-информатика» «Прикладная математика и информатика» «Программная инженерия» (бакалавриат)

Национальный исследовательский университет
«Высшая школа экономики»
Факультет информатики, математики и компьютерных наук
Образовательные программы
«Бизнес-информатика»
«Прикладная математика и информатика»
«Программная инженерия»
(бакалавриат)
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017
www.hse.ru

2.

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

3.

Компьютерная арифметика
Целочисленная арифметика
- знаковая
[– r n – 1 , r n – 1 – 1]
- беззнаковая
[0 , r n – 1]
r – основание системы счисления,
n – количество разрядов формата хранения числа
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017

4.

Компьютерная арифметика
Целочисленная арифметика двоичных чисел
- знаковая 8-разрядная архитектура
[– 2 8 – 1 , 2 8 – 1 – 1] => [–128 , 127]
- беззнаковая 8-разрядная архитектура
[0 , 2 8 – 1] => [0, 255]
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017

5.

Компьютерная арифметика
Целочисленная арифметика “десятичных” чисел
- знаковая 4-разрядная архитектура
[– 10 4 – 1 , 10 4 – 1 – 1] => [–1000 , 999]
- беззнаковая 4-разрядная архитектура
[0 , 10 4 – 1] => [0, 9999]
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017

6.

Компьютерная арифметика
Целочисленная арифметика.
Внутреннее представление двоичных чисел
- знаковая 8-разрядная архитектура
- неотрицательные числа
[0 , 127] => [00000000, 01111111]
- прямой код
- отрицательные числа
[–128 , –1] => [10000000, 11111111]
- дополнительный код
- беззнаковая 8-разрядная архитектура
[0, 255] => [00000000, 11111111]
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017

7.

Компьютерная арифметика
Целочисленная арифметика.
Внутреннее представление “десятичных” чисел
- знаковая 4-разрядная архитектура
- неотрицательные числа
[0 , 999] => [0000, 0999]
- прямой код
- отрицательные числа
[–1000 , –1] => [9000, 9999]
- дополнительный код
- беззнаковая 4-разрядная архитектура
[0, 9999] => [0000, 9999]
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017

8.

Компьютерная арифметика
Целочисленная арифметика.
Правила преобразования кода
ДК = ОК(ПК) + 1
ПК = ОК(ДК) + 1
ПК – прямой код
ОК – обратный код (поразрядное дополнение)
ДК – дополнительный код
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017

9.

Компьютерная арифметика
Целочисленная арифметика.
Примеры преобразования двоичного кода
Десятичное число 17
ПК => 00010001
ОК => 11101110
ДК => 11101111
(021 – восьмеричное)
(356 – восьмеричное)
(357 – восьмеричное)
Десятичное число –17
ДК => 11101111
ОК => 00010000
ПК => 00010001
(357 – восьмеричное)
(020 – восьмеричное)
(021 – восьмеричное)
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017

10.

Компьютерная арифметика
Целочисленная арифметика.
Примеры преобразования “десятичного” кода
Десятичное число 17
ПК => 0017
ОК => 9982
ДК => 9983
Десятичное число –17
ДК => 9983
ОК => 0016
ПК => 0017
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017

11.

Компьютерная арифметика
Целочисленная арифметика.
Примеры получения обратного кода
Десятичное число 17
ПК => 00010001
ОК => 11101110
(021 – восьмеричное)
(356 – восьмеричное)
Поразрядное дополнение до r – 1
Двоичный код (r = 2)
11111111
00010001
11101110
Восьмеричный код (r = 8)
377
021
356
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017

12.

Компьютерная арифметика
Целочисленная арифметика.
Примеры получения обратного кода
Десятичное число –17
ДК => 11101111
ОК => 00010000
(357 – восьмеричное)
(020 – восьмеричное)
Поразрядное дополнение до r – 1
Двоичный код (r = 2)
11111111
11101111
00010000
Восьмеричный код (r = 8)
377
357
020
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017

13.

Компьютерная арифметика
Целочисленная арифметика.
Примеры получения обратного “десятичного” кода
Десятичное число 17
ПК => 0017
ОК => 9982
Поразрядное дополнение до r – 1
“Десятичный” код (r = 10)
9999
0017
9982
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017

14.

Компьютерная арифметика
Целочисленная арифметика.
Примеры получения обратного “десятичного” кода
Десятичное число –17
ДК => 9983
ОК => 0016
Поразрядное дополнение до r – 1
“Десятичный” код (r = 10)
9999
9983
0016
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017

15.

Компьютерная арифметика
Вещественная арифметика
Числа с плавающей точкой в оперативной памяти компьютера
хранятся в виде конкатенации (“склейки”) трёх двоичных полей:
знака числа – S (от слова sign), 0 – для неотрицательных чисел, 1 –
для отрицательных;
смещённого (увеличенного на фиксированную подставку) двоичного
порядка числа – E + подставка (от слова exponent);
нормализованной мантиссы числа – M (от слова mantissa).
Примечание:
значение подставки определяется типом числа и разрядностью
архитектуры компьютера;
нормализованный вид мантиссы предполагает отсутствие ведущей
(старшей) единицы при её записи.
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017

16.

Компьютерная арифметика
Вещественная арифметика
Например, для 32-разрядной архитектуры размеры указанных
двоичных полей для внутреннего представления чисел с плавающей
точкой типа single для языка программирования Pascal или float для
языков программирования C и C++ будут такими:
S
– 1 двоичный разряд;
E + 127
– 8 двоичных разрядов;
M
– 23 двоичных разряда.
Число с плавающей точкой 122.0
01000010111101000000000000000000
42f40000
S = 02
c2f40000
S = 12
Число с плавающей точкой – 122.0
11000010111101000000000000000000
E + 127 = 100001012
M = 111010000000000000000002
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017

17.

Компьютерная арифметика
Вещественная арифметика. Примеры
Число с плавающей точкой 0.0
00000000000000000000000000000000
00000000
Число с плавающей точкой 0.1
00111101110011001100110011001101
3dcccccd
Число с плавающей точкой 0.5
00111111000000000000000000000000
3f000000
Число с плавающей точкой 1.0
00111111100000000000000000000000
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017
3f800000

18.

Компьютерная арифметика
Вещественная арифметика. Алгоритм упаковки
Число с плавающей точкой 122.0
1. S = 0, так как число неотрицательное.
2. E = 6, так как 64 < 122 < 128 (здесь 64 – это 26, а 128 – это 27).
3. Смещённый порядок E +127 = 133 (2058 в восьмеричной системе
счисления или 100001012 – в двоичной).
4. Вычислим нормализованную мантиссу числа. Разделим 122 на 64 и
представим результат деления в виде вещественного числа с
фиксированной точкой (целая часть, точка, дробная часть) – 1.90625,
затем ведущую (старшую) единицу отбросим и получим число 0.90625.
Теперь от десятичной системы счисления перейдём к двоичной,
получим число 0.111012. Итак, M = 0.111012.
Результат конкатенации (“склейки”) трёх двоичных полей:
01000010111101000000000000000000
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017

19.

Компьютерная арифметика
Вещественная арифметика. Алгоритм распаковки
Получив представление об алгоритме упаковки (прямая задача),
выясним, как распаковывается 32-разрядное двоичное поле, с тем
чтобы получить число с плавающей точкой в десятичной системе
счисления, зная формат его хранения (обратная задача).
Пусть объект, представляющий собой 32-разрядный двоичный код
после упаковки числа с плавающей точкой, называется F, тогда:
знак S будет определяться как F31,
двоичный порядок E будет вычисляться как
F3027 + F2926 + F2825 + F2724 + F2623 + F2522 + F2421 + F2320 – 12710,
нормализованная мантисса М будет вычисляться как
F222-1 + F212-2 + … + F02-23.
Тогда число с плавающей точкой в десятичной системе счисления
будет вычисляться как (– 1)S(1 + M)2E.
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017

20.

Компьютерная арифметика
Вещественная арифметика. Пример распаковки
Число с плавающей точкой 122.0
Двоичный код
01000010111101000000000000000000
Представим в десятичной системе счисления число с плавающей
точкой по двоичному коду его внутреннего представления:
1. Знак S = 0.
2. Двоичный порядок E = 6
(100001012 – 12710 = 128 + 4 + 1 – 127 = 6).
3. Нормализованная мантисса М = 0.90625
(111010000000000000000002 = 2-1 + 2-2 + 2-3 + 2-5 =
0.5 + 0.25 + 0.125 + 0.03125 = 0.90625).
Итак, (– 1)S(1 + M)2E = (– 1)0(1 + 0.90625)26 = 122.0
Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород, 2017