К. Поляков, Компьютерная арифметика 1.Особенности представления чисел в компьютереОсобенности представления чисел в компьютере 2.Хранение в памяти целых чиселХранение в памяти целых чисел 3.Операции с целыми числамиОперации с целыми числами 4.Хранение в памяти вещественных чиселХранение в памяти вещественных чисел 5.Операции с вещественными числамиОперации с вещественными числами

К. Поляков, Компьютерная арифметика Тема 1. Особенности представления чисел в компьютере

Компьютерная арифметика К. Поляков, Предельные значения чисел В математике нет предельных значений! В компьютере – конечное число деталей, ограниченное количество разрядов. Какой диапазон? ? 10000?

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

Компьютерная арифметика К. Поляков, Вещественные числа 5 система счисления с основанием B F разрядов в дробной части Какой диапазон? ?

Компьютерная арифметика К. Поляков, Неточность представления 6 Не все вещественные числа могут быть представлены в компьютере точно ! ! 0, ,3211 0,3212 0,3214

Компьютерная арифметика К. Поляков, Дискретность 7 1.Целые числа дискретны. 2.Вещественные числа непрерывны. 3.Компьютер работает только с дискретными данными. 4.При дискретизации может происходить потеря информации (искажение данных). 5.Большинство трудностей связано с кодированием вещественных чисел. Для хранения вещественных чисел нужна дискретизация ! !

К. Поляков, Компьютерная арифметика Тема 2. Хранение в памяти целых чисел

Компьютерная арифметика К. Поляков, Целые числа без знака (unsigned) 9 78 = Беззнаковые данные – не могут быть отрицательными биты младший старший старший полубайт старшая цифра младший полубайт младшая цифра 4 16 E = 4E 16 = N

Компьютерная арифметика К. Поляков, Целые числа без знака 10 01…127128… …7F …FF … … C0 16 FF FF 16 C В газете «Информатика» (1/2011) есть опечатки на этой схеме: вместо «64» набрано «-64»!

Компьютерная арифметика К. Поляков, Целые числа без знака: диапазон 11 KX min X max типы данных byte (Паскаль) unsigned char (Си) word (Паскаль) unsigned short (Си) cardinal (Delphi) unsigned int (Си) ?

Компьютерная арифметика К. Поляков, Целые числа со знаком 12 Сколько места требуется для хранения знака? ? Старший (знаковый) бит числа определяет его знак. Если он равен 0, число положительное, если 1, то отрицательное. Прямой код: 78 = – 78 = – < 0< 0 < 0< 0 операции с положительными и отрицательными числами выполняются по-разному!

Компьютерная арифметика К. Поляков, Целые числа со знаком 13 Идея: «– 1» должно быть представлено так, чтобы при сложении с числом «1» получить 0. Как кодируется «-1»? ? Для 8-битных чисел: код числа «–X» равен двоичному коду числа 256 – X (дополнение до 256). При K-битном кодировании дополнительный код числа «–X» равен двоичному коду числа 2 K – X (дополнение до 2 K ). !

Компьютерная арифметика К. Поляков, Как построить дополнительный код? 14 Алгоритм А0: перевести число 2 K – X в двоичную систему счисления. для вычислений требуется K+1 разряд Алгоритм А1: 1)перевести число X в двоичную систему счисления; 2)построить обратный код, выполнив инверсию всех битов (заменить 0 на 1 и наоборот); 3)к результату добавить 1. Алгоритм А1: 1)перевести число X в двоичную систему счисления; 2)построить обратный код, выполнив инверсию всех битов (заменить 0 на 1 и наоборот); 3)к результату добавить = инверсия +1+1

Компьютерная арифметика К. Поляков, Как построить дополнительный код? 15 Алгоритм А2: 1)перевести число X-1 в двоичную систему счисления; 2)выполнить инверсию всех битов. Алгоритм А2: 1)перевести число X-1 в двоичную систему счисления; 2)выполнить инверсию всех битов = 77 = инверсия Алгоритм А3: 1)перевести число X в двоичную систему счисления; 2)выполнить инверсию всех старших битов числа, кроме младшей единицы и нулей после нее. Алгоритм А3: 1)перевести число X в двоичную систему счисления; 2)выполнить инверсию всех старших битов числа, кроме младшей единицы и нулей после нее. 78 = инверсия

Компьютерная арифметика К. Поляков, Целые числа со знаком 16 –128–127…–1 0… …FF …7F … … F С FF – 128 – 1– – – – 128 – F 16 С FF

Компьютерная арифметика К. Поляков, Целые числа co знаком: диапазон 17 KX min X max типы данных 8– shortInt (Delphi) char (Си) 16– smallInt (Delphi) short (Си) 32 – integer (Delphi) int (Си) 64 – – 1 int64 (Delphi) long long (Си)

К. Поляков, Компьютерная арифметика Тема 3. Операции с целыми числами

Компьютерная арифметика К. Поляков, Сложение и вычитание 19 Операции с положительными и отрицательными числами выполняются по одинаковым алгоритмам! ! Вычитание = сложение с дополнительным кодом вычитаемого! !

Компьютерная арифметика К. Поляков, Переполнение 20 знаковый бит бит переноса Если бит переноса не совпадает со знаковым битом результата, произошло переполнение и результат неверный. ! СS СS

Компьютерная арифметика К. Поляков, Умножение Умножение выполняется в помощью сложения и сдвига. ! × ×

Компьютерная арифметика К. Поляков, Поразрядные логические операции 22 Поразрядные операции выполняются с отдельными битами числа и не влияют на остальные. Сложение – это поразрядная операция? ? регистр Операция «НЕ» (инверсия, not): R not R

Компьютерная арифметика К. Поляков, Логическая операция «И» ( and, & ) 23 DMD and M данные маска Маска – константа, которая определяет область применения логической операции к битам многоразрядного числа. С помощью операции «И» можно сбросить (установить в ноль) биты, для которых маска равна 0! ! D D and M M AA 16 6С AA 16 and 6C 16 = ?

Компьютерная арифметика К. Поляков, Логическая операция «ИЛИ» ( or, | ) 24 DMD or M С помощью операции «ИЛИ» можно записать единицу в биты, для которых маска равна 1! ! D D or M M AA 16 6С 16 EE AA 16 or 6C 16 = ?

Компьютерная арифметика К. Поляков, Операция «исключающее ИЛИ» ( xor, ^ ) 25 DMD xor M С помощью операции «исключающее ИЛИ» можно инвертировать биты, для которых маска равна 1! ! D D xor M M AA 16 6С 16 C AA 16 xor 6C 16 = ?

Компьютерная арифметика К. Поляков, Шифрование с помощью xor 26 Идея: (A xor B) xor B = Операция «исключающее ИЛИ» обратима, то есть ее повторное применение восстанавливает исходное значение! ! A Текст: 2*2=4 Коды символов: '2' = = '*' = 2A 16 = '=' = 3D 16 = '4' = =

Компьютерная арифметика К. Поляков, Шифрование с помощью xor 27 Исходный текст: 2*2=4 '2' xor = '*' 2A 16 xor = '=' 3D 16 xor = '4' xor = '%' 3D 16 '=' 2A 16 '*' '#' Маска: 23 = = Зашифрованный текст: %=%*# Расшифровка: '%' xor = '=' 3D 16 xor = '*' 2A 16 xor = '#' xor = '2' 2A 16 '*' 3D 16 '=' '4' В газете «Информатика» (1/2011) есть опечатка: вместо «%=%*#» набрано «%=%7*7#»!

Компьютерная арифметика К. Поляков, Логический сдвиг Влево: бит переноса С Вправо: С 0 Си: Паскаль: N = N > 1; N = N > 1; N := N shl 1; N := N shr 1; N := N shl 1; N := N shr 1; shift left shift right

Компьютерная арифметика К. Поляков, Логический сдвиг Влево: Вправо: Если число нечётное? ? Логический сдвиг влево (вправо) – это быстрый способ умножения (деления без остатка) положительного числа на 2. Если число отрицательное? ?

Компьютерная арифметика К. Поляков, Арифметический сдвиг (вправо) 30 –12 Если число нечётное? ? С – 6 Примеры: –20 –15 –11 –3–3 –1 –10 –8 –6 –2 –1 Арифметический сдвиг вправо – деление на 2 нацело с округлением «вниз» (к ближайшему меньшему целому).

Компьютерная арифметика К. Поляков, Циклический сдвиг Влево: Вправо: Циклический сдвиг предназначен для последовательного просмотра битов без потери данных. !

Компьютерная арифметика К. Поляков, Пример 32 Задача: в целой переменной N (32 бита) закодирована информация о цвете пикселя в RGB: Записать в переменные R, G, B составляющие цвета. Вариант 1: 1.Обнулить все биты, кроме G. Маска для выделения G: 0000FF Сдвинуть вправо так, чтобы число G передвинулось в младший байт. 0RGB Си: G =(N & 0xFF00) >> 8; Паскаль: G:=(N and $FF00) shr 8;

Компьютерная арифметика К. Поляков, Пример 33 Вариант 2: 1.Сдвинуть вправо так, чтобы число G передвинулось в младший байт. 2.Обнулить все биты, кроме G. Маска для выделения G: FF 16 0RGB Си: G =(N >> 8) & 0xFF; Паскаль: G:=(N shr 8) and $FF; Как решить, используя только сдвиги? ?

Компьютерная арифметика К. Поляков, Пример 34 0RGB Си: R =B =R =B = R =B =R =B = Паскаль: R:= B:= R:= B:=

К. Поляков, Компьютерная арифметика Тема 4. Хранение в памяти вещественных чисел

Компьютерная арифметика К. Поляков, Хранение вещественных чисел 36 С фиксированной запятой (в первых ЭВМ): целая частьдробная часть для больших и маленьких чисел нужно масштабирование 0, ,0 С плавающей запятой (автоматическое масштабирование): знакпорядок P значащая часть Z положение запятой цифры числа 1,2345· ,2345·10 17

Компьютерная арифметика К. Поляков, Хранение вещественных чисел 37 Теоретически оптимальный вариант (целая часть = 0): 0, = 0,12345· ,345 = 0,12345·10 2 X 10 всегда 0 один разряд расходуется впустую! Экономный вариант (целая часть от 1 до B): основание системы счисления X 10 0, = 1,2345· ,345 = 1,2345·10 1 повышение точности при конечном числе разрядов

Компьютерная арифметика К. Поляков, Нормализация 38 Нормализованная форма: значащая часть Z удовлетворяет условию 1 Z < B, где B – основание системы счисления (стандарт IEEE 754). Пример: 17,25 = 10001,01 2 = 1, ·2 4 5,375 = 7,625 = 27,875 = 13,5 = 0,125 = всегда 1, её можно не хранить в памяти!

Компьютерная арифметика К. Поляков, Число обычной точности (single) ,25 = ,01 2 = -1, ·2 4 знакпорядокзначащая часть single: 4 байта = 32 бита мантисса = дробная часть Z порядок со смещением знак p = = 131 = С18A000 0 для single

Компьютерная арифметика К. Поляков, Диапазон вещественных чисел 40 типдиапазон число десятичных значащих цифр размер (байт) single1,4· – 3,4· double4,9· – 1,8· extended3,6· – 1,2· Extended – тип для вычислений в сопроцессоре, единица в значащей части не скрывается. Single, double – только для хранения.

К. Поляков, Компьютерная арифметика Тема 5. Операции с вещественными числами

Компьютерная арифметика К. Поляков, Сложение и вычитание 42 1)порядки выравниваются до большего 2)значащие части складываются (или вычитаются) 3)результат нормализуется Как сложить два числа с плавающей запятой? ! 1,2345·10 – 5 + 1,2345·10 5 = ? Пример: 7,25 = 111,01 2 = 1, ·2 2 1,75 = 1,11 2 = 1,11 2 ·2 0 1,75 = 0, ·2 2 1, ,011120, , ,01 2 ·2 2 = 1,001 2 ·2 3 Почему порядки выравнивают до большего? ?

Компьютерная арифметика К. Поляков, Умножение и деление 43 Как умножить два числа с плавающей запятой? ! 1,2345·10 – 5 · 1,2345·10 5 = ? 1)значащие части умножаются (или делятся) 2)порядки складываются (или вычитаются) 3)результат нормализуется Пример: 1,75 = 1,11 2 = 1,11 2 ·2 0 6 = = 1,1 2 ·2 2 1,11 2 ·1,1 2 = 10, ,101 2 ·2 2 = 1, ·2 3 Надо ли выравнивать порядки? ? = = 2

Компьютерная арифметика К. Поляков, Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики высшей категории, ГОУ СОШ 163, г. Санкт-Петербург