Двоичная система счисления

Мы с вами привыкли, что числа записываются в виде последовательности цифр. Всего различных цифр 10: от 0 до 9. Такой способ записи чисел называется десятеричной системой счисления. Вам это покажется странным, но десятеричная система крайне неудобна. Вообще говоря, своей популярностью десятеричная система обязана только тому капризу природы, благодаря которому у нас десять пальцев на руках. Было бы у нас двенадцать пальцев – мы бы считали не десятками, а дюжинами, и цифр было бы 12.

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

Таким образом, минимальное количество информации, которое можно записать – одна двоичная цифра. По-английски словосочетание «двоичная цифра» пишется binary digit, отсюда произошло название минимальной единицы информации – бит (BInary digiT).

Если один бит имеет только два возможных значения: 0 и 1, то два бита могут иметь четыре разных значения: 00, 01, 10 и 11, а три бита – восемь значений: 000, 001, 010, 011, 100, 101, 110 и 111. Проверьте самостоятельно, что 4 бита могут иметь 16 различных значений. Вообще, при добавлении одного бита, количество вариантов удваивается. Таким образом, для n бит количество вариантов можно рассчитать по следующей формуле:

V=2ⁿ.

Таким образом, если необходимо записать какую-то величину, которая может принимать не более 2ⁿ различных значений, то достаточно n бит. Например, для записи числа, которое может принимать значения от 1 до 100 достаточно 7 бит, так как 100<128=2⁷, при этом останется еще 28 комбинаций бит, которые можно использовать для обозначения чисел от 100 до 128 или от 100 до 127 и еще числа 0. Второй вариант предпочтительней и на практике в подавляющем большинстве случаев применяется именно он, так как комбинацию 0000000 логично считать нулем, а не каким-то другим значением. Таким образом, комбинацией из семи бит, как правило, обозначаются числа от 0 до 127, комбинацией из восьми бит – от 0 до 255 и т.д. Разумеется, бывают и исключения. Например, если известно, что некоторая величина принимает значения, скажем, от 300 до 555 (256 различных значений), то эффективней принять число 300 за начало отсчета (вместо нуля) и использовать 8 бит для записи значения этой величины. В этом случае комбинация 00000000 будет означать число 300, комбинация 00000001 – 301, а комбинация 11111111 – 555, однако это следует делать только в том случае, если не требуется выполнять арифметических операций с этими значениями.

Если нумерация начинается с нуля (что, как уже говорилось, и используется обычно на практике), то арифметические операции с двоичными числами происходят по тем же законом, что и операции с десятичными за тем исключением, что в двоичной системе не существует никаких цифр старше единицы. Например, 0+0=0, 0+1=1, 1+0=1 – эти равенства справедливы как для десятичной, так и для двоичной системы. А чему равно 1+1 в двоичной системе? В десятичной системе ответ 2, но в двоичной системе нет такой цифры! Что происходит, когда к десятичной цифре 9 прибавляем 1? Так как цифры старше девятки нет, происходит перенос единицы в следующий разряд, а сама девятка превращается в ноль, т.е. 9+1=10. Аналогично и в двоичной системе: так как цифры старше единицы нет, следовательно, 1+1=10. Ничего удивительного в этом нет, просто таким образом (числом 10) в двоичной системе обозначается число 2. Для того, чтобы не возникало путаницы, будем к каждому числу подписывать систему счисления, в которой оно записано, например, результат предыдущих размышлений можно записать так: 10₂=2₁₀, т.е. 10 в двоичной равно 2 в десятичной. Рассуждая по аналогии, 10₂+1=11₂ (просто прибавили 1 к младшему разряду), 11₂+1=100₂ (происходит перенос сначала во второй разряд, а затем в третий), 100₂+1=101₂ и т.д.

Можно складывать двоичные числа столбиком. При этом, иногда, придется складывать сразу три единицы: две единицы, записанные в каком-то разряде складываемых чисел и перенос из предыдущего разряда. В таких случаях следует помнить, что 1+1+1=11₂. Пример сложения приведен на рис. 1.4.1.1.

Рис. 1.4.1.1  Сложение двоичных чисел столбиком

Если сложить 11111111₂ и 1 получим 100000000₂, т.е. здесь мы наблюдаем «цепную реакцию», когда перенос единицы в один разряд вызывает перенос в следующий разряд и т.д. Обратите внимание, что если на хранение некоторой величины было выделено 8 бит, и она содержала значение 11111111₂, а затем увеличилась на единицу, то результат станет девятиразрядным, т.е. места на самый старший, девятый, разряд не хватит! В этом случае данная величина станет равной 00000000₂, т.е. обнулится.

Для двоичных чисел можно использовать и операцию вычитания, главное при этом иметь в виду, что раз 1+1=10₂, значит 10₂-1=1, т.е. при вычитании единицы из нуля требуется заем из старшего разряда. Пример вычитания столбиком показан на рис. 1.4.1.2.

Рис. 1.4.1.2  Вычитание двоичных чисел столбиком

Каким образом можно записать отрицательное число? Можно ввести еще один разряд – для знака, например, 0 будет означать плюс, а 1 – минус. Однако это, очевидное на первый взгляд, решение крайне неудобно.

Как мы видели, когда количество разрядов ограничено (а количество разрядов всегда так или иначе ограничено, ведь память компьютера не бесконечна), может возникнуть переполнение, при котором происходит обнуление. Например, как было рассмотрено выше, если хранится только 8 разрядов числа, то 11111111₂+1=0. Отсюда следует, что 0-1=11111111₂, иначе говоря, если последовательностью из одних единиц обозначить число –1, то мы получим вполне корректные равенства! Именно этот подход и используется на практике, т.е. для восьмизначных чисел –1 обозначается как 11111111₂, для шестнадцатизначных – 1111111111111111₂ (16 единиц) и т.д. Число –2 на единицу меньше, чем –1, поэтому его можно обозначить (для восьмизначных чисел) последовательностью 11111110₂. Обратите внимание, что те же самые последовательности используются для чисел 255 и 254, поэтому при написании программ разработчикам необходимо указывать, как следует воспринимать число: как знаковое или как беззнаковое.

Разумеется, двоичные числа можно умножать. Мы не будем подробно рассматривать умножение, остановимся только на простейшем случае: умножение на 2. Как уже говорилось, в двоичной системе двойка записывается в виде числа 10₂. В десятичной системе при умножении на 10₁₀ необходимо просто дописать в конце 0. То же самое можно использовать и в двоичной системе, например 10111₂х10₂=101110₂. Отсюда следует интересная закономерность: числа, которые являются степенями двойки, являются в двоичной системе счисления «круглыми» числами, причем число, стоящее в показатели степени равно количеству нулей в числе. В табл. 1.4.1.1 приведены числа от 2⁰ до 2⁸. Эту таблицу можно использовать для перевода чисел из двоичной системы в десятичную и наоборот. Например, число 1010011₂=1000000₂+10000₂+10₂+1₂=64₁₀+16₁₀+2₁₀+1₁₀=83₁₀. Сделаем обратный перевод: 100₁₀=64₁₀+32₁₀+4₁₀=1000000₂+100000₂+ +100₂=1100100₂.

Табл. 1.4.1.1  Степени двойки

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

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