1 Компьютерная арифметика § 26. Особенности представления чисел в компьютере § 27. Хранение в памяти целых чисел § 28. Операции с целыми числами § 29. Хранение в памяти вещественных чисел § 30. Операции с вещественными числами
§ 26. Особенности представления чисел в компьютере 2
3 В математике нет предельных значений! В компьютере – конечное число деталей, ограниченное количество разрядов. Какой диапазон? ? 100 0 0 ?
4 система счисления с основанием B K разрядов Переполнение разрядной сетки — это ситуация, когда число, которое требуется сохранить, не умещается в имеющемся количестве разрядов вычислительного устройства.
5 система счисления с основанием B F разрядов в дробной части Какой диапазон? ?
6 Не все вещественные числа могут быть представлены в компьютере точно ! ! 0,1234 567 0,3211 0,3212 0,3214
7 хранится неточно! При сравнении вещественных чисел желательно избегать операции «равно» ! ! неточный результат! допустимая погрешность (10 -6 )
8 Целые числа дискретны. Вещественные числа непрерывны. Компьютер работает только с дискретными данными. При дискретизации может происходить потеря информации (искажение данных). Большинство трудностей связано с кодированием вещественных чисел. Для хранения вещественных чисел нужна дискретизация ! !
§ 27. Хранение в памяти целых чисел 9
10 78 = 1001110 2 Беззнаковые данные – не могут быть отрицательными. 0 1 0 0 1 1 1 0 7 6 5 4 3 2 1 0 биты младший старший старший полубайт старшая цифра младший полубайт младшая цифра 4 16 E 16 1001110 2 = 4E 16 = ‘N’
11 0 1 … 127 128 … 255 00 16 01 16 … 7 F 16 80 16 … FF 16 0000 0000 2 0000 0001 2 … 0111 1111 2 1000 0000 2 … 1111 1111 2 1111 1111 + 0000 0001 1 0000 000 0 255 128 0 64 192 C0 16 FF 16 4 0 16 0 16 80 16 0 FF 16 C0 16 40 16 128 80 16 255 64 192
12 K X min X max типы данных 8 0 255 byte ( Паскаль ) unsigned char ( Си ) 16 0 65 535 word ( Паскаль ) unsigned short ( Си ) 32 0 4 294 967 295 cardinal ( Delphi ) unsigned int ( Си ) 64 0 18 446 744 073 709 551 615 unsigned long long ( Си ++ )
13 Сколько места требуется для хранения знака? ? Старший (знаковый) бит числа определяет его знак. Если он равен 0, число положительное, если 1, то отрицательное. Прямой код : 78 = 1001110 2 0 1 0 0 1 1 1 0 – 78 = –1001110 2 1 1 0 0 1 1 1 0 ≥ 0 < 0 операции с положительными и отрицательными числами выполняются по-разному!
14 Идея : « – 1» должно быть представлено так, чтобы при сложении с числом «1» получить 0. Как кодируется «-1»? ? 1111 1111 + 0000 0001 1 0000 000 0 -1 255 1 256 Для 8-битных чисел : код числа « – X » равен двоичному коду числа 256 – X ( дополнение до 256). При K- битном кодировании дополнительный код числа « – X » равен двоичному коду числа 2 K – X ( дополнение до 2 K ). !
15 Алгоритм А0: перевести число 2 K – X в двоичную систему счисления. для вычислений требуется K+1 разряд Алгоритм А 1 : перевести число X в двоичную систему счисления; построить обратный код, выполнив инверсию всех битов (заменить 0 на 1 и наоборот); к результату добавить 1. 78 = 0 1001110 2 10110001 - 78 10 1100 10 инверсия + 1
16 Алгоритм А2: перевести число X -1 в двоичную систему счисления; выполнить инверсию всех битов. 78 - 1 = 77 = 0 10011 01 2 инверсия Алгоритм А 3 : перевести число X в двоичную систему счисления; выполнить инверсию всех старших битов числа, кроме младшей единицы и нулей после нее. 78 = 0 10011 10 2 - 78 10 1100 10 - 78 10 1100 10 инверсия
17 –128 –127 … –1 0 … 127 80 16 81 16 … FF 16 00 16 … 7F 16 1 000 0000 2 1 000 0001 2 … 1 111 1111 2 0000 0000 2 … 0111 1111 2 80 16 7 F 16 40 16 С 0 16 0 1 FF 16 1 27 – 1 28 – 1 64 1 – 64 127 – 1 0 1 – 128 – 64 64 40 16 7 F 16 С 0 16 80 16 FF 16 01 16
18 K X min X max типы данных 8 – 128 127 shortInt ( Delphi ) char ( Си ) 16 – 32 768 32 767 smallInt ( Delphi ) short ( Си ) 32 – 2 147 483 648 2 147 483 64 7 integer ( Delphi ) int ( Си ) 64 – 2 63 2 63 – 1 int64 ( Delphi ) long long ( Си )
§ 28. Операции с целыми числами 19
20 Операции с положительными и отрицательными числами выполняются по одинаковым алгоритмам! ! Вычитание = сложение с дополнительным кодом вычитаемого! ! 0000 0101 1111 0111 + 1111 1 1 00 -4 - 9 5 +
21 знаковый бит дополнительный бит Если бит переноса не совпадает с битом S’, произошло переполнение и результат неверный. ! 0110000 0 0 0 10000 1 + 0 10 0 0000 1 96 33 -127 S ’ S 0 0 1 0 1 1 011111 10 10000 0 + 1 0111111 1 -96 - 33 127 S ’ S 1 1 0 1
22 9 5 4 5 Умножение выполняется с помощью сложения и сдвига. ! 00001001 × 00000 1 01 00001001 00000000 00000 1 0 1 0000101101 + - 9 5 -4 5 1111 0 11 1 × 00000 1 01 1111 0 11 1 00000000 1111 0 11 1 1 00 1101001 1 +
23 Поразрядные операции выполняются с отдельными битами числа и не влияют на остальные. Сложение – это поразрядная операция? ? 0 1 0 0 1 0 0 0 регистр Операция «НЕ» (инверсия, not ): 1 0 0 1 1 0 1 0 R not R 0 1 1 0 0 1 0 1
24 D M D and M 0 0 0 1 0 0 0 1 0 1 1 1 данные маска Маска – константа, которая определяет область применения логической операции к битам многоразрядного числа. С помощью операции «И» можно сбросить (установить в ноль) биты, для которых маска равна 0! ! 1 0 1 0 1 0 1 0 D D and M 0 1 1 0 1 1 0 0 M 0 0 1 0 1 0 0 0 AA 16 6С 16 28 16 7 6 5 4 3 2 1 0 AA 16 and 6C 16 = ?
25 D M D or M 0 0 0 1 0 1 0 1 1 1 1 1 С помощью операции «ИЛИ» можно записать единицу в биты, для которых маска равна 1! ! 1 0 1 0 1 0 1 0 D D or M 0 1 1 0 1 1 0 0 M 1 1 1 0 1 1 1 0 AA 16 6С 16 EE 16 7 6 5 4 3 2 1 0 AA 16 or 6C 16 = ?
26 D M D xor M 0 0 0 1 0 1 0 1 1 1 1 0 С помощью операции «исключающее ИЛИ» можно инвертировать биты, для которых маска равна 1! ! 1 0 1 0 1 0 1 0 D D xor M 0 1 1 0 1 1 0 0 M 1 1 0 0 0 1 1 0 AA 16 6С 16 C6 16 7 6 5 4 3 2 1 0 AA 16 xor 6C 16 = ?
27 Идея: ( A xor B ) xor B = Операция «исключающее ИЛИ» обратима, то есть ее повторное применение восстанавливает исходное значение! ! A Текст: 2*2=4 Коды символов: '2' = 32 16 = 00110010 2 '*' = 2A 16 = 00101010 2 '=' = 3D 16 = 00111101 2 '4' = 34 16 = 00110100 2
28 Исходный текст: 2*2=4 '2' 32 16 xor 17 16 = '*' 2A 16 xor 17 16 = '=' 3D 16 xor 17 16 = '4' 34 16 xor 17 16 = 2 5 16 ' % ' 3D 16 '=' 2A 16 '*' 23 16 '#' Маска: 23 = 17 16 = 00010111 2 Зашифрованный текст: %=%* # Расшифровка: '%' 25 16 xor 17 16 = '=' 3D 16 xor 17 16 = '*' 2A 16 xor 17 16 = '#' 23 16 xor 17 16 = 32 16 ' 2 ' 2A 16 ' * ' 3 D 16 ' = ' 3 4 16 ' 4 '
29 1 0 0 1 1 0 1 1 Влево: 0 0 1 1 0 1 1 0 1 0 бит переноса С Вправо: 1 0 0 1 1 0 1 1 0 1 0 0 1 1 0 1 1 С 0 Си: Паскаль: N = N << 1; N = N >> 1; N := N shl 1 ; N := N shr 1 ; shift left shift right
30 0 0 0 0 1 1 0 0 Влево: 12 0 0 0 1 1 0 0 0 24 0 0 0 0 1 1 0 0 Вправо: 12 0 0 0 0 0 1 1 0 6 Если число нечётное? ? Логический сдвиг влево (вправо) – это быстрый способ умножения (деления без остатка) положительного числа на 2. Если число отрицательное? ?
31 –12 Если число нечётное? ? 1 1 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 С – 6 Примеры: 20 1 5 1 1 3 1 10 7 5 1 0 –20 –1 5 –1 1 – 3 –1 –10 – 8 –6 – 2 –1 Арифметический сдвиг вправо – деление на 2 нацело с округлением «вниз» (к ближайшему меньшему целому).
32 1 0 0 1 1 0 1 1 Влево: 0 0 1 1 0 1 1 1 Вправо: 1 0 0 1 1 0 1 1 1 1 0 0 1 1 0 1 Циклический сдвиг предназначен для последовательного просмотра битов без потери данных. !
33 Задача : в целой переменной N ( 32 бита ) закодирована информация о цвете пикселя в RGB : Записать в переменные R, G, B составляющие цвета. Вариант 1 : Обнулить все биты, кроме G. Маска для выделения G : 00 00FF00 16 Сдвинуть вправо так, чтобы число G передвинулось в младший байт. 0 R G B 31 24 23 16 15 8 7 0 Си: G =(N & 0xFF00) >> 8; Паскаль: G:=(N and $FF00) shr 8;
34 Вариант 2 : Сдвинуть вправо так, чтобы число G передвинулось в младший байт. Обнулить все биты, кроме G. Маска для выделения G : 000000 FF 16 0 R G B 31 24 23 16 15 8 7 0 Си: G =(N >> 8 ) & 0xFF; Паскаль: G:=(N shr 8 ) and $FF; Как решить, используя только сдвиги? ?
35 0 R G B 31 24 23 16 15 8 7 0 Си: R = B = Паскаль: R:= B:=
§ 29. Хранение в памяти вещественных чисел 36
37 С фиксированной запятой (в первых ЭВМ) : целая часть дробная часть для больших и маленьких чисел нужно масштабирование 0,000000000000012345 123450000000000000,0 С плавающей запятой (автоматическое масштабирование) : знак порядок P значащая часть Z положение запятой цифры числа 1, 2345· 10 -14 1, 2345· 10 1 7
38 Теоретически оптимальный вариант (целая часть = 0) : 0,0012345 = 0, 12345· 10 -2 12, 345 = 0,12345 · 10 2 X 10 всегда 0 один разряд расходуется впустую! Экономный вариант (целая часть от 1 до B ) : основание системы счисления X 10 0,0012345 = 1, 2345· 10 -3 12, 345 = 1,2345 · 10 1 повышение точности при конечном числе разрядов
39 Нормализованная форма : значащая часть Z удовлетворяет условию 1 ≤ Z < B, где B – основание системы счисления ( стандарт IEEE 754 ). Пример : 17,25 = 10001,01 2 = 1,000101 2 ·2 4 5,375 = 7,625 = 27,875 = 13,5 = 0,125 = всегда 1, её можно не хранить в памяти!
40 - 17,25 = - 10001,01 2 = - 1,000101 2 ·2 4 знак порядок значащая часть single : 4 байта = 32 бита 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 31 0 22 30 23 мантисса = дробная часть Z порядок со смещением знак p = 4 + 127 = 1 31 = 100000 11 2 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 С 1 8 A 0 0 0 0 для single
41 тип диапазон число десятичных значащих цифр размер (байт) single 1,4·10 -45 – 3,4·10 38 7-8 4 double 4,9·10 -324 – 1,8·10 308 15-16 8 extended 3,6·10 -4951 – 1,2·10 4932 19-20 10 Extended – тип для вычислений в сопроцессоре, единица в значащей части не скрывается. Single, double – только для хранения.
§ 30. Операции с вещественными числами 42
43 порядки выравниваются до большего значащие части складываются (или вычитаются) результат нормализуется Как сложить два числа с плавающей запятой? ! 1,2345 ·10 – 5 + 1,2345 ·10 5 = ? Пример: 7,25 = 111,01 2 = 1,1101 2 ·2 2 1, 7 5 = 1, 1 1 2 = 1,11 2 ·2 0 1, 7 5 = 0,0111 2 ·2 2 1,1101 2 0, 0 1 1 1 2 + 1 0, 0 100 2 10,01 2 ·2 2 = 1,001 2 ·2 3 Почему порядки выравнивают до большего? ?
44 Как умножить два числа с плавающей запятой? ! 1,2345 ·10 – 5 · 1,2345 ·10 5 = ? значащие части умножаются (или делятся) порядки складываются (или вычитаются) результат нормализуется Пример: 1, 7 5 = 1, 1 1 2 = 1, 1 1 2 ·2 0 6 = 1 1 0 2 = 1, 1 2 ·2 2 1,1 1 2 · 1,1 2 = 1 0, 1 01 2 1 0, 1 01 2 ·2 2 = 1, 01 01 2 ·2 3 Надо ли выравнивать порядки? ? 0 + 2 = 2
45 Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru ЕРЕМИН Евгений Александрович к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь eremin@pspu.ac.ru
46 авторские материалы
