Код. Тайный язык информатики

На старте женского одиночного зачета в Уимблдонском турнире – 128ДЕСЯТЬ, или 200ВОСЕМЬ, участниц.

Площадь Мемфиса равна 640ДЕСЯТЬ, или 1000ВОСЕМЬ, квадратных километров.

Обратите внимание: в этом списке есть несколько круглых восьмеричных чисел. Круглым называется число, оканчивающееся на один или несколько нулей. Если десятеричное число оканчивается двумя нулями, значит, оно кратно 100ДЕСЯТЬ, а 100ДЕСЯТЬ – это 10ДЕСЯТЬ, умноженное на 10ДЕСЯТЬ. В восьмеричной системе два нуля в конце числа означают, что число кратно 100ВОСЕМЬ, то есть 10ВОСЕМЬ умножить на 10ВОСЕМЬ (или 8ДЕСЯТЬ умножить на 8ДЕСЯТЬ, что равно 64ДЕСЯТЬ).

Возможно, вы также заметили, что такие круглые восьмеричные числа, как 100ВОСЕМЬ, 200ВОСЕМЬ и 400ВОСЕМЬ, в десятеричной системе соответствуют 64ДЕСЯТЬ, 128ДЕСЯТЬ и 256ДЕСЯТЬ, и все эти десятеричные числа – степени двойки. Это логично. Например, число 400ВОСЕМЬ, равно 4ВОСЕМЬ умножить на 10ВОСЕМЬ и умножить на 10ВОСЕМЬ, и все это – степени двойки. Всякий раз при умножении степени двойки на степень двойки мы получаем еще одну степень двойки.

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

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

Структурно восьмеричная система аналогична десятеричной. Отличия лишь в деталях. Например, каждая позиция в восьмеричном числе – это цифра, умноженная на степень восьмерки.

Следовательно, восьмеричное число 3725ВОСЕМЬ можно разбить:

3725ВОСЕМЬ = 3000ВОСЕМЬ + 700ВОСЕМЬ + 20ВОСЕМЬ + 5ВОСЕМЬ.

Эту последовательность можно переписать несколько иначе. Например, при помощи степеней восьмерки в их десятеричном представлении:

3725ВОСЕМЬ = 3 × 512ДЕСЯТЬ +

7 × 64ДЕСЯТЬ +

2 × 8ДЕСЯТЬ +

5 × 1.

То же самое, записанное при помощи степеней восьмерки в восьмеричном представлении:

3725ВОСЕМЬ = 3 × 1000ВОСЕМЬ +

7 × 100ВОСЕМЬ +

2 × 10ВОСЕМЬ +

5 × 1.

А можно сделать вот так:

3725ВОСЕМЬ = 3 × 83 +

7 × 82 +

2 × 81 +

5 × 80.

Если выполнить эти расчеты в десятеричной системе, получится 2005ДЕСЯТЬ. Таким образом восьмеричные числа преобразуются в десятеричные.

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

Например, 5ВОСЕМЬ + 7ВОСЕМЬ = 14ВОСЕМЬ, то есть восьмеричные числа можно складывать в столбик.

Начинаем справа: 5 плюс 3 равно 10, 0 пишем, 1 в уме; 1 плюс 3 плюс 4 равно 10, 0 пишем, 1 в уме; 1 плюс 1 плюс 6 равно 10.

Аналогично дважды два и в восьмеричной системе равно четырем. Но трижды три не равно девяти. А как? Трижды три равно 11ВОСЕМЬ, это столько же, сколько и 9ДЕСЯТЬ. Далее полностью приведена восьмеричная таблица умножения.

Здесь у нас 4 × 6 равно 30ВОСЕМЬ, но 30ВОСЕМЬ равно 24ДЕСЯТЬ, то есть 4 × 6 в десятеричной системе.

Восьмеричная система счисления столь же полноценна, как и десятеричная.

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

Вот как считают в четверичной системе: 0, 1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 32, 33, 100, 101, 102, 103, 110 и т. д.

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

В четверичной системе счисления число 31 232 можно записать следующим образом:

31 232ЧЕТЫРЕ = 3 × 256ДЕСЯТЬ +

1 × 64ДЕСЯТЬ +

2 × 16ДЕСЯТЬ +

3 × 4ДЕСЯТЬ +

2 × 1ДЕСЯТЬ.

Что равнозначно записи:

31 232ЧЕТЫРЕ = 3 × 10 000ЧЕТЫРЕ +

1 × 1000ЧЕТЫРЕ +

2 × 100ЧЕТЫРЕ +

3 × 10ЧЕТЫРЕ +

2 × 1ЧЕТЫРЕ.

А это то же самое, что и:

31 232ЧЕТЫРЕ = 3 × 44 +

1 × 43 +

2 × 42 +

3 × 41 +

2 × 40.

Если мы выполним вычисления в десятичной системе счисления, то обнаружим, что 31 232ЧЕТЫРЕ – это 878ДЕСЯТЬ.

Теперь мы сделаем еще один прыжок, на этот раз окончательный. Представьте, что мы дельфины и можем использовать для подсчета два плавника. В данном случае мы имеем дело с системой счисления с основанием 2, или двоичной, или, иначе, бинарной (от лат. binary – «двойной», «состоящий из двух частей»). Понятно, что у нас будет только две цифры: 0 и 1.

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

Да, в двоичной системе счисления за 1 следует 10. Это странно, однако это не должно удивлять. Независимо от того, какую систему счисления мы используем, всякий раз, когда у нас заканчиваются отдельные цифры, первое двузначное число всегда 10. В двоичной системе счисления мы считаем:

0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, 10001…

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

Количество голов у людей – 1ДЕСЯТЬ, или 1ДВА.

Количество плавников у дельфинов – 2ДЕСЯТЬ, или 10ДВА.

Количество чайных ложек в столовой ложке – 3ДЕСЯТЬ, или 11ДВА.

Количество сторон у квадрата – 4ДЕСЯТЬ, или 100ДВА.

Количество пальцев на одной человеческой руке – 5ДЕСЯТЬ, или 101ДВА.

Количество конечностей у насекомых – 6ДЕСЯТЬ, или 110ДВА.

Количество дней в неделе – 7ДЕСЯТЬ, или 111ДВА.

Количество музыкантов в октете – 8ДЕСЯТЬ, или 1000ДВА.

Количество планет в Cолнечной системе, включая Плутон, – 9ДЕСЯТЬ, или 1001ДВА.

Количество центнеров в тонне – 10ДЕСЯТЬ, или 1010ДВА.

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

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

Допустим, у нас есть двоичное число 101101011010. Его можно записать так:

101101011010ДВА = 1 × 2048ДЕСЯТЬ +

0 × 1024ДЕСЯТЬ +

1 × 512ДЕСЯТЬ +

1 × 256ДЕСЯТЬ +

0 × 128ДЕСЯТЬ +

1 × 64ДЕСЯТЬ +

0 × 32ДЕСЯТЬ +

1 × 16ДЕСЯТЬ +

1 × 8ДЕСЯТЬ +

0 × 4ДЕСЯТЬ +

1 × 2ДЕСЯТЬ +

0 × 1ДЕСЯТЬ.

Или:

101101011010ДВА = 1 × 211 +

0 × 210 +

1 × 29 +

1 × 28 +

0 × 27 +

1 × 26 +

0 × 25 +

1 × 24 +

1 × 23 +

0 × 22 +

1 × 21 +

0 × 20.

Если просто сложить все слагаемые в десятичной системе, получим 2048 + 512 + 256 + 64 + 16 + 8 + 2, что составляет 2906ДЕСЯТЬ.

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

Эта схема позволяет конвертировать числа, содержащие до восьми двоичных разрядов; ее можно легко расширить. Введите до восьми цифр в восемь верхних полей, по одной цифре в каждый квадрат. Выполните восемь операций умножения и введите их результаты в восемь нижних полей. Сложите числа в этих восьми полях для получения окончательного результата. Этот пример демонстрирует процесс нахождения десятичного эквивалента двоичного числа 10010110.

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

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

Помните, что каждая целая часть будет равна либо 0, либо 1. Если делимое меньше делителя, то целая часть от деления будет равна 0, а остаток – самому делимому. Если делимое больше или равно делителю, то целая часть от деления будет равна 1, а остаток – разности между делимым и делителем. Вот как преобразуется число 150.

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

Давайте с помощью этой таблицы сложим два двоичных числа.

Начиная с правого столбца: 1 плюс 0 равно 1. Второй столбец справа: 0 плюс 1 равно 1. Третий столбец: 1 плюс 1 равно 0, 1 в уме. Четвертый столбец: 1 (перенесенное значение) плюс 0 плюс 0 равно 1. Пятый столбец: 0 плюс 1 равно 1. Шестой столбец: 1 плюс 1 равно 0, 1 в уме. Седьмой столбец: 1 (перенесенное значение) плюс 1 плюс 0 = 10.

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

Вот процесс умножения числа 13ДЕСЯТЬ на число 11ДЕСЯТЬ в двоичной системе счисления.

Результат – 143ДЕСЯТЬ.

Люди, работающие с двоичными числами, часто предваряют их нулями, то есть пишут нули слева от первой 1, например 0011 вместо 11. Это совершенно не влияет на значение, а служит исключительно для красоты. В следующей таблице перечислены первые шестнадцать двоичных чисел и их десятичные эквиваленты.

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

• в крайнем правом столбце – 0 и 1;

• во втором столбце справа – два 0 и две 1;

• в следующем столбце – четыре 0 и четыре 1;

• в крайнем левом столбце – восемь 0 и восемь 1.

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

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

При записи больших десятичных чисел мы используем запятые через каждые три знака для облегчения их восприятия[11]. Например, если вы увидите число 12000000, вероятно, придется подсчитать количество цифр, однако, увидев число 12,000,000, вы сразу поймете, что оно означает 12 миллионов.

Двоичные числа очень быстро могут стать весьма длинными. Например, 12 миллионов в двоичной системе счисления записывается так: 101101110001101100000000. Чтобы такое число было легче воспринимать, каждые четыре двоичных разряда обычно разделяются пробелами (1011 0111 0001 1011 0000 0000). Далее в этой книге мы рассмотрим более сжатый способ записи двоичных чисел.

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

Провод может представлять собой двоичную цифру. Если по нему идет ток, то двоичная цифра равна 1, если нет – 0.

Переключатель может представлять собой двоичную цифру. Если переключатель включен, или замкнут, то двоичная цифра равна 1, если переключатель выключен, или разомкнут, то двоичная цифра – 0.

Лампочка может представлять собой двоичную цифру. Если лампочка горит, то двоичная цифра равна 1, если нет – 0.

Телеграфное реле может представлять собой двоичную цифру. Если реле замкнуто, то двоичная цифра равна 1, если разомкнуто – 0.

Двоичные цифры имеют непосредственное отношение к компьютерам.

Примерно в 1948 году американский математик Джон Тьюки (род. 1915)[12] осознал, что в будущем словосочетание «двоичная цифра» (binary digit), вероятно, приобретет гораздо большее значение – по мере распространения компьютеров. Он решил создать новое, более короткое слово, чтобы заменить эти громоздкие пять слогов, и рассматривал такие варианты, как bigit и binit, но остановился на коротком, простом, элегантном и просто замечательном слове bit («бит»).

Глава 9. За битом бит

Когда в 1973 году Тони Орландо в своей песне попросил, чтобы любимая «повязала желтую ленточку вокруг старого дуба», он не сопроводил свою просьбу ни подробными объяснениями, ни долгими рассуждениями. Никаких «если», «и», «но». Несмотря на сложные чувства и эмоции, сопровождавшие ситуацию, что разворачивалась в реальной жизни и легла в основу песни, мужчине хотелось получить простой ответ: «да» или «нет». Он знал, что, если на старом дубе появится желтая ленточка, это будет означать: «Да, хотя ты и наворотил дел и провел три года в тюрьме, я все равно хочу, чтобы ты вернулся и мы жили под одной крышей». А отсутствие желтой ленточки скажет: «Даже не думай здесь останавливаться».

Здесь есть две четкие взаимоисключающие альтернативы. Тони Орландо не пел: «Повяжи половину желтой ленточки, если тебе нужно время на размышление» или «Повяжи голубую ленточку, если больше не любишь меня, но по-прежнему хочешь остаться друзьями». Нет, он все сформулировал очень просто.

Не менее информативно, нежели отсутствие или наличие желтой ленточки (разве что не столь поэтично), сработал бы дорожный знак, поставленный во дворе, например «Путь открыт» или «Въезд запрещен». Или табличка на двери «Закрыто» или «Открыто». Или фонарик на окне – включенный или выключенный.

Если вам нужно просто сказать «да» или «нет», то способов хватает. Для этого не надо произносить ни одной фразы, слова, даже буквы. Необходим всего один бит, то есть 0 или 1.

Как мы узнали в предыдущих главах, десятеричная система, которой мы пользуемся при подсчете предметов, на самом деле ничем не примечательна. Ясно, что мы пользуемся системой с основанием 10, так как у нас 10 пальцев на руках. Мы могли бы с тем же успехом использовать систему с основанием 8 (будь мы мультяшками), 4 (будь мы омарами) или даже 2 (если бы мы были дельфинами).

Однако двоичная система счисления все-таки особенная. Дело в том, что это простейшая возможная система счисления. В двоичной системе всего две цифры: 0 и 1. Если нам нужно что-то проще двоичной системы, придется избавиться от 1, и останется только 0. Имея всего лишь 0, ничего не сделаешь.

Слово «бит» – сокращение от английского выражения binary digit («двоичная цифра»). Пожалуй, это одно из симпатичнейших слов в компьютерной терминологии. В английском языке у слова bit есть и общеупотребительное значение – «кусочек, небольшая часть», и это значение нам отлично подходит, поскольку один бит – двоичная цифра, мельчайший фрагмент информации.

Иногда, если изобретается новое слово, ему присваивается новое значение. В данном случае все именно так. Слово «бит» – это не только двоичные цифры, при помощи которых удобно считать дельфинам. В компьютерную эпоху это слово приобрело значение «мельчайший первичный фрагмент информации».

Да, смелое утверждение. Естественно, информация передается не только при помощи битов. Буквы, слова, азбука Морзе и шрифт Брайля, а также десятеричные цифры тоже переносят информацию. Суть бита заключается в том, что он передает очень мало информации. Один бит – это минимально возможное количество информации. Меньше бита – отсутствие информации.

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

«Запомните, дети, – слышал весь мир, // Как в полночь глухую скакал Поль Ревир…» – писал Генри Лонгфелло. Возможно, он исторически недостоверно описал поступок Поля Ревира, предупредившего американских колонистов о вторжении британцев, однако эти стихи замечательно демонстрируют, как можно передать важную информацию при помощи битов.

Он другу сказал: «Я сигнала жду.Коль ночью из города наступатьНачнут британцы, ты дай мне знать,На Северной церкви зажги звезду, –Одну, если сушей, а морем – две»[13].

Итак, Ревир дал другу два фонаря. Если британцы вторгнутся по суше, друг зажжет на колокольне один, если высадятся с моря – то зажжет оба.

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

Допустим, два фонаря висят на колокольне всегда. Как правило, они не горят.

Значит, британцы пока не наступают. Если зажжен один фонарь, значит, британцы наступают по суше, если горят оба, – высаживаются с моря.

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

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

00 = британцы пока не наступают;

01 = британцы наступают с суши;

10 = британцы наступают с суши;

11 = британцы наступают с моря.

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

В случае с фонарями на колокольне к «шуму» можно отнести такие факторы, как темнота и расстояние от Поля Ревира до колокольни, которые могут помешать отличить первый фонарь от второго. Вот важнейший отрывок из стихов Лонгфелло:

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

Скорее всего, Поль Ревир был не в состоянии определить, какой фонарь зажегся первым.

Из этого следует важный вывод: информация – выбор из двух или более возможностей. Например, когда мы говорим с кем-либо, любое произносимое слово выбирается из словаря. Если бы мы пронумеровали все слова из словаря от 1 до 351 482, то могли бы столь же четко вести беседу, называя номера, а не слова (естественно, обоим собеседникам понадобились бы словари, где все слова пронумерованы одинаково, а также терпение).

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

Жесты «палец вверх» или «палец вниз» содержат по одному биту информации. Еще есть жесты «два пальца вверх» и «два пальца вниз». Два последних жеста нравились ныне покойным кинокритикам Роджеру Эберту и Джину Сискелу, которые таким образом выносили окончательные вердикты по новейшим фильмам. Итак, в данном случае мы следим только за их большими пальцами. Получается четыре возможности, которые можно представить в виде двух битов:

00 = обоим не понравилось;

01 = Сискелу не понравилось, Эберту понравилось;

10 = Сискелу понравилось, Эберту не понравилось;

11 = обоим понравилось.

Первый бит относится к Сискелу; таким образом, 0 означает, что кино не понравилось Сискелу, а 1 – что кино понравилось Сискелу. Аналогично второй бит описывает вкусы Эберта. Итак, если друг спросит, что решили Сискел и Эберт о фильме Impolite Encounter, вы, вместо того чтобы ответить: «С точки зрения Сискела – большой палец вверх, с точки зрения Эберта – большой палец вниз» или «Сискелу понравилось; Эберту – нет», можете просто сказать: «Один ноль». Если друг знает, какой бит относится к Сискелу, а какой – к Эберту, а 1 означает «палец вверх», 0 – «палец вниз», то ваш ответ будет понятен. Просто вы должны знать код.

Можно сразу условиться, что бит 1 означает «палец вниз», а 0 – «палец вверх». Это может показаться нелогичным. Естественно, мы привыкли считать, что 1 означает нечто «утвердительное», а 0 – наоборот. На самом деле такое соответствие произвольное. Требуется всего лишь, чтобы все, кто пользуется кодом, знали значения бита 0 и 1.

Значение конкретного бита или совокупности битов всегда понимается в контексте. Вероятно, смысл желтой ленточки, повязанной на конкретном дубе, понятен лишь тому, кто ее туда повесил, и тому, для кого предназначен этот знак. Достаточно изменить цвет, дерево, дату – и значение исчезнет, останется просто тряпочка. Чтобы извлечь какую-либо полезную информацию из жестикуляции Сискела и Эберта, нужно как минимум понимать, о каком фильме идет речь.

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