Хотя метод хранения информации в виде закодированных символов удобен, он неэффективен, когда мы имеем дело только с числовой информацией. Чтобы понять, почему это так, рассмотрим, как будет храниться число 25. Если мы хотим хранить его в стандарте ASCII, используя для каждого символа 1 байт памяти, то нам потребуется в общей сумме 16 битов. Кроме того, самое большое число, которое мы можем представить, используя 16 битов, это 99. Более эффективным является хранение числового значения в двоичном представлении.
Двоичное представление (binary notation) — это способ записи числовых значений, в котором используются только 0 и 1, а не 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9, как в традиционной, десятичной, системе счисления. Напомним, что в десятичной системе счисления каждой позиции в записи числа соответствует определенный разряд. В записи числа 375 цифра 5 занимает позицию единиц, 7 — позицию десятков, 3 — позицию сотен (рис. 1, а). При смещении по записи числа влево вес разряда увеличивается в десять раз. Значение, представленное записью, можно получить, умножив значение каждого числа на вес его разряда и затем сложив полученные произведения. Например, запись 375 имеет вид (3 х 100) + (7 х 10) + (5х 1).
Рисунок 1 – Десятичная и двоичная системы счисления: а – десятичная система счисления; б – двоичная система счисления
В двоичном представлении каждая позиция в записи числа также соответствует определенному разряду, при движении по записи числа влево вес разряда каждый раз увеличивается в два раза. Более точно, вес разряда последнего числа справа равен единице (2°), вес разряда следующего числа равен двум (21), следующего — четырем (22), следующего — восьми (23) и т. д. Например, в двоичной записи 1011 самая крайняя справа 1 соответствует весу разряда, равному единице, следующая единица — весу разряда, равному двум, 0 соответствует весу разряда, равному четырем, а самая крайняя слева 1 — весу разряда, равному восьми (рис. 1, б).
Чтобы получить значение, представленное двоичной записью, выполняем те же действия, как в случае с десятичной системой счисления: умножаем значение каждой цифры на вес соответствующего разряда и складываем полученные произведения. Например, значение, имеющее запись 100101, равно 37 (рис. 2). Обратите внимание на то, что поскольку в двоичном представлении используются только 0 и 1, то получение значения числа сводится к суммированию тех разрядов, в которых в записи стоит единица. Следовательно, двоичная запись 1011 имеет значение 11, так как единицы соответствуют разрядам 1, 2 и 8.
Рисунок 2 – Расшифровка двоичной записи 100101
Последовательность двоичных записей, соответствующих десятичным числам от 0 до 8, выглядит следующим образом: 0, 1, 10, 11, 100, 101, 110, 111, 1000.
Существуют различные подходы к получению этой последовательности, и хотя они не всегда красивы с теоретической точки зрения, однако обеспечивают быстрое получение двоичной записи небольших чисел. Один подход — представить счетчик пройденного пути автомобиля, содержащий только числа 0 и 1 на своем табло. Счетчик пройденного пути стоит на 0 и затем показывает 1, когда машина начинает двигаться. Затем единица снова заменяется нулем, при этом соседнее значение слева становится равным 1, и мы имеем 10. Потом 0 справа заменяется единицей, и значение на счетчике пройденного пути становится равным 11. Теперь самое крайнее значение и значение справа от него опять заменяются нулями, что приводит к появлению единицы на третьем колесе счетчика пройденного пути, который теперь показывает 100.
Для получения двоичной записи больших положительных чисел можно использовать более систематический подход, описываемый следующим алгоритмом.
Шаг 1. Разделите число на два и запишите остаток деления.
Шаг 2. До тех пор пока частное не равно нулю, продолжайте делить частные на два и записывать остаток.
Шаг 3. Когда частное станет равно нулю, двоичная запись числа будет состоять из остатков деления, выписанных справа налево в том порядке, в каком они были получены.
Применим этот алгоритм к числу 13 (рис. 3). Сначала делим тринадцать на два, получаем частное, равное шести, и единицу в остатке; так как частное не равно нулю, делим его на два в соответствии с шагом 2. В результате имеем новое частное, равное трем, и ноль в остатке. Это частное также не равно нулю, поэтому делим его на два, получая частное, равное единице, и два в остатке. Еще раз делим частное (единицу) на два, в этот раз частное равно нулю, а остаток единице. Так как мы получили в результате деления ноль, то переходим к третьему шагу и получаем двоичную запись исходного значения (тринадцать), которая имеет вид 1101.
Рисунок 3 – Получение двоичной записи числа 13
Теперь вспомним пример хранения числа 25, который мы привели в начале этого раздела. Как мы заметили, для представления этого числа в стандарте ASCII потребуется два байта памяти, и самое большое число, которое мы сможем сохранить в этих двух байтах, равно 99. Однако если мы будем использовать двоичное представление, мы сможем хранить целые числа в интервале от 0 до 65 535, что является значительным усовершенствованием.
По этой и другим причинам числовую информацию принято хранить в виде двоичной записи, а не в виде закодированных символов. Мы говорим «в виде двоичной записи», потому что обычная двоичная система счисления описывает только основы нескольких способов хранения числовой информации, используемые в машинах. Некоторые из этих вариантов двоичной системы счисления обсуждаются далее в этой главе. Сейчас мы просто обращаем внимание на то, что для хранения целых чисел принята система кодирования, называемая представлением в дополнительном коде, потому что она дает возможность кодирования и положительных, и отрицательных чисел. Для хранения чисел с дробной частью, таких как 4 (1/2) используется другая форма, называемая представлением чисел с плавающей точкой. Таким образом, отдельное значение (например, 25) может быть представлено различными последовательностями битов (как символ, закодированный в стандарте ASCII; в представлении в дополнительном коде или в форме с плавающей точкой, как 250/2), и наоборот, отдельную последовательность битов можно интерпретировать по-разному.
В завершение этого раздела следует упомянуть проблемы, связанные с системами хранения чисел, которые мы рассмотрим позже. Независимо от размера области памяти, которую машина может выделить для хранения числового значения, все равно будут появляться слишком большие целые числа или слишком маленькие дроби, не помещающиеся в эту область. Поэтому всегда существует возможность ошибок, таких как переполнение (число слишком большое) или усечение (дробь слишком маленькая). С ними необходимо бороться, иначе ничего не подозревающий пользователь столкнется с множеством ошибочных данных.
Сложение в двоичной системе счисления.Перед тем как сложить два числа в двоичной записи, вспомним сначала основные правила сложения (рис. 4), как в начальной школе по отношению к десятичной системе счисления.
Рисунок 4 – Правила сложения в двоичной системе
Используя эти правила, мы находим сумму двух чисел следующим образом: сначала складываем числа в последнем столбце, записываем младший разряд полученной суммы под столбцом, а старший (если он есть) — в следующий слева столбец, и продолжаем сложение. Например, решение задачи
+00111010
00011011
мы начинаем со сложения 0 и 1 в последнем столбце, получаем единицу, которую записываем под столбцом. Теперь мы складываем две единицы из следующего столбца, получая 10. Записываем 0 под столбцом, а 1 — над следующим столбцом. На этом этапе процесс решения выглядит следующим образом:
00011011
Складываем 1, 0 и 0, получаем 1 и записываем ее под этим столбцом. Следующие две единицы в сумме дают 10, записываем 0 под столбцом и переносим 1 в следующий столбец. Теперь решение выглядит так:
+00111010
00011011
Три единицы в следующем столбце в сумме дают 11, записываем младшую 1 под столбцом, а другую переносим в следующий столбец. Теперь складываем 1, 1 и 0, получаем 10. Снова записываем 0 под столбцом, а 1 — в следующий столбец.
+00111010
00011011
Складываем 1, 0 и 0 из предпоследнего столбца, получаем 1, записываем ее под столбцом. И, наконец, сумма чисел в последнем столбце равна 0, записываем ее под столбцом. Окончательное решение выглядит так:
+00111010
00011011
Дроби в двоичной системе счисления.При представлении дробей используется точка, чтобы отделить целую часть от дробной части. Цифры слева от точки являются целой частью числа и записываются в двоичном представлении по принципу, изложенному выше. Цифры справа от точки являются дробной частью числа и записываются так же, как целые, с той лишь разницей, что каждой позиции в записи числа соответствует разряд, вес которого является дробным числом. То есть вес разряда, соответствующего первой позиции после точки, равен 1/2, второй позиции — 1/4, следующей — 1/8 и т. д. Обратите внимание на то, что эта закономерность представляет собой лишь продолжение правила, сформулированного выше: при движении по записи числа влево вес разряда увеличивается в два раза. Для того чтобы получить десятичное представление дробного числа из его двоичной записи, нужно выполнить те же действия, что и в случае с целым числом: умножить значение каждой цифры на пес соответствующего разряда. Как перевести двоичное число 101.101 в десятичную дробь 55/8, показано на рис. 5.
Рисунок 5 – Расшифровка двоичной записи 101.101
Для сложения двух чисел также применяется методика, которая используется для целых чисел. То есть, чтобы получить сумму двух дробных чисел, записываем числа одно под другим так, чтобы точки находились в одном столбце, и выполняем те же действия, как с целыми числами. Например, числа 10.011 и 100.101 в сумме дают 111.000:
