Лекция 2: представление данных в компьютере.

Как было сказано в предыдущей лекции, данные в компьютере представляют собой двоичный код. Поэтому возникает проблема представления произвольного набора данных в двоичном виде. Проще всего эта проблема решается для случая целых беззнаковых (то есть, все данные имеют только один знак, который поэтому можно опустить) чисел. Перевод такого числа из десятичной системы в двоичную можно осуществить с помощью целочисленного деления по следующему алгоритму:

1. Если текущее число меньше 2, то записать его в младший разряд результата, выполнение прекратить. Иначе, разделить текущее число с остатком на 2.
2. Остаток записать в младший разряд результата.
3. Применить пункт 1 к частному.

Это можно наглядно продемонстрировать с помощью деления «уголком».

Теперь достаточно записать справа налево выделенные цифры, и получится ответ: 1000110111. Чтобы представить это число в системе с фиксированным числом разрядов (например, 16), нужно неиспользованные старшие разряды заполнить нулями: 0000001000110111.

Обратный перевод осуществляется гораздо более тривиальным способом: необходимо просуммировать все цифры двоичного числа, умноженные на число 2^{номер разряда}, нумерация разрядов начинается с младшего (правого), которому соответствует номер 0. то есть: 1∙2⁹+0∙2⁸+0∙2⁷+0∙2⁶+1∙2⁵+1∙2⁴+0∙2³+1∙2²+1∙2¹+1∙2⁰=512+0+0+0+32+16+0+4+2+1=567.

Все эти вычисления занимают время и требуют большой внимательности при выполнении, поэтому использовать десятичную систему в программировании не очень удобно. Неудобно использовать также и двоичную систему из-за большого числа разрядов. Для того, чтобы представлять в удобочитаемой форме двоичные данные используется шестнадцатеричная система счисления. В ней используются цифры от 0 до 9 и латинские буквы от A до F.

0₁₀=0₁₆

1₁₀=1₁₆

2₁₀=2₁₆

3₁₀=3₁₆

4₁₀=4₁₆

5₁₀=5₁₆

6₁₀=6₁₆

7₁₀=7₁₆

8₁₀=8₁₆

9₁₀=9₁₆

10₁₀=A₁₆

11₁₀=B₁₆

12₁₀=C₁₆

13₁₀=D₁₆

14₁₀=E₁₆

15₁₀=F₁₆

16₁₀=10₁₆

Эта система счисления обладает очень важным свойством: любые четыре цифры двоичного числа (называемые тетрадой) всегда соответствуют одному шестнадцатеричному знаку:

0000₂=0₁₆

0001₂=1₁₆

0010₂=2₁₆

0011₂=3₁₆

0100₂=4₁₆

0101₂=5₁₆

0110₂=6₁₆

0111₂=7₁₆

1000₂=8₁₆

1001₂=9₁₆

1010₂=A₁₆

1011₂=B₁₆

1100₂=C₁₆

1101₂=D₁₆

1110₂=E₁₆

1111₂=F₁₆

Поэтому совершенно тривиально осуществляется перевод из двоичной системы в шестнадцатеричную и обратно: достаточно запомнить эту таблицу, и просто заменять тетрады соответствующими знаками или наоборот. Таким образом, максимальное значение одного байта записывается как FF₁₆, а максимальное значение, с которым может работать 32-разрядный процессор без применения математического сопроцессора – FFFFFFFF₁₆.

Также следует упомянуть ещё одну систему счисления – двоично-десятичную. Это искусственная система, в которой каждая цифра десятичного числа кодируется двоичной тетрадой. Например, десятичное число 851 в двоично-десятичной системе выглядит так: 1000 0101 0001. Ясно, что такая система, во-первых, не использует всю полноту возможности записи числа при фиксированном количестве разрядов, а во-вторых, приводит к крайнему усложнению математических операций: приходится с каждой тетрадой работать как с отдельным числом, отслеживая при этом межтетрадные переносы. Единственным её практически полезным свойством является отсутствие потери точности во время перевода из двоично-десятичной системы в десятичную и обратно при фиксированном количестве разрядов. Отсюда следует её основное применение – в бытовых калькуляторах, где стоит задача выводить результат точно такой, какой получил бы человек, считая на бумаге.

Итак, представление целых беззнаковых чисел в двоичном коде проблемы не составляет. Возникает вопрос, что делать с целыми знаковыми числами. Первое и очевидное решение – это использовать старший бит двоичного числа для хранения знака: 0, если знак «+» и 1, если знак «-». Подобное решение называют прямым кодом. Например, для случая 8-разрядной системы, 65₁₀=01000001₂, а -65₁₀=11000001₂. Однако данная система создаёт серьёзную проблему: a-b≠a+(-b). Действительно: 00110010-00110010=0, а 00110010+10110010=11100100, что абсурдно. Значит, нужно на уровне процессора отдельно определять операции сложения и вычитания, всегда следить за тем, чтобы вычисления производились с числами одного знака. Знак же результата определять путём сравнения исходных чисел. Ясно, что это совершенно недопустимо усложняет, а потому замедляет, вычисления.

Поэтому существует не вполне очевидное на первый взгляд, но очень эффективное решение – дополнительный код. Чтобы изменить знак числа в дополнительном коде, нужно выполнить такую операцию -a=ā+1, где черта над буквой – знак инверсии, замены всех нулей единицами, а единиц нулями. 65₁₀=01000001₂, а -65₁₀=10111110₂. Попробуем сложить эти два числа – получим 100000000₂, то есть, 256. Вспомним, однако, что мы работаем с 8-разрядной системой, а число 100000000₂ в ней записать невозможно. Поэтому старший бит 1 выйдет за границы числа, и в итоге останется 00000000₂, что является верным. Интересно заметить, что старший бит числа по-прежнему отвечает за знак, а потому можно использовать его значение можно использовать для того, чтобы узнать знак числа. Но уже нельзя использовать простую инверсию старшего бита для смены знака. Тем не менее, такое небольшое усложнение операции смены знака ведёт к огромному упрощению остальных операций – их можно производить, не задумываясь о знаке, результат всегда будет верным.

Следующим этапом усложнения типов представляемых данных является представление десятичных дробей. Исторически первым явилось решение представлять их в формате с фиксированной запятой (точкой) [1]. При этом определённое количество бит числа отдаётся под целую часть, а остальные разряды – под дробную. Несложно заметить, что такое представление данных является во многом искусственным, поскольку достаточно домножить все вводимые данные на 2^{число бит дробной части}, чтобы полностью избавиться от необходимости применения записи с фиксированной запятой. К тому же, такая запись сильно ограничивает диапазон возможных значений чисел.

На практике применяется метод записи чисел в формате с плавающей запятой (точкой). Этот формат представляет собой компьютерную реализацию экспоненциальной записи чисел. Представление чисел с плавающей точкой определяется стандартом IEEE 754-1985. В соответствии с этим стандартом, разряды, выделенные для представления числа, делятся на три поля: S, E и M. Поле S представляет собой один бит, отвечающий за знак числа (0, если «+» и 1, если «-»). Поле E — это набор бит, количество которых зависит от конкретного типа данных, выделенный под экспоненту [2]. Проблема хранения отрицательных значений экспоненты решается следующим образом: к реальному значению экспоненты добавляется число 2^{(число бит экспоненты)-1}. Например, в случае восьмиразрядной экспоненты, 00000001₂=-127₁₀, а 10000001₂=2₁₀. Поле M представляет собой набор бит, выделенный под мантиссу. Мантисса в компьютере имеет важную особенность: всегда верно неравенство 1≤M<2. За счёт этого её целая часть всегда равна 1, а потому при вычислениях отбрасывается. Таким образом, мантисса представляет собой целое беззнаковое. Стандартом IEEE 754-1985 предусмотрено три типа чисел с плавающей точкой:

l В 32-битном типе, называемом так же вещественным одинарной точности, под мантиссу выделены биты с 0 по 22, под экспоненту — с 23 по 30, 31 — под знак. Этот тип позволяет хранить числа от -3,4∙10³⁸ до 3,4∙10³⁸.

l В 64-битном типе, называемом так же вещественным двойной точности, под мантиссу выделены биты с 0 по 51, под экспоненту — с 52 по 62, 63 — под знак. Этот тип позволяет хранить числа от -1,79∙10³⁰⁸ до 1,79∙10³⁰⁸.

l Во 80-битном типе, называемом так же вещественным расширенной точности, под мантиссу выделены биты с 0 по 63, под экспоненту — с 64 по 78, 79 — под знак. Этот тип позволяет хранить числа от -1,18∙10⁴³⁹² до 1,18∙10⁴³⁹².

Вычисления с плавающей точкой осуществляет математический сопроцессор. Возникает вопрос — какова точность этих вычислений? Запишем для каждого типа минимальное по модулю представимое в нём число. Для 32-битного это будет 1,8∙10^-38, для 64-битного — 2,23∙10^-308, для 80-битного — 3,37∙10^-4392. Соответственно, любое число, которое по модулю меньше этих чисел, компьютер не сможет отличить от нуля. Так возникает понятие машинного нуля. Ясно, что погрешность вычислений не может быть меньше машинного нуля. Но на самом деле она ещё больше. Существует понятие машинный эпсилон – это минимальное число, для которого неравенство 1+ε≠1, с точки зрения компьютера, верно. Доказано, что числа a и b неразличимы для компьютера, если .

Помимо собственно вещественных чисел, тип с плавающей точкой позволяет кодировать два специальных обозначения: если экспонента равна своему максимальному значению, а мантисса равна нулю, то такой код считается бесконечностью со знаком. Если экспонента равна своему максимальному значению, а мантисса — не ноль, то такой код считается «не числом» (обозначается NaN). Это специальное значение, которое возвращают функции, когда их вызывают с аргументами, для которых они не определены. Например, NaN получится при попытке делить на ноль или извлечь квадратный корень из отрицательного числа.

В принципе, перечисленных методов хватает, чтобы закодировать что угодно, поскольку любую информацию можно привести к числовой. Однако стоит рассмотреть один очень важный частный случай – текстовую информацию. Изначально требовалось кодировать только буквы латинского алфавита, цифры, а также небольшой набор спецсимволов. Для этого вполне хватает 128 различных значений, поэтому была создана 7-битная кодировка ASCII. Поскольку минимальной адресуемой единицей является байт (8 бит), старшие биты ASCII-кодов просто оставались нулевыми. Важной особенностью ASCII является то, что цифры от 0 до 9, буквы от a до z и от A до Z расположены по порядку, причём буквы верхнего и нижнего регистров отличаются только значением пятого бита. Однако с развитием компьютерной техники возникла необходимость кодировать больше символов, в том числе, другие алфавиты. Решение в данном случае очевидно – заполнять коды с единичным старшим битом. Но неоднозначен вопрос, каким образом это делать. Поэтому возникло огромное количество кодовых страниц – вариантов заполнения верхней части таблицы символов. Среди кириллических кодовых страниц особо следует выделить две: CP-1251 (Windows-1251) и KOI8-R. CP-1251 была создана в начале 90х годов при русификации операционных систем Windows. По причине большого распространения последних, эта кодовая страница является наиболее часто употребляемой. KOI8-R – это кодировка, возникшая в то время, когда была ещё очень распространена 7-битная ASCII, и не было гарантии, что большинство компьютеров будут отображать 8-битную кодировку корректно. Поэтому, KOI8-R построена таким образом, что при потере старшего бита русские буквы превращаются в их английские фонетические аналоги, что оставляло возможность прочитать текст. KOI8-R является стандартом де-факто 8-битной кодировки в Unix-подобных операционных системах.

Естественно, что применение большого количества кодовых страниц приводило к сложностям в работе с текстами. Поэтому возникла идея создать кодировку, в которой бы отображались любые символы, которые только могут потребоваться при работе с текстом. Такой кодировкой стал изобретённый в 1991 году Юникод. В Юникоде зарезервировано 1114112 позиций для символов, на данный момент используется всего около 90000. Сам по себе Юникод кодировкой не является, это набор символов, на основе которого составляются кодировки. Одной из таких кодировок является UTF-8. Она не имеет постоянной разрядности, число байт, которое будет распознаваться как один символ, зависит от того, какой вид имеет считываемая последовательность:

1 байт – 0xxxxxxx

2 байта – 110xxxxx 10xxxxxx

3 байта – 1110xxxx 10xxxxxx 10xxxxxx

4 байта – 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

Где x – какой-то бит. Несложно заметить, что представление однобайтовых символов UTF-8 совпадает с представлением символов ASCII, а потому любой текст в ASCII корректно отображается в UTF-8, а текст в UTF-8, состоящий только из символов ASCII, корректно отображается в ASCII

Дата добавления: 2015-11-13