Представление данных в компьютерных системах

Тема 2 : Представление данных в компьютерных системах 1 1. Уровни представления данных в компьютерных системах 2 3 Уровни представления данных • Уровень конечного пользователя; • Уровень IT специалиста; • Уровень вычислительной машины. 4 Различные типы данных отличаются: 1. Операциями, которые можно выполнять над этими данными; 2. Возможными значениями или диапазонами значений; 3. Структурой хранения – выделение памяти, представление данных в ней и метод доступа. 5 2.Типы и структуры данных 6 Простейшие типы данных • Числовые данные • Символьные данные • Логические данные • Указатели 7 Простейшие типы данных • Числовые данные: Операции: +, - ,*,/, сравнение =, < , > , ≤ , ≥ • Символьные данные Операции: || (конкатенация) ’a’||’b’ = ’ab’; в лексикографическом порядке Сравнение по коду внутреннего представления • Логические данные Операции: ˅ ,˄ ,ˉ , ….. • Указатели Операции: + , -, сравнение 8 3. Числовые данные • Одним из основных понятий математики является число, используемое для количественной характеристики объектов, их нумерации, сравнения объектов и их частей. Изучение видов и свойств чисел проводится в отдельном разделе математики - "Теории чисел". 9 Натуральные числа (представление конечного пользователя) • Это целые числа больше нуля. Международный стандарт ISO 80000-2:2009 устанавливает два вида натуральных чисел, обозначаемых обычно N: • N - натуральные числа, включая ноль {0,1,2,3,...}, так называемый "расширенный натуральный ряд", • N* - натуральное число без нуля {1,2,3,...}. 10 Свойства натуральных чисел • Натуральные числа замкнуты относительно операций сложения и умножения, в которых результат тоже натуральное число. • Сложение и умножение натуральных чисел коммутативны и ассоциативны. • Операции вычитания и деления не замкнуты, так как определены не для всех пар натуральных чисел. • Операция умножения дистрибутивна относительно сложения и вычитания. 11 Особенности натуральных чисел в компьютерных системах В программных системах натуральному числу соответствует понятие целого числа без знака, причем, в отличии от математического понятия ноль считается положительным числом. В языке С++ натуральное число может быть задано объявлением переменных: unsigned char var_a; unsigned int var_b; 12 Целые числа множество всех отрицательных и положительных целых чисел на числовой оси и могут быть получены как разность двух натуральных чисел. Целые числа замкнуты относительно сложения, вычитания и умножения, но не деления. При их записи принято указывать знак целого числа символами "-" и "+", знак "+" часто опускают. Для натуральных и целых чисел вводят отдельную операцию деления - деление с остатком. В программировании этим числам соответствует понятие "целое со знаком". Например, такие данные могут быть описаны в языке С++: signed char var_a; signed int var_b; 13 Рациональные числа числа, представимые в виде отношения целого и натурального чисел, они замкнуты относительно всех четырех арифметических операций - сложения, вычитания, умножения и деления, кроме деления на ноль. В явном виде рациональные числа в системах программирования обычно не представлены. 14 Действительные (вещественные) числа расширение множества рациональных чисел числами, которые не могут быть получены как отношение целых чисел. 15 • Рациональные и действительные числа имеют целую и дробную части, которые при записи принято разделять знаками "точка" или "запятая". • Особо следует выделить правильные дроби, в которых целая часть равна нулю. Они имеют важное значение в вычислительной технике при записи чисел с фиксированной точкой (запятой). Для удобства при записи правильной дроби перед точкой, разделяющей целую и дробную части записывают не значащий "ноль", однако следует иметь в виду, что этот "ноль" используется для удобства восприятия числа и не является символом, хранимым в памяти вычислительной машины. • В современном программировании действительные числа чаще представляются в форме с плавающей точкой, например, форматы float, double, long double в языке С++ и других. 16 4. Системы счисления Система счисления - способ записи чисел с помощью ограниченного набора символов и совокупность правил (алгоритмов) сопоставления этим записям реальных значений чисел. 17 • Символы, используемые для записи числа, часто называют цифрами данной системы счисления. Однако, для записи числа могут использоваться не только символы цифр, например, символ знака числа, точки или запятой, указывающих разделение числа на целую и дробную части. • Системы счисления могут быть позиционными и непозиционными, иногда используют смешанные системы счисления. 18 Непозиционная система счисления значение символа не зависит от его места расположения в числе. Для образования числа в непозиционной системе счисления используются операции арифметического сложения и вычитания. Примером непозиционной системы счисления является римская: XVI=X+V+I=10+5+1=1610 IX=X-I=10-1=910 19 20 Позиционная система счисления В позиционной системе счисления значение каждого символа алфавита зависит от его места расположения в числе. Справедливо следующее представление действительного положительного числа в позиционной системе счисления: x(q) = a n-1 q n-1 + a n-2 q n-2+ ... +a1q1 + a0q0 + a-1q-1 + ...+a-mq-m+..... , (1) где: x(q) - число в заданной системе счисления; q - основание системы счисления, в позиционной системе счисления равен размеру алфавита, используемого для записи числа; q i - вес i - того разряда числа; a i - разрядный множитель - один из символов алфавита, используемого для записи числа, которому приписано соответствующее числовое значение; n - количество целых разрядов числа; m - количество дробных разрядов числа - точность представления числа. 21 Особенности позиционной системы счисления: • • • • Основание системы счисления всегда натуральное число, большее 1 и равно 10 в этой системе счисления (например, q = 210 = 102, q = 810 = 108, q = 1610 = 102 и т.д.); Для выполнения основных арифметических операций - сложения, вычитания, умножения, деления и деления с остатком достаточно задать только таблицы сложения и умножения; В алфавите, используемом для записи положительного числа, отсутствуют символы, отличные от символов цифр. Например, в него не входят символы "+","-",".", ",". Позиционной системе счисления соответствует запись числа в форме (1), называемой развернутой записью. В этой записи нет необходимости указывать разделитель целой и дробной частей, все определяется весом разрядов. На практике мы пользуемся сокращенной записью числа в виде последовательности разрядных множителей. Это естественно при использовании десятичной системы счисления, когда вес каждого разряда мы знаем, начиная с уроков арифметики в школе - единицы, десятки, сотни и т.д. При использовании другой системы счисления такая запись может вызвать затруднения. 22 схема Горнера Для целого числа x(q) = (...((a n-1 q + a n-2 )q+ a n-3) q + ... + a1) q+ a0 23 Часто используемые системы счисления Двоичная система счисления: q=2, А={0,1}. Восьмеричная система счисления: q=8, А={0,1,2,3,4,5,6,7}. Для записи числа в шестнадцатеричной системе счисления используются десять символов цифр и символы латинского алфавита A,B,C,D,E,F, которыми обозначают символы (10),(11),(12),(13),(14),(15), соответственно: q=16, А={0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. При работе с шестнадцатеричными числами в выражении (1) следует использовать десятичные номера символов A,B,C,D,E,F – (10), (11), (12), (13), (14),(15), соответственно. 24 • Принятая запись шестнадцатеричного числа приводит к тому, что число может начинаться с символа латинского алфавита, а это автоматически воспринимается компилятором не как число, а как имя объекта данных. Поэтому разные системы программирования накладывают дополнительные требования к форме записи шестнадцатеричных чисел. • В языке ASSEMBLER в конце записи числа указывается символ "h" (hexadecimal), а впереди записывается незначащий "0". Другие реализации языка требуют префикса "$" перед числом. • В языке С++ принята форма "0x<шестнадцатеричное число>, например, 0xA9В3. Допускаются как прописные, так и строчные символы. 25 4. Перевод чисел из одной системы счисления в другую Пусть необходимо перевести число из системы счисления qк . В зависимости от того, какие значения имеют qи в систему счисления qи и q к , в инженерной практике используются различные правила: 1. перевод числа из десятичной системы в систему с любым основанием и =10, к ≠ 10: • перевод целого qчисла, и • перевод правильной дроби, • перевод числа, имеющего целую и дробную часть; 2. перевод числа из системы с любым основанием ( и ≠ 10) в десятичную ( к =10); 3. перевод числа произвольной недесятичной из системы с основанием и ≠ 10 в систему с основанием к ≠ 10; 4. перевод числа из двоичной системы счисления = 2, в систему p и счисления к = , где р = {2,3,4,.....} ; 5. перевод числа из системы счисления и = p , где р = {2,3,4,.....} , в двоичную систему счисления . к q q q q q q q 2 q 2 q 2 q • Правило 1.1: Для перевода целого числа из десятичной системы счисления (qи =10) в недесятичную систему с основанием qк ≠ 10, число нужно последовательно делить на основание qк до тех пор, пока не будет получена целая часть частного, равная 0, то есть будет получен остаток от деления, меньший qк . Число в системе счисления с основанием qк записывается в виде упорядоченной последовательности остатков от деления в порядке, обратном получению остатков, то есть старшей цифрой числа будет последний остаток. Пример: перевод целого десятичного числа • Правило 1.2: Для перевода правильной дроби из десятичной системы счисления(qи =10) в систему с основанием qк ≠ 10 число нужно последовательно умножать на основание qк (причем умножению подвергаются только дробные части) до тех пор, пока не будет обеспечена заданная точность представления числа. Дробь в системе счисления с основанием qк записывается в виде упорядоченной последовательности целых частей произведений в порядке их получения. • Если требуемая точность перевода в qк составляет m разрядов после запятой, отделяющей дробную часть, то число указанных последовательных произведений (то есть цифр в представлении дроби) равно m+1. Затем результат округляется до m разрядов. • Если на некотором шаге получения произведений дробная часть числа становится равной 0, то процесс преобразования на этом заканчивается, так как все остальные цифры в представление дроби будут равны 0, а результат дополняется до m разрядов незначащими нулями. • Правило 1.3: При переводе неправильной дроби из десятичной системы счисления в систему с основанием qк ≠ 10 отдельно переводится целая и дробная части числа. • Пример: перевести число 123.5810 в восьмеричную систему счисления. • 123.5810 =12310 + 0.5810 = 1738 + 0.458 = 173.458 Правило 2: Для перевода числа из недесятичной системы счисления с основанием qи ≠ 10 в десятичную, qк = 10, пользуются формулой разложения в ряд (1). Выражение (1) справедливо как для целых, так и для дробных чисел. Пример: представить числа: а)111011.011, б)154.31, в)А2В.3С в десятичной системе счисления. а). 111011.0112 = 1*25 +1*24 +1*23 +0*22 +1*21 +1*20 +0*2-1 +1*2-2 +1*2-3 = =32 +16+8+2+1+1/4+1/8=59.37510; б). 154.318 = 1*82 +5*81 +4*80 +3*8-1 +1*8-2 = 64+ 40+ 4+ 3/8+ 1/64 = 108.39062510; в). А2В.3С16 = А*162 +2*161 +В*160 +3*16-1 +С*16-2 = 3840+32+11+3/16+12/256 = 3883.23437510. Правило 3: При переводе чисел из системы счисления с основанием qи ≠ 10 в систему с основанием qк ≠ 10 выполняется промежуточное преобразование в десятичную систему. Правило 4: Для перевода двоичного числа qи =2 в число с основанием системы счисления, равным целой степени 2, qк =2р, где р ={2, 3, 4, ...} необходимо разбить исходное двоичное число на группы из р разрядов. Разбиение выполняется для целой части числа справа на лево от запятой, а для дробной - слева на право от запятой. При необходимости группы дополняются не значащими нулями. Число в новой системе счисления записывается как последовательность символов, соответствующих каждой группе. Пример: 110001110010101111010110110.01011101012 0110 0011 1001 0101 1110 1011 0110 .0101 1101 0100 6 3 9 5 E B 6 5 D 4 Правило 5: Перевод из числа qи =2р, где р ={2, 3, 4, ...} в двоичное число qк =2 выполняется последовательной записью двоичных чисел, соответствующих каждому символу исходного числа. Пример: A2E.С1D16 = 101000101110.1100000111012 5. Формы представления чисел в разрядной сетке вычислительной машины 38 5.1. Разрядная сетка. Представление целых чисел без знака 39 unsigned char var_a; 40 5.2. Представление целых чисел со знаком 41 При использовании не двоичной системы счисления в общем случае в знаковом разряде можно записать более чем 2 значения, обозначающие «+» и «-». Тогда необходимы дополнительные соглашения о кодировании знака числа. Так, например, в ряде случаев используется упакованный десятичный формат числа – BCD (Binary-Coded Decimal). В этом формате для хранения десятичного числа выделяется целое число байт, каждый байт разбивается на два четырехразрядных поля - тетрады, в которых хранится двоичное представление соответствующего десятичного разряда. В этом формате знак числа определяет старший бит старшей тетрады в записи числа. 42 5.3.Числа с фиксированной точкой Для представления действительных чисел, имеющих дробную часть, в разрядной сетке необходимо указать разделитель целой и дробной части – символ «точка» или «запятая». Эти символы не входят в алфавит, используемый для записи числа, и поэтому не могут быть использованы. 1) Целое число можно рассматривать как действительное, у которого отсутствует дробная часть. Тогда точка, разделяющая целую и дробную части, подразумевается справа от самого младшего разряда числа. Дробная часть находится за пределами разрядной сетки. 2) Целая часть числа равна нулю и, следовательно, число является правильной дробью. Тогда точка, разделяющая целую и дробную части, подразумевается между знаковым разрядом и значащей частью числа. Такое представление называется «число с фиксированной точкой». 43 Вариант 2 – точка подразумевается перед знаковым разрядом Вариант 1 – точка подразумевается после младшего разряда 44 Число с фиксированной точкой представляется следующим образом: Хф.т.= Х*Км , где : Хф.т.- машинное представление числа с фиксированной точкой; Х - исходное число, Км - масштабный коэффициент, который выбирается из условий конкретной разрядной сетки и не должен допускать выхода исходных чисел и результатов вычислений за пределы допустимого диапазона. 45 Таким образом, число с фиксированной точкой всегда правильная дробь. 46 5.4.Числа с плавающей точкой. Число с плавающей точкой представляется в виде Х = M*Е P , где: Е = q P M - основание системы счисления, порядок числа, мантисса числа. 47 Пример: запись десятичного числа в формате с плавающей точкой: Х10 = 525*100 = 5.25*102= 0.525*103 48 международный стандарт IEEE 754 (754-2008 - IEEE Standard for Floating-Point Arithmetic) Три основных формата представления двоичных чисел: • число одинарной точности (float в языке С/С++); • число двойной точности (double в языке С++); • расширенный формат - число четырехкратной точности (long double в языке С++) не является обязательным и используется не во всех системах программирования. 49 Общее представление двоичного числа в разрядной сетке по стандарту IEEE 754 50 Мантисса Мантисса числа должна быть нормализованной, т.е. отвечать условию 1 ≤ Мн < Е, для двоичного числа 1 ≤ Мн < 210 .(или 102 ) 51 Особенности • Нормализованная мантисса двоичного числа всегда имеет целую часть, равную 1, поэтому целая часть мантиссы не записывается в разрядной сетке, а учитывается при вычислениях (кроме расширенного формата); • В поле мантиссы разрядной сетки хранится модуль дробной части числа; • Особым случаем является нулевое значение числа. "Ноль" в таком представлении может иметь как знак "+", так и "-". Нулевую мантиссу нельзя нормализовать, поэтому вводится понятие "машинный ноль", за которое принимают число с нулевым значением мантиссы и порядка. 52 Алгоритм нормализации мантиссы Для двоичного числа точку, разделяющую целую и дробную части необходимо сдвигать влево или право до тех пор, пока не будет получена целая часть числа, равная 1. На каждом шаге сдвига порядок числа увеличивается (при сдвиге точки влево) или уменьшается (при сдвиге точки вправо) на единицу. Например, если при нормализации точка была перенесена на 4 разряда влево, порядок числа должен быть увеличен на 4. Примеры нормализации мантиссы двоичного числа: а) 111011.101 = 1.11011101*Е0101; б) 1.110111 = 1.110111*Е00; в) 0.0011011 = 1.1011000*Е1011. Красным выделен знак порядка 53 Порядок Стандарт IEEE 754 требует, чтобы в поле порядка всегда указывалось только целое число без знака. Поэтому в поле порядка хранится смещенный на (2nр-1 - 1). порядок Pсм, называемый характеристикой Pсм = Р + (2nр-1 - 1). Характеристика всегда целое число без знака. 54 Машинное представление двоичного числа в разрядной сетке по стандарту IEEE 754, целая часть мантиссы равна 1 и подразумевается 55 Для приведенных выше примеров машинное представление при np = 4 и nm = 8 : а) 111011.101 = .11011101*Е1100; б) 1.110111 = .11011100*Е0111; в) 0.0011011 = .10110000*Е0100. Здесь целая часть мантиссы равна 1 и подразумевается, показатель степени – смещенный порядок (характеристика) 56 Обобщенный алгоритм преобразования вещественного десятичного числа в двоичное число с плавающей точкой формата IEEE. 1. Представить целую часть вещественного числа в двоичном виде и поставить после нее десятичную точку. 2. Преобразовать дробную часть вещественного числа в двоичную систему счисления с точностью nm после точки. 3. Записать полученное значение в двоичной форме. 4. Нормализовать полученное двоичное число, определив значение показателя степени в порядке Р. 5. Найти характеристику Pсм= Р+(2nр-1 - 1). 6. Записать значение характеристики в соответствующие биты формата. 7. Записать дробную часть нормализованной мантиссы в поле мантиссы, отбросив разряды, выходящие за пределы этого поля. Примечание. Правила округления мантиссы могут отличаться в различных системах программирования. 8. Если число положительное, то в самый старший разряд представления следует записать 0, если отрицательное – то 1. 57 При записи вещественного числа в ограниченном формате разрядной сетки неизбежны погрешности. • • • • • • • • • • • • • • • Так, например, перевод десятичного числа 0.210 в представлении float ( С++ ) дает значение 0.20000000310. Несмотря на то, что величина ошибки не значительна, это может привести к серьезным ошибкам при сравнении чисел. Например, приведенные ниже фрагменты программ для систем MATLAB и C++ , дадут разные результаты. В программе на зыке C++ переменная var_b получит значение 0, а в MATLAB - 1. ++ C : float var_a, char var_b =0; var_a = 0.2; if ((var_a - 0.2) == 0) var_b = 1; MATLAB: var_a=0.2; var_b=0; if (var_a - 0.2)==0 var_b=1; end Ошибка в программе на C++ заключается в том, что в сравнении участвуют значения разных форматов var_a - float, константа 0.2 по умолчанию имеет формат double. При вычислении будет выполнено автоматическое приведение типов данных float var_a = - 0.200000003 будет приведено к типу double добавлением незначащих нулей. Соответственно, (0.20000000300000000 - 0.20000000000000001) ≠ 0. 58 6. Числа в прямом и дополнительном кодах 59 Для разрядной сетки размером n 60 Прямой код Достоинства прямого кода: • Простое получение кода отрицательных чисел; • Код значащей части числа является его модулем совпадает с соответствующим числом без знака, что удобно для сравнения чисел; • При заданной разрядной сетке количество положительных чисел равно количеству отрицательных. Недостатки прямого кода: • выполнение арифметических операций требует усложнения алгоритмов либо архитектуры процессора; • число "0" имеет два значения - "+0" и "-0". 61 Особенности дополнительного кода • Представление положительных чисел в прямом и дополнительном кодах совпадают; • Знаковый разряд может рассматриваться как число и, соответственно, участвовать в вычислениях на ровне с другими разрядами; • Очень простой и быстрый алгоритм выполнения сложения чисел со знаком; • Чтобы изменить знак числа записанного в дополнительном коде достаточно взять дополнение; • Наличие только одного нуля; • Представление не симметрично - число отрицательных чисел на "1" больше, чем положительных. 62 Двоичные числа в прямом и дополнительном кодах 63 Чтобы найти дополнение для числа в двоичной системе счисления необходимо выполнить инверсию всех разрядов и прибавить "1" к младшему разряду. 64 примеры 65 7. Обработка переполнения разрядной сетки при сложении двоичных чисел 66 • Если С1 = С2, переполнения нет, в знаковом разряде разрядной сетки находится знак результата, а содержимое CF игнорируется, флаг OF = 0. • Если С1 ≠ С2, произошло переполнение, в знаковом разряде разрядной сетки находится старший разряд значащей части результата (разряд переполнения p), знак результата вытеснен за пределы разрядной сетки и находится в CF, OF = 1 указывает на то, что произошло переполнение. OF =. С1 ⨁ С2 67 Пример 7.1 68 Пример 7.2 69 Пример 7.3 70 Пример 7.4 71 8. Арифметические операции с числами с плавающей точкой • Сложение: Если порядки слагаемых одинаковы, то сложение выполняется по следующему алгоритму: 1. Мантиссы слагаемых складываются. 2. Порядок результата равен порядку слагаемых. 3. Мантисса нормализуется, при этом младшие разряды мантиссы, не вмещающиеся в ее разрядную сетку, отбрасываются. Если при нормализации мантиссы младшие разряды освобождаются, они заполняются незначащими нулями. 72 Если порядки слагаемых различны, перед выполнением перечисленных действий сначала выполняется выравнивание порядков – меньший порядок приводится к большему. Для этого мантисса сдвигается вправо с учетом целой части и на каждом шаге сдвига порядок увеличивается на «1» до тех пор, пока порядки слагаемых не станут равными. 73 Пример: С = А + В; А = + 1.111111100 Е100111 (указан смещенный порядок) В = + 1.000111011 Е100001 74 75 • Умножение и деление чисел с плавающей точкой не требует выравнивания порядков. При выполнении этих операций мантиссы перемножаются (делятся), а порядки складываются или вычитаются. Однако, обязательным этапом операций умножения или деления является нормализация мантиссы полученного результата. 76 9. Особенности выполнения умножения в вычислительной машине. C = X1 *X2, Где: X1 - множимое; X2 - множитель. X1 и X2 - целые числа без знака, разрядность n. Сумма частичных произведений (СЧП) –разрядность 2n СЧПH и СЧПL 77 Обозначения • Сдвиг числа вправо на один разряд «→»; • X20 младший разряд множителя; • Сдвигу числа вправо соответствует операция деления числа на основание системы счисления. 78 Алгоритм умножения 1) Сумма частичных произведений приравнивается к нулю СЧП = 0. 2) Умножение множимого на младший разряд множителя с использованием таблицы умножения двоичных чисел (умножение на "0" дает "0", на "1" - множимое) и сложение результата с СЧПH СЧПH = СЧПH + X1* X20. 3) Сдвиг СЧП вправо на один разряд СЧПH = СЧПH →. 4) Сдвиг X2 вправо на один разряд X2 = X2 →. В результате повторения шагов 2 - 4 алгоритма n раз сумма частичных произведений будет равна C = X1 *X2. 79 80 10. Диапазон представления чисел в различных форматах 1. Целое число без знака 81 Целое число со знаком 1. Прямой код 2. Дополнительный код 82 Правильная дробь 83 Число с плавающей точкой 84