Внутренняя форма представления данных в компьютере и недесятичные системы счисления. Часть 4. - Начинающим - Shelek
9. Внутреннее представление целых чисел.

Теперь после рассмотрения недесятичных ситем пора разобраться в том, как же все-таки хранятся данные в компьютере. Да вроде бы ведь уже разобрались, не так ли? Ну, скажем, есть у нас байт. В него можно поместить одно из 256 чисел, и, как мы уже считали (см. задание 2), это числа от 0 до 255, представленные в двоичной системе. Да, конечно, все это верно, но числа-то все только положительные! А в реальных вычислениях, начиная со средней школы мы постоянно пользуемся как положительными, так и отрицательными числами.

Как же быть? Ничего кроме битов в байте нет, никаких специальных приспособлений для указания знака не предусмотрено. Где же выход?

А выход очень прост: давайте пожертвуем одним битом и будем считать его ответственным за знак. Скажем, 0 соответствует положительному числу, 1 - отрицательному. Можно, конечно, и наоборот, разницы никакой, но так уж принято, что обычно 1 обозначает знак минус.

Теперь вопрос: а какой из восьми бит использовать? На самом деле все равно, но проще всего использовать старший бит.

Теперь надо понять, какому отрицательному числу какой двоичный код соответствует. Опять же, решений может быть множество, но самый логичный подход выглядит так: используем такие представления для отрицательных чисел, чтобы (-1) = 0 - 1, (-2) = (-1) -1 и т.д.

Представим себе опять, что байт - это всего лишь счетчик с восемью окошечками. Для значения "0" представление нам известно - это 0 0 0 0 0 0 0 0. Какие цифры получатся в окошках такого счетчика, если вычесть 1?

Вспоминаем правила вычитания в двоичной системе. Как вы помните, при вычитании 1 из 0 в занимается единица из следующего разряда. В нашем случае это произойдет во всех разрядах, пока мы не дойдем до самого старшего. Дальше занимать неоткуда! Что же делать? А ничего! Вот то, что получилось и будет результатом. Так что же у нас получилось? Ну конечно, 1 1 1 1 1 1 1 1. А что получится, если к этому числу добавить 1? Правильно, в соответствии с двоичными правилами сложения во всех разрядах получатся нули, а из старшего разряда получится перенос за пределы счетчика. Этот перенос мы, естественно, тоже проигнорируем.

С подобным поведением вы, конечно, сталкивались в обыденной жизни. В любом счетчике после того, как все разряды заполняются максимальной цифрой (например, 9 9 9 9 9) при прибавлении 1 получаются все нули.

Итак, мы выяснили, что 1 1 1 1 1 1 1 1 соответствует -1.

Дальше все пойдет проще.
1 1 1 1 1 1 1 1 - 1 = 1 1 1 1 1 1 1 0, это будет -2
1 1 1 1 1 1 1 0 - 1 = 1 1 1 1 1 1 0 1, это будет -3
и так далее.

Задание 7. Посчитайте, каким отрицательным числам соответствуют все возможные значения байта с единицей в старшем разряде.

Задание 8. Пользуясь правилами, которые мы только что разобрали, определите весь диапазон чисел, которые может хранить байт, с учетом использования старшего бита для знака.

В ходе выполниния заданий у вас мог возникнуть вопрос: а что происходит, когда мы производим следующее действие:
1 0 0 0 0 0 0 0 - 1 = 0 1 1 1 1 1 1 1 ? Было (-128), а что стало?

Все очень просто: в результате последнего действия мы переехали из области отрицательных чисел в область положительных, поскольку в старшем разряде теперь 0. А для положительных чисел мы давно знаем, чему каждое из них соответствует. 0 1 1 1 1 1 1 1 соответствует 127.

Что же это такое?! Как же это после (-128) получается не (-129), а 127? А вы что ожидали, что сможете теперь в один байт вместить вообще любые существующие числа? Нет, так не бывает! Между прочим, общее количество различных значений, которые можно хранить в одном байте, как и следовало ожидать, не изменилось. Их по-прежнему 256. Только раньше мы не использовали знак и диапазон был от 0 до 255. Теперь, когда один бит считается знаковым, диапазон стал от -128 до 127.

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

Остался еще один важный вопрос: а как проще переводить отрицательные числа в дополнительный код и обратно? Оказывается, дополнительный код обладает очень интересным свойством: если поменять знак с "-" на "+", перевести полученное число в двоичную форму, заполнив этим числом байт, заменить все нули на единицы, а единицы на нули (это называется инвертированием) и к полученному результату добавить 1 по правилам двоичной системы, как раз и получится дополнительный код исходного числа.

Пример:
Исходное число: -37,
меняем знак: 37,
переводим в двоичную систему: 100101,
заполняем байт: 00100101,
меняем нули на единицы и наоборот: 11011010
добавляем единицу: 11011011.
Все. Результат получен. -37 = 11011011

Задание 9. Убедитесь, что приведенное число действительно соответствует -37. Можно использовать результаты выполнения задания 7.

10. Большие числа, числа со знаком и без знака.

А что делать, если диапазон от -128 до +127 нас не устраивает? То же самое, что мы делали для положительных чисел - использовать два, четыре, или больше байтов для представления числа. При этом все свойства таких представлений останутся такими же, как и для одного байта.

Теперь мы можем вернуться к вопросу, поставленному в начале этого урока:
Почему иногда в программах 120+10 дает 130, а иногда - (-126) ???

Переводим 120 в двоичную систему: 1111000.
Переведем 10, в двоичную систему: 1010.
Складываем: 1111000 + 1010 = 10000010.

Что получится, если 10000010 перевести в десятичную систему? Все зависит от того, как компьютер воспринимает это число. Если это байт без знака, или, допустим, младший байт из двухбайтовой комбинации (00000000 10000010), перевод будет осуществляться по обычным правилам для двоичной системы. Тогда получится 130 (проверьте!). Однако, если число 10000010 - это содержимое байта со знаком, переводить его надо по правилам, принятым для дополнительного кода. В этом случае число получится отрицательное, а точнее - (-126) (тоже проверьте!).

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

В связи с этим в некоторых языках программирования (например, в С и С++) выделяются даже специальные типы данных, в название которых входит слово unsigned (без знака).



11. Дробные числа.

Все, что мы с вами только что разобрали, относится к целым числам. Однако, в реальной жизни нам очень часто приходится вести вычисления с дробными данными. Давайте теперь разберем, как же такие данные представляются в компьютере.

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

Способов можно придумать много. Два наиболее распространенных способа очень похожи на те, которыми мы все когда-то пользовались в школе. То есть, конечно, не простые дроби, вроде 7/8 или 2 15/43, хотя и такие способы возможны (если кому-то будет интересно, расскажу, хотя это выходит за пределы данной статьи). Я имею ввиду способы представления десятичных дробей.

Итак, вспоминаем: 23.456, 0.0098 - это один способ. Кстати, кому больше нравится, можете вместо десятичной точки поставить запятую. Другой способ - 6.67 * 10^-11, 6.06 * 10^23 и т.д. Например, приведенные ранее числа можно представить вторым способом так: 0.23456 * 10^2, 9.8 * 10^-3.
А можно и так: 23456 * 10^-3, 0.0000098 * 10^3.

Как видите, способы очень отличаются друг от друга. Между прочим, вы обратили внимание на то, что первый способ дает однозначное представление чисел, в то время как второй позволяет, в зависимости от степени десяти, перемещать десятичную точку (или запятую)? Именно поэтому, первый способ в программировании получил название представление с фиксированной точкой (запятой), в то время, как второй - представление с плавающей точкой.

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

Давайте поступим так же, как мы поступали для целых чисел, а именно, начнем с того, что попытаемся понять, что же из себя представляет десятичная дробь.

3.14159 = 3 + 1*(1/10) + 4*(1/100) + 1*(1/1000) + 5*(1/10000) + 9*(1/100000),

или иначе

3.14159 = 3 * 10^0 + 1 * 10^-1 + 4 * 10^-2 + 1 * 10^-3 + 5 * 10^-4 + 9 * 10^-5.

А теперь возьмем число, записанное в виде "двоичной дроби":

1.01101 = 1 * 2^0 + 0 * 2^-1 + 1 * 2^-2 + 1 * 2^-3 + 0 * 2^-4 + 1 * 2^-5,

или, другими словами

1.01101 = 1 + 0/2 + 1/4 + 1/8 + 0/16 + 1/32 = 1.40625

Не будем вдаваться в подробности перевода двоичных дробных чисел в десятичные и обратно, скажем лишь, что свойства "двоичных дробей" очень похожи на свойства десятичных дробей с той лишь разницей, что цифр только две, и смещение на один разряд дает изменение значения в два раза, а не в десять.

12. Фиксированная точка (запятая).

Раз уж в нашем байте нет специального места для десятичной точки, просто договоримся, где мы будем мысленно ее помещать. Скажем, если считать, что байт делится так: биты 0 - 4 - целая часть, биты 5 - 7 - дробная часть, то диапазон представимых чисел получится такой:

00000.000
00000.001
00000.010
. . .
11111.110
11111.111

Если считать, что рассматриваются числа без знака, то есть только положительные, то это будет соответствовать таким десятичным числам:

0, 0.125, 0.25, ... , 31.75, 31.875

Задание 10. Убедитесь, что приведенный диапазон правилен и составьте диапазон чисел, представимых в рамках одного байта, при условии, что десятичная точка находится сразу после бита 0.

Представление чисел с фиксированной точкой можно расширить на несколько байтов, аналогично тому, как мы поступали с целыми числами. Можно считать, например, что из двух байтов один - это целая часть, а второй - дробная.

Точно так же, как мы делали для целых чисел, можно отвести один бит под знак, и таким способом получить представление отрицательных чисел с фиксированной точкой.

Представление чисел с фиксированной точкой, как видим, совсем несложно, однако оно не получило широкого распространения. Как вы думаете, почему?

Причина очень проста. Допустим, что числа из приведенного ранее примера мы захотели бы представить с фиксированной точкой. Что получилось бы?

6.67 * 10-11 превратилось бы в 0.0000000000667, а 6.06 * 1023 - в 606000000000000000000000 !

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

13. Плавающая точка.

Теперь нам осталось разобрать устройство чисел с плавающей точкой. Возьмем все тот же пример: 6.06 * 1023. Какие элементы определяют это число? Значение 6.06, называемое мантисса, значение 23, называемое порядок, и значение 10, определяющее, по сути дела, в какой системе мы работаем. Ну, с десяткой все понятно - она везде десятка, никуда не денется, а значит, никак не определяет конкретное число. Остаются мантисса и порядок.

Итак, как же нам представить мантиссу и порядок в рамках байтов? По сути дела, это просто два числа: одно с фиксированной точкой (мантисса) и одно - целое (порядок), причем оба - со знаком. Таким образом, все, что надо сделать, это отвести достаточно места для этих двух чисел. Конечно, одного байта не хватит, да и двух пожалуй будет маловато, а вот четырех байтов уже вполне достаточно. Скажем, один байт на порядок и три байта на мантиссу.

Давайте посмотрим, какие числа можно будет при этом представлять. Что определяется мантиссой? В первую очередь, точность значения. Как ее посчитать?

Очень просто. Допустим, у нас есть три байта под мантиссу. Это 24 бита, но один из них надо отвести на знак. Итого, 23 бита под значащие цифры. Сколько это будет в пересчете на десятичные цифры? По сути дела, нас интересует, "сколькозначному" десятичному числу соответствует 2^23. Ну, это совсем просто. Log(2) = 0.301. Если умножить 0.301 на 23, получим 6.92, то есть, точность примерно равна 7 десятичным знакам.

Много это, или мало? Все зависит от того, насколько интенсивные вычисления нам предстоит выполнять. Как известно, при неточных расчетах ошибки имеют тенденцию накапливаться, в конце концов полностью "съедая" настоящее значение, и для интенсивных вычислений 7 десятичных знаков точности может оказаться недостаточно. Поэтому, наряду с четырехбайтными используются восьмибайтные и даже более длинные числа с плавающей точкой.

Теперь, что нам дает порядок? В нормальной записи это степень 10, то есть основания системы, показывающая, насколько велико или мало число по абсолютной величине, то есть, грубо говоря, для маленьких чисел - сколько нулей надо поставить после десятичной точки до начала значения мантиссы, а для больших - сколько нулей должно быть после окончания мантиссы.

В компьютере, как мы знаем, все строится на базе двоичной системы. Поэтому и порядок показывает не степень 10, а степень 2. Так что увеличение порядка на единицу будет соответствовать удвоению числа, а уменьшение - делению на два. В остальном все останется так же, как и для десятичной системы.

Задание 11. Запишите в двоичной системе различные возможные значения порядка и мантиссы для числа 1.75. Попытайтесь сделать это самостоятельно, не пользуясь подсказкой.

Если вам не удалось справиться с заданием 11 самостоятельно, вот вам подсказка: 1.75 = 7 / 4.

Теперь можно посчитать, какой диапазон чисел обеспечивает один байт, отведенный для порядка. Диапазон порядка - это диапазон одного байта со знаком, а он, как мы помним состоит из 256 значений, от -128 до 127. Это и будет диапазон порядка, а, поскольку порядок показывает степень числа 2, то и диапазон представимых таким образом чисел по абсолютной величине будет от 2 ^ -128
до 2 ^ 127.

Много это, или мало? Ну, пользуясь приведенным ранее значением логарифма, легко получить диапазон - примерно от 10 ^ -38 до 10 ^ 38. В общем, для обычных вычислений вполне достаточно, а кому мало - опять же, могут использовать более длинные (например, восьмибайтовые) представления чисел с плавающей точкой.

В связи с представлением чисел с плавающей точкой (по-английски, floating point) во многих языках для работы с дробными числами используются специальные типы данных float. Более длинные представления для чисел с плавающей точкой (например, восьмибайтное), одно время назывались числами с плавающей точкой удвоенной точности (по-английски, floating point with double precision), в связи с чем во многих языках программирования для таких представлений используется специальный тип данных double.

На этом мы закончим обсуждение чисел с плавающей точкой. Здесь были изложены только общие принципы их построения. Интересующиеся более детальным изучением чисел с плавающей точкой могут поискать дополнительную информацию на интернете, пользуясь ключевыми словами float и double. Вы также можете найти интересную информацию и ссылки на страницы у нас на форуме по адресу:

ЗДЕСЬ

14. Символы и тексты.

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

Как легко понять, прежде, чем говорить о тексте, надо разобраться с одиночными символами. К счастью, тут ничего даже изобретать не надо. Представление букв и цифр в двоичном виде было создано задолго до компьютеров. Поняли, о чем идет речь? Если вместо нулей использовать короткие сигналы (точки), а вместо единиц - длинные (тире), то получится давно используемая в телеграфе азбука Морзе.

Азбуку Морзе не стали все же использовать без изменений. В частности, в азбуке Морзе все буквы обозначались кодами разной длины, а в компьютерах коды одинаковой длины. В свое время использовалась длина в семь бит на символ, однако позднее повсеместно были приняты кодировки, использующие по одному байту на символ. И на сегодняшний день используются по крайней мере две такие кодировки - ASCII и EBCDIC. Вся разница между ними - различные коды для одних и тех же символов.

Как мы уже знаем, один байт обеспечивает хранение одной из 256 возможных комбинаций. Таким образом, любая однобайтная система кодировки обеспечивает набор, достаточный для строчных и заглавных букв латинского алфавита, (включая буквы, специфические для отдельных языков), цифр, специальных значков, да и еще остаются неиспользуемые коды. Их можно использовать по-разному. Например, можно добавить русский алфавит, причем места хватит как для строчных, так и для заглавных русских букв.

Однако, в последние несколько лет с однобайтовыми кодами для символов появились проблемы: в процессе происходящей повсеместно интернационализации компьютерной индустрии оказалось необходимым обеспечить языки с иероглифической письменностью, такие как японский и китайский. Количество используемых знаков в этих языках даже по минимальным нормам во много раз превышает 256. В чем же выход? Применили тот же прием, что и для представления чисел: если одного байта не хватает, можно использовать двухбайтовые и более длинные комбинации. Наиболее распространенной кодировкой символов, использующей по два байта на символ на сегодняшний день является Unicode. В некоторых случаях даже вернулись к старому, использовавшемуся еще в азбуке Морзе механизму: разной длине кодов для различных символов. Примером такой кодировки может служить UTF.
Коль скоро внутреннее представление для отдельных символов придумано, дальше уже все проще. В конце концов, любой текст - это всего лишь набор из нескольких символов, идущих подряд, так что, по идее, достаточно расположить подряд в памяти компьютера коды соответствующих символов, и можно считать, что текст готов. Возникающие при этом определенные технические сложности находятся за пределами рассмотрения этой статьи.
Information
  • Posted on 31.01.2010 23:40
  • Просмотры: 2937