Системы счисления и действия в них

Содержание

Слайд 2

Цель: рассмотреть основные понятия числовых систем; правила построения систем; выполнение действий в системах счисления.

Цель: рассмотреть
основные понятия числовых систем;
правила построения систем;
выполнение действий в системах счисления.


Слайд 3

Алфавит Х из р символов и правила записи (изображения) и обработки

Алфавит Х из р символов и правила записи (изображения) и обработки

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

Система счисления

Слайд 4

Система счисления Любая система счисления – это система кодирования числовых величин

Система счисления

Любая система счисления – это система кодирования числовых величин (количеств),

позволяющая выполнять операции кодирования и декодирования, то есть по любой количественной величине однозначно находить его кодовое представление и по любой кодовой записи – восстанавливать соответствующую ей числовую величину.
Наиболее используемые в информатике системы счисления:
двоичная, над алфавитом Х = {0,1};
восьмеричная, над Х = {0, 1, 2, 3, 4, 5, 6, 7};
шестнадцатеричная, над Х = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С, D, Е, F}, где символы А, В, С, D, Е, F имеют десятичные веса 10, 11, 12, 13, 14, 15.
Слайд 5

Основные понятия кодирования и шифрования Все системы счисления строятся по общему

Основные понятия кодирования и шифрования

Все системы счисления строятся по общему

принципу: определяется величина р – основание системы, а любое число х записывается в виде комбинации степеней веса р от 0-й до n-й степени следующим образом:
(x)10 = xnpn + xn–1pn–1 + ... + x1p1 + x0p0 , где (n+1) – количество разрядов в числе x
Пример.
11012 = 1 x 23 + 1 x 22 + 0 x 21 + 1 x 20 = 8 + 4 + 1 = 1310 ,
1578 = 1 x 82 + 5 x 81 + 7 x 80 = 64 + 40 + 7 = 11110 ,
A6F16 = 10 x 256 + 6 x 16 + 15 x 1 = 267110 .
110,0012 = 1x22 + 1 x 21 + 0 x 20 + 0 x 2-1 + 0 x 2-2 + 1 x 2-3 = 6,12510 ;
A,B16 = A x 160 + B x 16-1 = 10 x 1 + 11 x 0,0625 = 10,687510 .
Слайд 6

Позиционные и непозиционные системы счисления Система счисления в которой вес цифры

Позиционные и непозиционные системы счисления

Система счисления в которой вес цифры

(или символа алфавита) зависит от ее места в записи числа или слова называется позиционной; в противном случае система называется непозиционной.
Непозиционная система – древняя римская система записи чисел с алфавитом вида Х={I (1), V (5), Х (10), L (50), С (100), D (500), М (1000)}.
Примеры римских чисел: III (3), IV (4), V (5), VI (6), IX (9), XI (11), DCL (650).
Запись числа в этой системе получается двусторонней конкатенацией, причем правая конкатенация ассоциируется с добавлением, а левая конкатенация – с убавлением (например, IV и VI).
Слайд 7

Процедура перевода десятичных чисел в р-ную систему счисления: перевести отдельно целую

Процедура перевода десятичных чисел в р-ную систему счисления:

перевести отдельно целую

часть числа х:
последовательно делить целую часть [х]10, а затем все частные (получаемые при делении) на р до тех пор, пока не получим в очередном частном число меньшее р; результат получается последовательным приписыванием к последнему частному остатков от деления – от последнего до первого;
перевести отдельно дробную часть (мантиссу) числа:
последовательно умножать исходную мантиссу, а затем мантиссы получаемых чисел на р до тех пор, пока не получим мантиссу, равную нулю, или нужное количество цифр в {х}p ; результат получается приписыванием к целой части первого произведения второй такой же цифры и т.д., до последней цифры целой части;
итоговый результат будет иметь вид (х)р = [х]p, {х}p .
Слайд 8

Пример: найти: 12,810 = ?2 Переводим целую часть: 1210 =11002; переводим

Пример: найти: 12,810 = ?2

Переводим целую часть: 1210 =11002;
переводим

дробную часть (выделены цифры, идущие в изображение мантиссы в двоичной системе) посредством умножения на 2:
0,8 x 2 = 1,6;
0,6 x 2 = 1,2;
0,2 x 2 = 0,4;
0,4 x 2 = 0,8;
и так далее до тех пор, пока не получится нулевая дробная часть или не будет достигнута требуемая точность
0,810 = 0,1100110...2 ;
результат перевода: 12,810 = 1100,1100110011...2 .
Слайд 9

Примеры Найдем 29,2510 = ?8 . Решение имеет вид 1) 2910

Примеры
Найдем 29,2510 = ?8 .
Решение имеет вид 1) 2910 = 358

; 2) 0,2510 = 0,28 ;
3) 29,2510 = 35,28 .
Найдем 79,2610 = ?16 .
Решение: 1) 7910 = 4F16 ; 2) 0,2610 = 0,4016 ;
3) 79,2610 = 4F,416.
При переводе дробной части ограничились нахождением двух значащих цифр после запятой, так как перевод точно сделать невозможно.
Слайд 10

Для перевода из 2-ной в 8-ную и наоборот, из 2-ной в

Для перевода из 2-ной в 8-ную и наоборот, из 2-ной в

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

Переводы в смешанных системах Из 2-ной системы в 8-ную (двоично-восьмеричное изображение):

Переводы в смешанных системах

Из 2-ной системы в 8-ную (двоично-восьмеричное изображение):


из 8-ной системы в 2–ную (восьмерично-двоичное изображение):
Слайд 12

Переводы в смешанных системах из 2-ной системы в 16-ную (двоично-шестнадцатеричное изображение):

Переводы в смешанных системах

из 2-ной системы в 16-ную (двоично-шестнадцатеричное изображение):
из 16-ной

системы в 2-ную (шестнадцатерично-двоичное изображение):
Слайд 13

Арифметические операции: Сложение в двоичной системе счисления осуществляется по правилам 0

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

Сложение в двоичной системе счисления осуществляется по правилам
0 +

0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 210 = 102 (единица идет в старший разряд).
Вычитание в двоичной системе счисления имеет вид
0 – 0 = 0, 1 – 0 = 1, 1 – 1 = 0, 10 – 1 = 1.
Умножение в двоичной системе счисления имеет вид
0 x 0 = 0, 0 x 1 = 0, 1 x 0 = 0, 1 x 1 = 1.
Деление в двоичной системе счисления имеет вид
0 : 0 = не определено, 1 : 0 = не определено,
0 : 1 = 0, 1 : 1 = 1.
Слайд 14

Как представляются целые числа? Обычно занимают в памяти компьютера один или

Как представляются целые числа?

Обычно  занимают  в  памяти  компьютера  один  или  два

 байта. В  однобайтовом  формате  принимают  значения  от  000000002   до   111111112. В двубайтовом формате - от  00000000 000000002   до   11111111 111111112.

Диапазоны значений целых чисел без знака

Слайд 15

Примеры: а) число 7210 = 10010002 в однобайтовом формате: б) это

Примеры:

а) число 7210 = 10010002 в однобайтовом формате:
б) это же число

в двубайтовом формате:
в) число 65535 в двубайтовом формате:

Номера разрядов
Биты числа

Номера разрядов
Биты числа

Номера разрядов
Биты числа

Слайд 16

Целые числа со знаком Обычно занимают в памяти компьютера один, два

Целые числа со знаком

Обычно занимают в памяти компьютера один, два или

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

Диапазоны значений целых чисел со знаком

Слайд 17

Прямой, обратный и дополнительный код. Рассмотрим особенности записи целых чисел со

Прямой,   обратный и  дополнительный код.

Рассмотрим особенности записи целых чисел со знаком

на примере однобайтового формата, при котором для знака отводится один разряд, а для цифр абсолютной величины - семь разрядов.
Положительные числа в прямом, обратном и дополнительном кодах изображаются одинаково - двоичными кодами с цифрой 0 в знаковом разряде. Например:

знак числа

Слайд 18

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

Прямой,   обратный и  дополнительный код.

Отрицательные числа в прямом, обратном и дополнительном

кодах имеют разное изображение.
1. Прямой код. В знаковый разряд помещается цифра 1, а в разряды цифровой части числа - двоичный код его абсолютной величины. Например:

Прямой код числа -1

Прямой код числа -127

Знак числа “-”

Знак числа “-”

Слайд 19

2. Обратный код. Получается инвертированием всех цифр двоичного кода абсолютной величины

2. Обратный код. Получается инвертированием всех цифр двоичного кода абсолютной величины

числа, включая разряд знака: нули заменяются единицами, а единицы — нулями. Например:
3. Дополнительный код. Получается образованием обратного кода с последующим прибавлением единицы к его младшему разряду. Например:

Прямой код числа -1

Обратный код числа -1

Прямой код числа -127

Обратный код числа -127

Дополнительный код числа -1

Дополнительный код числа -127

Слайд 20

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

Прямой,   обратный и  дополнительный код.

Обычно отрицательные десятичные числа при вводе в

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

Сложение обратных кодов. Здесь при сложении чисел А и В имеют

Сложение обратных кодов.

Здесь при сложении чисел А и В имеют место

четыре основных и два особых случая:
1. А и В положительные. При суммировании складываются все разряды, включая разряд знака. Так как знаковые разряды положительных слагаемых равны нулю, разряд знака суммы тоже равен нулю.
Слайд 22

2. А положительное, B отрицательное и по абсолютной величине больше, чем

2. А положительное, B отрицательное и по абсолютной величине больше, чем

А.
Получен правильный результат в обратном коде. При переводе в прямой код биты цифровой части результата инвертируются: 1 0000111 = -710.
3. А положительное, B отрицательное и по абсолютной величине меньше, чем А.
Компьютер исправляет полученный первоначально неправильный результат (6 вместо 7) переносом единицы из знакового разряда в младший разряд суммы.
Слайд 23

4. А и В отрицательные. Полученный первоначально неправильный результат (обратный код

4. А и В отрицательные.
Полученный первоначально неправильный результат (обратный код

числа -1110 вместо обратного кода числа -1010) компьютер исправляет переносом единицы из знакового разряда в младший разряд суммы. При переводе результата в прямой код биты цифровой части числа инвертируются:
1 0001010 = -1010.
При сложении может возникнуть ситуация, когда старшие разряды результата операции не помещаются в отведенной для него области памяти. Такая ситуация называется переполнением разрядной сетки формата числа. Для обнаружения переполнения и оповещения о возникшей ошибке в компьютере используются специальные средства.
Слайд 24

5. А и В положительные, сумма А+В больше, либо равна 2n-1,

5. А и В положительные, сумма А+В больше, либо равна 2n-1,

где n — количество разрядов формата чисел (для однобайтового формата n=8, 2n-1 = 27 = 128).
Семи разрядов цифровой части числового формата недостаточно для размещения восьмиразрядной суммы (16210 = 101000102), поэтому старший разряд суммы оказывается в знаковом разряде. Это вызывает несовпадение знака суммы и знаков слагаемых, что является свидетельством переполнения разрядной сетки.
Слайд 25

6. А и В отрицательные, сумма абсолютных величин А и В

6. А и В отрицательные, сумма абсолютных величин А и В

больше, либо равна 2n-1.
Здесь знак суммы тоже не совпадает со знаками слагаемых, что свидетельствует о переполнении разрядной сетки.
Слайд 26

Сложение дополнительных кодов. Здесь также имеют место рассмотренные выше шесть случаев:

Сложение дополнительных кодов.

Здесь также имеют место рассмотренные выше шесть случаев:
1.

А и В положительные. Здесь нет отличий от случая 1, рассмотренного для обратного кода.
2. А положительное, B отрицательное и по абсолютной величине больше, чем А.
Получен правильный результат в дополнительном коде. При переводе в прямой код биты цифровой части результата инвертируются и к младшему разряду прибавляется единица: 1 0000110 + 1 = 1 0000111 = -710.
Слайд 27

3. А положительное, B отрицательное и по абсолютной величине меньше, чем

3. А положительное, B отрицательное и по абсолютной величине меньше, чем

А.
Получен правильный результат. Единицу переноса из знакового разряда компьютер отбрасывает.
4. А и В отрицательные.
Получен правильный результат в дополнительном коде. Единицу переноса из знакового разряда компьютер отбрасывает.
Слайд 28

Обратный и дополнительный код Обратным кодом числа в системе с основанием

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

Обратным кодом числа в системе с основанием р

называется число в этой системе, получаемое заменой цифры, символа в каждом разряде числа на его дополнение до максимальной цифры в системе (то есть до р – 1).
Дополнительный код = обратный код + единица в младшем разряде.
Пример.10011 двоичное число,
01100 обратный код этого двоичного числа,
01101 дополнительный код этого двоичного числа;
Найти обратный и дополнительный коды для: 4578, А916.
Слайд 29

Точность Точность в чистой математике – понятие абстрактное и в вычислительной

Точность

Точность в чистой математике – понятие абстрактное и в вычислительной математике

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

Точность Так как диапазон n-разрядных чисел системы счисления с основанием p

Точность

Так как диапазон n-разрядных чисел системы счисления с основанием p находится

в пределах , то для представления дробных чисел этот диапазон еще снижается, поскольку часть разрядов необходимо отвести под изображение мантиссы. Таким образом, имеются так называемые "зоны нечувствительности" форм представления чисел в n-разрядных арифметиках.
Слайд 31

В 1937 году Конрадом Цузе для увеличения диапазона чисел, представимых в

В 1937 году Конрадом Цузе для увеличения диапазона чисел, представимых в

арифметике двоичных чисел, а также для повышения точности этого представления, было предложено использовать представление чисел в нормализованной форме с плавающей запятой, т. е. число x представляется в виде:
где m – мантисса числа, k – целый порядок числа,
p – основание
-0.000001 (одна миллионная):-0.1 ×10 − 5
В вычислительных машинах показатель степени принято отделять от мантиссы буквой "E" (exponent).
1,528535047×10-25 в большинстве языков программирования высокого уровня записывается как 1.528535047E-25.
Слайд 32

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

Пример:

Пусть даны два числа:
( ). Тогда можно проверить, что результаты выполнения

операций будут равны:
Слайд 33

Если из n разрядов, отводимых под изображение чисел, m двоичных разрядов

Если из n разрядов, отводимых под изображение чисел, m двоичных разрядов

отвести под мантиссу, k – под порядок, один разряд – под знак числа и один разряд – под знак порядка (например, 0 – плюс, 1 – минус), то диапазон представимых в форме с плавающей запятой чисел резко увеличивается (m + k + 2 = n):
(многоточие соответствует k единицам).
Слайд 34

Пример: Рассмотрим представление R с 3-разрядной мантиссой со знаком в диапазоне

Пример:
Рассмотрим представление R с 3-разрядной мантиссой со знаком в диапазоне 0,1≤

| f | < 1 и 2-разрядной экспонентой со знаком.
Диапазон от -0,100×10^(-99) до +0,999×10^(+99)
[199 разрядов, а для записи требуется 5 разрядов и 2 знака]
Слайд 35

Числа, меньшие нижней границы положительных чисел и большие верхней границы отрицательных

Числа, меньшие нижней границы положительных чисел и большие верхней границы отрицательных

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

Такое представление очень удобно для хранения в ЭВМ, так как на

Такое представление очень удобно для хранения в ЭВМ, так как на

самом деле необходимо хранить не само число, а его знак, мантиссу, порядок и знак порядка, и все операции с числами сводятся к операциям с этими объектами.
Операции же с этими объектами просты: сравнение знаков, увеличение, уменьшение порядка, сложение мантисс, нормализация, то есть в конечном итоге сводятся к достаточно просто реализуемым операциям сдвига, выравнивания, сравнения разрядов.
Слайд 37

-10^99 -10^(-100) 0 10^(-100) 10^(99) Отрицательное переполнение (1) Положительное переполнение (7)

-10^99 -10^(-100) 0 10^(-100) 10^(99)

Отрицательное переполнение (1)

Положительное переполнение (7)

Выражаемые отрицательные числа

(2)

Выражаемые положительные числа
(6)

Отрицательная потеря значимости
(3)

Положительная потеря значимости
(5)

Ось действительных чисел

 

и (7) – ошибка переполнения
(3) и (5) – ошибка потери значимости
(2) и (6) – промежутки между числами не постоянны

Нуль
(4)

Числа с плавающей точкой не образуют континуума. В двухзнаковой пятиразрядной системе можно выразить ровно 179 100 положительных чисел, 179 100 отрицательных числе и 0, т.е. всего 358201 чисел.

Слайд 38

К "неудобствам" этой формы представления чисел можно отнести возможность возникновения следующих

К "неудобствам" этой формы представления чисел можно отнести возможность возникновения следующих

"особо опасных" ситуаций:

если число достаточно мало, например, а = 0.12Е + 00, то оно может быть представлено любым числом из наименьшего интервала включающего а, в частности числом 0.120000001 или 0.199999999 и в этом случае сравнивать на равенство "в лоб" нельзя (вещественные числа в форме с плавающей запятой опасно сравнивать на совпадение);
порядок выполнения операций может влиять на результат, например, в 4-разрядной арифметике с фиксированной запятой 20.0000 + 0.0001 = 20.0001, но при этом 0.2000Е+02 + 0.1000Е–05 = 0.2000Е + 02;

Слайд 39

может возникнуть так называемая ситуация "переполнения порядка" при сложении (умножении) очень

может возникнуть так называемая ситуация "переполнения порядка" при сложении (умножении) очень

больших чисел или "исчезновения порядка" при сложении (умножении) "очень малых чисел“:
0.6000Е+39 × 0.1200Е+64 = 0.9999Е+99 (или же не определено)
0.6000Е–35 × 0.0200Е–65 = 0.9999Е – 99 (или же не определено)
при сложении чисел с плавающей запятой (а, в конечном счете, все операции выполняются через сложение) происходит выравнивание порядков для последующего сложения мантисс, а при выравнивании степеней может происходить потеря (усечение) младших разрядов, например, такая ситуация может возникнуть при сложении одного "очень большого числа" с одним "очень малым числом"
Слайд 40

Ненормализованная форма. Основание степени 2 Для приведения к нормализованному виду нужно

Ненормализованная форма. Основание степени 2
Для приведения к нормализованному виду нужно сдвинуть

мантиссу влево на 11 бит и вычесть 11 из экспоненты
Нормализованная форма. Основание степени 2
*В примерах указана 16-разрядная мантисса (включая знаковый бит) и 7-разрядная экспонента.
Слайд 41

Ненормализованная форма. Основание степени 16 Для приведения к нормализованному виду нужно

Ненормализованная форма. Основание степени 16
Для приведения к нормализованному виду нужно сдвинуть

мантиссу влево на 2 шестнадцатеричных разряда и вычесть 2 из экспоненты
Нормализованная форма. Основание степени 16
*В примерах указана 16-разрядная мантисса (включая знаковый бит) и 7-разрядная экспонента.
Слайд 42

Стандарт IEEE 754 1985 г. институт IEEE выпустил стандарт IEEE 754,

Стандарт IEEE 754

1985 г. институт IEEE выпустил стандарт IEEE 754, которому

в настоящее время соответствуют команды с плавающей точкой большинства процессоров (Intel, SRARC и JVM).
Разработчик стандарта Вильям Каган (William Kahan, университет Беркли)
IEEE 754 определяет 3 формата:
с одинарной точностью (32 бит);
с удвоенной точностью (64 бит);
с повышенной точностью (80 бит).

используется основание степени 2 для мантисс и смещенная экспонента

используется в арифметике с плавающей точки для уменьшения ошибки округления

Слайд 43

Форматы стандарта IEEE с плавающей запятой Одинарная точность Удвоенная точность 1.

Форматы стандарта IEEE с плавающей запятой

Одинарная точность
Удвоенная точность
1. Знаковый бит (0

– положительное число; 1 – отрицательное)
2. Смещенная экспонента: смещения 127 (одинарная точность) и 1023 (удвоенная точность)
[минимальная (0) и максимальная (255 и 2047) экспоненты не используются для нормализованных чисел]
3. Мантиссы по 23 и 52 бит

Биты 1 8 23

Биты 1 11 52

Экспонента

Знак

Знак

Слайд 44

Форматы стандарта IEEE с плавающей запятой Нормализованная мантисса начинается с двоичной

Форматы стандарта IEEE с плавающей запятой

Нормализованная мантисса начинается с двоичной точки

за которой следует 1 бит, а затем – остаток мантиссы.
В стандарте IEEE мантисса состоит из неявного бита, который всегда равен 1, неявной двоичной точки, за которыми идут 23 или 52 произвольных бита. В этом случае говорят о значащей части числа (significant).
Значащая часть числа (s) всех нормализованных чисел лежит в диапазоне 1 ≤ s < 2
Проблемы: переполнение, потеря значимости и неинициализированные числа.
Слайд 45

Числовые типы стандарта IEEE Если модуль результата меньше самого маленького нормал-ого

Числовые типы стандарта IEEE

Если модуль результата меньше самого маленького нормал-ого числа

с плавающей точкой => результат 0 или ошибка потери значимости.
В IEEE введены ненормализованные числа:
Имеют экспоненту 0 и мантиссу 23 и 52 бит.
Неявный бит 1 слева от двоичной точки превращается в 0
Ненормализованные числа можно легко отличить от нормализованных, т.к. у последних нет нулевой экспоненты
Слайд 46

Форматы стандарта IEEE с плавающей запятой Самое маленькое число 1,0×2^(-126) [1

Форматы стандарта IEEE с плавающей запятой

Самое маленькое число 1,0×2^(-126) [1 в

экспоненте и 0 в мантиссе]
Самое большое число примерно 0,9999999×2^(127) [0 в экспоненте и все 1 в мантиссе]
По мере уменьшения результат экспонента по прежнему остается равной 0, а первые несколько бит мантиссы превращаются в 0 (сокращается значение и число значимых бит мантиссы).
Самое маленькое ненулевое ненормализованное число содержит 1 в крайнем правом бите, все остальные биты 0.
Экспонента представляет 2^(-127), мантисса – 2^(-23), т.е. значение равно 2^(-150)