Введение

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

Исчерпывающее изложение способов представления чисел в компьютере и выполнения арифметических операций можно найти в [ REF _Ref302564317 \r \h 1 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003300300032003500360034003300310037000000 REF _Ref302555646 \r \h 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003300300032003500350035003600340036000000 ]. Детальная информация о представлении вещественных чисел содержится в стандарте [ REF _Ref265592159 \r \h 2 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003200360035003500390032003100350039000000 ].

1.       Представление целых чисел в компьютере. Двоичная запись. Биты

Целые числа являются простейшим типом данных, оперируемых компьютером. Для целых чисел различают 2 вида представления: беззнаковое и представление со знаком. Беззнаковое представление применяется для неотрицательных целых чисел. Примером таких данных могут служить адреса в памяти компьютера, которые отсчитываются от 0 и поэтому всегда неотрицательны. Представление со знаком применяется в случае, когда нужно хранить и положительные, и отрицательные числа.

В данном разделе рассматривается беззнаковое представление, различные способы представления чисел со знаком изложены в следующем разделе.

Как известно, любое целое число может быть представлено в двоичной системе счисления, будем называть это представление двоичной записью числа. Например, число 5719 в двоичной системе записывается в виде 5719₁₀ = 1011001010111₂, 1011001010111 является его двоичной записью.

Вся информация в компьютере представляется в виде последовательности двоичных разрядов, называемых битами. Бит может принимать одно из двух значений: 0 или 1, таким образом, бит является цифрой в двоичной системе счисления[1]. 8 расположенных подряд бит объединяются в байт.

Будем считать, что для хранения чисел используется ячейка памяти размера n бит. Типичные значения n на современных компьютерах: 8, 16, 32 и 64 бита (1, 2, 4 и 8 байт соответственно). Существует 2n  различных комбинаций значений n бит (по 2 возможных значения для каждого бита, значения всех битов независимы друг от друга, поэтому общее число возможных комбинаций является произведением числа возможных значений для каждого бита). Следовательно, ячейка памяти размером n бит может быть использована для однозначного представления не более 2n  различных чисел.

Таким образом, с использованием n бит при данной схеме могут быть представлены все целые числа от 0 до 2n-1  включительно. Двоичная запись числа может быть короче, чем n бит, в этом случае дополним ее нулями слева для достижения требуемого количества. Полученную последовательность битов будем называть двоичным представлением числа.

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

В качестве примера рассмотрим беззнаковое представление числа 5719 в ячейке памяти из 16 бит: двоичной записью числа является 1011001010111, она содержит 13 бит, для получения двоичного представления дополним ее тремя (16 – 13) стартовыми нулями, получим последовательность 0001011001010111. Число 571900 не может быть представлено аналогичным образом с использованием 16 бит, так как его двоичная запись (10010000011101010100) слишком длинна – она состоит из 20 бит и (при используемой схеме) не может убраться в 16. В то же время оно может быть представлено в 32-битной ячейке памяти.

В языке программирования Pascal для представления целых чисел без знака используются следующие типы данных:

1. Byte: размер 1 байт, диапазон значений от 0 до 255 включительно (255 = 2⁸ – 1).
2. Word: размер 2 байта, диапазон значений от 0 до 65535 включительно (65535 = 2¹⁶ – 1).

2.       Хранение отрицательных чисел. Дополнительный код

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

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

Заметим, что при применении описанного способа возможны 2 представления нуля, отличающихся старшим битом и содержащие 0 во всех остальных битах («+0» и «–0»). Данная сложность может быть преодолена с помощью специальной договоренности о представлении нуля. При использовании прямого кода (без дополнительных договоренностей) представимы все целые числа в диапазоне от -2n-1-1  до 2n-1-1  включительно (общее количество представимых чисел равно 2n-1  из-за двух представлений нуля).

В качестве примера рассмотрим представление числа –51 в 8-битном прямом коде. Число отрицательное, следовательно, старший бит прямого кода равен 1. 51₁₀ = 110011₂, двоичное представление модуля равно 0110011 (используется 8 – 1 = 7 бит). Таким образом, прямой код числа –51 равен 10110011.

Несмотря на интуитивную простоту у прямого кода есть существенный недостаток, связанный со сложностью реализации арифметических операций, подробнее он разобран в конце данного раздела. В связи с этим в большинстве современных компьютеров для представления целых чисел со знаком используется дополнительный код. Дополнительный код неотрицательного числа совпадает с его прямым кодом. Дополнительный код отрицательного числа x  равен двоичной записи[2] числа 2n-|x| . При использовании данного формата проблемы с двумя представлениями нуля нет и представимы все целые числа в диапазоне от -2n-1  до 2n-1-1  включительно.

При этом старший бит дополнительного кода отрицательных чисел равен 1, а дополнительного кода неотрицательных чисел равен 0. Асимметрия диапазона представимых значений в сторону отрицательных, а не положительных, чисел связана с поддержкой данного свойства (в случае противоположной асимметрии дополнительный код числа 2n-1  единственный из дополнительных кодов положительных чисел имел бы старший бит равный 1, что нарушало бы общность).

Для примера рассмотрим представление числа –51 в 8-битном дополнительном коде (представление данного числа в прямом коде рассматривалось выше). Число отрицательное, следовательно, дополнительный код равен двоичной записи числа 28  – 51 = 205₁₀ = 11001101₂. Таким образом, дополнительный код числа –51 равен 11001101.

Для представления целых чисел со знаком в языке программирования Pascal используются следующие типы данных:

1. Shortint: размер 1 байт, диапазон значений от –128 до 127 включительно (–128 = –2⁷, 127 = 2⁷ – 1).
2. Integer: размер 2 байта, диапазон значений от –32768 до 32767 включительно (–32768 = –2¹⁵, 32767 = 2¹⁵ – 1).
3. Longint: размер 4 байта, диапазон значений от –2147483648 до 2147483647 включительно (–2147483648 = –2³¹, 2147483647 = 2³¹ – 1).

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

Еще одним способом представления отрицательных целых чисел является обратный код. Обратный код положительного числа совпадает с его прямым кодом, обратный код отрицательного числа x  равен двоичной записи числа 2n-x-1 . Исследование свойств данного представления предлагается для самостоятельной работы.

Достоинства и недостатки рассмотренных видов представления целых чисел, а также способы представления очень больших целых чисел и выполнения арифметических операций над ними подробно рассмотрены в [ REF _Ref302564317 \r \h 1 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003300300032003500360034003300310037000000 ].

3.       Битовые операции

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

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

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

Побитовое отрицание (побитовое НЕ, дополнение, NOT) – унарная (имеющая одним операнд) операция, состоящая в применении логического отрицания к каждому биту двоичного представления операнда. Таким образом, бит результата равен 1 тогда и только тогда, когда соответствующий бит операнда был равен 0. Например, NOT 01011101 = 10100010.

Побитовое И (AND) – бинарная (имеющая два операнда) операция, состоящая в применении логического И к каждой паре битов, стоящих на одинаковых позициях в двоичном представлении операндов. Таким образом, бит результата равен 1 тогда и только тогда, когда оба соответствующих бита операндов были равны 1. Например, 10110101 AND 00011001 = 00010001.

Побитовое ИЛИ (OR) – бинарная операция, состоящая в применении логического ИЛИ к каждой паре битов, стоящих на одинаковых позициях в двоичной записи операндов. Таким образом, бит результата равен 1 тогда и только тогда, когда хотя бы один из соответствующих битов операндов был равен 1. Например, 10110101 OR 00011001 = 10111101.

Побитовое исключающее ИЛИ (XOR) – бинарная операция, состоящая в применении логического исключающего ИЛИ к каждой паре битов, стоящих на одинаковых позициях в двоичной записи операндов. Таким образом, бит результата равен 1 тогда и только тогда, когда соответствующие биты операндов различны (ровно один из соответствующих битов операндов равен 1). Например, 10110101 XOR 00011001 = 10101100.

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

В языке программирования Pascal побитовому НЕ соответствует операция not, побитовым И, ИЛИ, исключающему ИЛИ – операции and, or, xor соответственно, побитовым сдвигам влево и вправо – операции shl, shr (от английских названий shift left, shift right).

Продемонстрируем применения битовых операций для получения значения определенного бита двоичного представления данного целого числа. Пусть необходимо получить значение j-го бита. Во-первых, занулим все остальные биты заданного представления (и не будем менять значение j-го). Далее сравним полученное значение с 0: если они равны, то искомый бит был равен 0, в противном случае он был равен 1. Для выполнения первой части выполним побитовое И со специально сгенерированным числом, называемым маской. В данном случае маской будет являться двоичная запись числа 2j : она содержит 1 в позиции j, все остальные ее биты равны нулю. Данное число является результатом побитового сдвига 1 влево на j разрядов. При выполнении побитового И с данной маской значение j-го бита будет сохранено, значения остальных битов станут равны 0. Далее приведена реализация данной функции на языке Pascal, возвращающее значение типа boolean:

function get_bit(x, j: integer): boolean;

{Функция получения значения j-го бита числа x. Возвращает true, если бит был равен 1, иначе false}

var mask: integer;

begin

  mask := 1 shl j;

  if (x and mask = 0) then

    get_bit := false;

  else

    get_bit := true;

end;

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

4.       Представление вещественных чисел

Вещественные числа наиболее широко применяются в компьютерных вычислениях. При этом способ их представления и выполнения арифметических операций является существенно более сложным по сравнению с целыми числами, неаккуратная работа с вещественными числами в прошлом не раз приводила к катастрофам, таким как, например, падение ракеты. В данном разделе даются базовые сведения о представлении вещественных чисел. Исчерпывающие сведения по данному вопросу можно найти в стандарте [ REF _Ref265592159 \r \h 2 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003200360035003500390032003100350039000000 ].

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

Для общности будем формулировать понятия с использованием произвольного целого числа p≥2 .

Под экспоненциальной записью числа x будем понимать его представление в виде x=m*pq , где q – целое число, m может быть целым или вещественным. Естественно, каждое число имеет бесконечно много экспоненциальных записей: x=x*p0=xp*p1=xp2*p2=…=xp*p-1=… .

Будем называть экспоненциальную запись числа x≠0  нормализованной, если выполняется ограничение 1≤m<p . В таком случае m называется мантиссой, а q – порядком числа[3]. Для краткости в дальнейшем будем называть нормализованную экспоненциальную запись просто нормализованной записью. Несложно показать, что любое ненулевое число представляется единственной нормализованной записью, выражение соответствующих значений m и q через x оставляется в качестве упражнения для самостоятельной работы. Таким образом, при фиксированном p любое ненулевое вещественное число определяется единственным образом парой из мантиссы и порядка. Для нуля тоже можно определить единственную нормализованную запись.

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

Рассмотрим пример. Пусть p=10 , записи  0,035621 * 101  и 3,5621 * 10-1  являются двумя экспоненциальными записями числа 0,35621. При этом первая запись не является нормализованной (так как 0,035621<1 ), а вторая – является (так как 1≤3,5621 <10 ). Компьютерный способ представления нормализованной записи: 3,5621 * 10-1=3,5621E-1 .

Для представления вещественных чисел в компьютере обычно используется экспоненциальное представление для p=2  (также иногда используются варианты с p=10 , мы не будем их рассматривать). В связи с этим форма представления вещественных чисел в компьютере называется числами с плавающей запятой (другой применяемый вариант – числа с плавающей точкой – является дословным переводом соответствующего английского названия floating-point).

Для почти всех чисел это нормализованное представление, однако для чисел, очень близких к 0, с целью повышения точности используется ненормализованное. Подробности изложены в [ REF _Ref265592159 \r \h 2 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003200360035003500390032003100350039000000 ], мы не будем углубляться в тонкости и рассмотрим лишь нормализованное представление. Нормализованное вещественное число представляется тройкой: знак, мантисса (которая при этом неотрицательна), порядок. Один бит представления используется для хранения знака (0 для положительных, 1 для отрицательных), часть остальных бит для хранения порядка, остальные – для мантиссы. Количество бит для хранения мантиссы и порядка определяется используемым типом данных. Стандартные размеры ([ REF _Ref265592159 \r \h 2 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003200360035003500390032003100350039000000 ]): 8 бит для порядка и 23 бита для мантиссы (так называемая одинарная точность); 11 бит для порядка и 52 бита для мантиссы (двойная точность).

Для удобства выполнения операций хранится не само значения порядка, а смещенный порядок, равный разности порядка и минимально возможного (для используемого типа данных) порядка. Таким образом, смещенный порядок всегда неотрицателен и хранится как беззнаковое целое. Если p=2 , из условия 1≤m<p  (знак мантиссы хранится отдельно, поэтому считаем, что m>0 ) следует, что m=1,…  то есть перед запятой в мантиссе всегда стоит 1 и ее можно не хранить и тем самым сэкономить 1 бит для еще одной двоичной цифры мантиссы (для других значений p  это неверно). Цифры мантиссы после запятой также представляются в виде, подобном беззнаковым целым, разница лишь в том, что при необходимости они дополняются нулями справа.

Специальные значения порядка зарезервированы для представления 0 (точнее, 0 обоих знаков, в случае вещественных чисел это упрощает реализацию арифметических операций), бесконечности обоих знаков и NaN - нечисловых данных (например, результат деления 0/0). Данные специальные значения упрощают реализацию и анализ многих операций, подробное освещение можно найти в [ REF _Ref265592159 \r \h 2 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003200360035003500390032003100350039000000 ].

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

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

Для представления чисел с плавающей запятой в языке программирования Pascal используются следующие типы данных:

1. Single: размер 4 байта, диапазон значений абсолютной величины от 1,5E–45 до 3,4E38.
2. Real: размер 6 байт, диапазон значений абсолютной величины от 2,9E–39 до 1,7E38.
3. Double: размер 8 байт, диапазон значений абсолютной величины от 5E–324 до 1,7E308.
4. Extended: размер 10 байт, диапазон значений абсолютной величины от 3,4E–4932 до 1,1E4932.
5. Comp: размер 8 байт, диапазон значений от –2E63 +1 до 2E63 – 1.

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

1. 5.       Литература

5.1.       Использованные источники информации

1. Кнут Д. Искусство программирования, том 2. Получисленные методы. – 3-е изд. – М.: Вильямс, 2007. – С. 832.

5.2.       Дополнительная литература

1. IEEE Computer Society. IEEE Standard for Floating-Point Arithmetic. IEEE Standard 754-2008, August 2008.

5.3.       Информационные ресурсы сети Интернет

1. Электронный учебник по Информатике и Программированию на языке высокого уровня.

[http://kuzelenkov.narod.ru/mati/book/informat_prog.html