кр гаряев. Чарльз Петцольд - Код_ тайный язык информатики-Манн, Иванов и Фе. Книга принадлежит Контакты владельца Культовая книга талантливого преподавателя стала для многих первым уверенным шагом в программировании
 Скачать 6.11 Mb.
|
|
+ 0 1 0 0 1 1 1 10 Давайте с помощью этой таблицы сложим два двоичных числа. 1100101 + 0110110 10011011 Начиная с правого столбца: 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 не влияет на исходное число. × 0 1 0 0 0 1 0 1 Вот процесс умножения числа 13 ДЕСЯТЬ на число 11 ДЕСЯТЬ в двоичной сис- теме счисления. 1101 × 1011 1101 1101 0000 1101 10001111 Результат — 143 ДЕСЯТЬ Глава 8. Альтернативы десятке 77 Люди, работающие с двоичными числами, часто предваряют их нулями, то есть пишут нули слева от первой 1, например 0011 вместо 11. Это совершен- но не влияет на значение, а служит исключительно для красоты. В следующей таблице перечислены первые шестнадцать двоичных чисел и их десятичные эквиваленты. Двоичное число Десятичное число 0000 0 0001 1 0010 2 0011 3 0100 4 0101 5 0110 6 0111 7 1000 8 1001 9 1010 10 1011 11 1100 12 1101 13 1110 14 1111 15 Давайте рассмотрим список двоичных чисел. Обратите внимание на каж- дый из четырех вертикальных столбцов, состоящих из нулей и единиц, и за- метьте, как эти цифры чередуются в столбцах сверху вниз: ȣ в крайнем правом столбце — 0 и 1; ȣ во втором столбце справа — два 0 и две 1; ȣ в следующем столбце — четыре 0 и четыре 1; ȣ в крайнем левом столбце — восемь 0 и восемь 1. В этом есть порядок, не так ли? Действительно, вы можете легко напи- сать следующие шестнадцать двоичных чисел, просто повторив первые шест- надцать и добавив 1 в начале. 78 Код Двоичное число Десятичное число 10000 16 10001 17 10010 18 10011 19 10100 20 10101 21 10110 22 10111 23 11000 24 11001 25 11010 26 11011 27 11100 28 11101 29 11110 30 11111 31 Вот еще один способ смотреть на это: при выполнении подсчета в двоич- ном формате крайняя цифра справа (также называемая младшим разрядом) по- очередно принимает значения 0 и 1. Каждый раз, когда она изменяется с 1 на 0, вторая цифра справа, следующая за младшим разрядом, также изменяется либо с 0 на 1, либо с 1 на 0. Так что каждый раз, когда двоичная цифра изменяется с 1 на 0, следующая за ней цифра также меняется либо с 0 на 1, либо с 1 на 0. При записи больших десятичных чисел мы используем запятые через каждые три знака для облегчения их восприятия*. Например, если вы увиди- те число 12000000, вероятно, придется подсчитать количество цифр, однако, увидев число 12,000,000, вы сразу поймете, что оно означает 12 миллионов. Двоичные числа очень быстро могут стать весьма длинными. На- пример, 12 миллионов в двоичной системе счисления записывается так: 101101110001101100000000. Чтобы такое число было легче восприни- мать, каждые четыре двоичных разряда обычно разделяются пробелами (1011 0111 0001 1011 0000 0000). Далее в этой книге мы рассмотрим более сжа- тый способ записи двоичных чисел. Сведя систему счисления к двоичным цифрам 0 и 1, мы достигли предела. Далее упрощать некуда. Более того, двоичная система соединяет арифметику * Запятая для разделения разрядов числа используется преимущественно в англоязычной нотации; дробная часть числа в таком случае отделяется точкой. В России принято разделять разряды пробелами, а дробную часть отделять запятой. Прим. науч. ред. Глава 8. Альтернативы десятке с электричеством. В предыдущих главах мы рассматривали переключатели, провода, лампочки и реле, и любой из этих объектов может отображать дво- ичные цифры 0 и 1. Провод может представлять собой двоичную цифру. Если по нему идет ток, то двоичная цифра равна 1, если нет — 0. Переключатель может представлять собой двоичную цифру. Если пере- ключатель включен, или замкнут, то двоичная цифра равна 1, если переклю- чатель выключен, или разомкнут, то двоичная цифра — 0. Лампочка может представлять собой двоичную цифру. Если лампочка горит, то двоичная цифра равна 1, если нет — 0. Телеграфное реле может представлять собой двоичную цифру. Если реле замкнуто, то двоичная цифра равна 1, если разомкнуто — 0. Двоичные цифры имеют непосредственное отношение к компьютерам. Примерно в 1948 году американский математик Джон Тьюки (род. 1915)* осознал, что в будущем словосочетание «двоичная цифра» (binary digit), ве- роятно, приобретет гораздо большее значение — по мере распространения компьютеров. Он решил создать новое, более короткое слово, чтобы заменить эти громоздкие пять слогов, и рассматривал такие варианты, как bigit и binit, но остановился на коротком, простом, элегантном и просто замечательном слове bit («бит»). * Вскоре после выхода в свет первого издания этой книги, в том же 2000 году, Джон Тьюки скончался. 80 Глава 9 За битом бит Когда в 1973 году Тони Орландо в своей песне попросил, чтобы любимая «по- вязала желтую ленточку вокруг старого дуба», он не сопроводил свою просьбу ни подробными объяснениями, ни долгими рассуждениями. Никаких «если», «и», «но». Несмотря на сложные чувства и эмоции, сопровождавшие ситуацию, что разворачивалась в реальной жизни и легла в основу песни, мужчине хоте- лось получить простой ответ: «да» или «нет». Он знал, что, если на старом дубе появится желтая ленточка, это будет означать: «Да, хотя ты и наворотил дел и провел три года в тюрьме, я все равно хочу, чтобы ты вернулся и мы жили под одной крышей». А отсутствие желтой ленточки скажет: «Даже не думай здесь останавливаться». Здесь есть две четкие взаимоисключающие альтернативы. Тони Орландо не пел: «Повяжи половину желтой ленточки, если тебе нужно время на размыш- ление» или «Повяжи голубую ленточку, если больше не любишь меня, но по-преж- нему хочешь остаться друзьями». Нет, он все сформулировал очень просто. Не менее информативно, нежели отсутствие или наличие желтой лен- точки (разве что не столь поэтично), сработал бы дорожный знак, поставлен- ный во дворе, например «Путь открыт» или «Въезд запрещен». Или таблич- ка на двери «Закрыто» или «Открыто». Или фонарик на окне — включенный или выключенный. Если вам нужно просто сказать «да» или «нет», то способов хватает. Для этого не надо произносить ни одной фразы, слова, даже буквы. Необходим всего один бит, то есть 0 или 1. Как мы узнали в предыдущих главах, десятеричная система, которой мы пользуемся при подсчете предметов, на самом деле ничем не примечательна. Ясно, что мы пользуемся системой с основанием 10, так как у нас 10 пальцев на руках. Мы могли бы с тем же успехом использовать систему с основанием 8 (будь мы мультяшками), 4 (будь мы омарами) или даже 2 (если бы мы были дельфинами). Однако двоичная система счисления все-таки особенная. Дело в том, что это простейшая возможная система счисления. В двоичной системе всего две Глава 9. За битом бит 81 цифры: 0 и 1. Если нам нужно что-то проще двоичной системы, придется из- бавиться от 1, и останется только 0. Имея всего лишь 0, ничего не сделаешь. Слово «бит» — сокращение от английского выражения binary digit («дво- ичная цифра»). Пожалуй, это одно из симпатичнейших слов в компьютерной терминологии. В английском языке у слова bit есть и общеупотребительное значение — «кусочек, небольшая часть», и это значение нам отлично подходит, поскольку один бит — двоичная цифра, мельчайший фрагмент информации. Иногда, если изобретается новое слово, ему присваивается новое значение. В данном случае все именно так. Слово «бит» — это не только двоичные циф- ры, при помощи которых удобно считать дельфинам. В компьютерную эпоху это слово приобрело значение «мельчайший первичный фрагмент информации». Да, смелое утверждение. Естественно, информация передается не толь- ко при помощи битов. Буквы, слова, азбука Морзе и шрифт Брайля, а также десятеричные цифры тоже переносят информацию. Суть бита заключается в том, что он передает очень мало информации. Один бит — это минимально возможное количество информации. Меньше бита — отсутствие информации. Поскольку бит выражает минимальный возможный объем информации, более сложную информацию можно передать некоторым количеством битов. (Говоря, что бит передает мало информации, я совершенно не имею в виду, что эта информация граничит с бессмыслицей. Желтая ленточка очень важна для тех, кто в ней заинтересован.) «Запомните, дети, — слышал весь мир, // Как в полночь глухую скакал Поль Ревир…» — писал Генри Лонгфелло. Возможно, он исторически недостовер- но описал поступок Поля Ревира, предупредившего американских колонис тов о вторжении британцев, однако эти стихи замечательно демонстрируют, как можно передать важную информацию при помощи битов. Он другу сказал: «Я сигнала жду. Коль ночью из города наступать Начнут британцы, ты дай мне знать, На Северной церкви зажги звезду, — Одну, если сушей, а морем — две» *. Итак, Ревир дал другу два фонаря. Если британцы вторгнутся по суше, друг зажжет на колокольне один, если высадятся с моря — то зажжет оба. Правда, Лонгфелло не дает явного указания на все случаи жизни. Он умал- чивает о третьей возможности, означающей, что британцы пока не вторгаются. * Здесь и далее стихотворение приводится в переводе М. А. Зенкевича. 82 Код Лонгфелло подразумевает, что тогда ни одного фонаря на колокольне гореть не будет. Допустим, два фонаря висят на колокольне всегда. Как правило, они не горят. Значит, британцы пока не наступают. Если зажжен один фонарь, значит, британцы наступают по суше, если горят оба, — высаживаются с моря. или Каждый фонарь — это один бит. Зажженный фонарь равен единичному биту, незажженный — нулевому биту. Тони Орландо показал, что для описа- ния любой из двух возможностей достаточно всего одного бита. Если бы Поль Ревир должен был оповестить людей лишь о том, вторгаются британцы или нет (а не откуда именно), то хватило бы и одного фонаря. Фонарь горел бы в случае нападения и был бы потушен, если бы предстоял еще один спокойный вечер. Глава 9. За битом бит 83 Чтобы описать одну из трех возможностей, требуется два фонаря. При на- личии второго фонаря и двух битов уже можно описать четыре возможности: 00 = британцы пока не наступают; 01 = британцы наступают с суши; 10 = британцы наступают с суши; 11 = британцы наступают с моря. На самом деле Поль Ревир, ограничившись всего тремя возможностями, поступил весьма хитроумно. В телекоммуникационной терминологии можно сказать, что он задействовал избыточность, позволяющую бороться с шумом. Термин «шум» в теории телекоммуникаций означает любые помехи, ослож- няющие передачу информации. Типичный пример шума — помехи на теле- фонной линии. Тем не менее, даже несмотря на помехи, общение по телефону обычно проходит успешно, поскольку устная речь крайне избыточна. Не тре- буется четко слышать каждый слог в каждом слове, чтобы понять, что сказали. В случае с фонарями на колокольне к «шуму» можно отнести такие фак- торы, как темнота и расстояние от Поля Ревира до колокольни, которые мо- гут помешать отличить первый фонарь от второго. Вот важнейший отрывок из стихов Лонгфелло: Вдруг видит — звездой огонек замигал, То дан с колокольни желанный сигнал! В седло он вскочил, сжал повод в ладонь. Под ним захрапел в нетерпенье конь. Второй сигнал! Он коня погнал! Скорее всего, Поль Ревир был не в состоянии определить, какой фонарь зажегся первым. Из этого следует важный вывод: информация — выбор из двух или более возможностей. Например, когда мы говорим с кем-либо, любое произносимое слово выбирается из словаря. Если бы мы пронумеровали все слова из слова- ря от 1 до 351 482, то могли бы столь же четко вести беседу, называя номера, а не слова (естественно, обоим собеседникам понадобились бы словари, где все слова пронумерованы одинаково, а также терпение). Верно и обратное: любую информацию можно свести к выбору между двумя или более возможностями, а сами возможности выразить при помо- щи битов. Излишне говорить, что существует множество таких вариантов че- ловеческой коммуникации, где выбор между конкретными возможностями 84 Код не предоставляется, и такие формы коммуникации также жизненно необхо- димы. Вот почему люди не флиртуют с компьютерами (по крайней мере, хо- чется на это надеяться). Если некоторую информацию невозможно выразить при помощи слов, картинок или звуков, значит, ее нельзя закодировать при помощи битов. Да и не возникает такого желания. Жесты «палец вверх» или «палец вниз» содержат по одному биту ин- формации. Еще есть жесты «два пальца вверх» и «два пальца вниз». Два по- следних жеста нравились ныне покойным кинокритикам Роджеру Эберту и Джину Сискелу, которые таким образом выносили окончательные вердикты по новейшим фильмам. Итак, в данном случае мы следим только за их боль- шими пальцами. Получается четыре возможности, которые можно предста- вить в виде двух битов: 00 = обоим не понравилось; 01 = Сискелу не понравилось, Эберту понравилось; 10 = Сискелу понравилось, Эберту не понравилось; 11 = обоим понравилось. Первый бит относится к Сискелу; таким образом, 0 означает, что кино не понравилось Сискелу, а 1 — что кино понравилось Сискелу. Аналогично вто- рой бит описывает вкусы Эберта. Итак, если друг спросит, что решили Сискел и Эберт о фильме Impolite Encounter, вы, вместо того чтобы ответить: «С точки зрения Сискела — большой палец вверх, с точки зрения Эберта — большой палец вниз» или «Сискелу понравилось; Эберту — нет», можете просто ска- зать: «Один ноль». Если друг знает, какой бит относится к Сискелу, а какой — к Эберту, а 1 означает «палец вверх», 0 — «палец вниз», то ваш ответ будет понятен. Просто вы должны знать код. Можно сразу условиться, что бит 1 означает «палец вниз», а 0 — «палец вверх». Это может показаться нелогичным. Естественно, мы привыкли считать, что 1 означает нечто «утвердительное», а 0 — наоборот. На самом деле такое соответствие произвольное. Требуется всего лишь, чтобы все, кто пользуется кодом, знали значения бита 0 и 1. Значение конкретного бита или совокупности битов всегда понимается в контексте. Вероятно, смысл желтой ленточки, повязанной на конкретном дубе, понятен лишь тому, кто ее туда повесил, и тому, для кого предназна- чен этот знак. Достаточно изменить цвет, дерево, дату — и значение исчезнет, останется просто тряпочка. Чтобы извлечь какую-либо полезную информа- цию из жестикуляции Сискела и Эберта, нужно как минимум понимать, о ка- ком фильме идет речь. Глава 9. За битом бит 85 Если вы вели список фильмов, отрецензированных Сискелом и Эбертом, и фиксировали их голоса, можно добавить в систему еще один бит, который будет выражать ваше мнение. В таком случае количество возможностей дохо- дит до восьми: 000 = Сискелу не понравилось; Эберту не понравилось; мне не понравилось; 001 = Сискелу не понравилось; Эберту не понравилось; мне понравилось; 010 = Сискелу не понравилось; Эберту понравилось; мне не понравилось; 011 = Сискелу не понравилось; Эберту понравилось; мне понравилось; 100 = Сискелу понравилось; Эберту не понравилось; мне не понравилось; 101 = Сискелу понравилось; Эберту не понравилось; мне понравилось; 110 = Сискелу понравилось; Эберту понравилось; мне не понравилось; 111 = Сискелу понравилось; Эберту понравилось; мне понравилось. Один из плюсов при представлении этой информации в виде битов таков: мы уверены, что учли все возможности, мы знаем, что существу- ет восемь и только восемь возможностей — ни больше, ни меньше. Имея три бита, можно сосчитать лишь от нуля до семи. Трехзначных двоичных чисел больше нет. Итак, при описании таких битов Сискела и Эберта вас, возможно, уже занимает следующий непростой вопрос: «А что насчет сборника рецензий Leonard Maltin’s Movie & Video Guide?» Ведь Леонард Малтин оценивает филь- мы не такими «пальцевыми» жестами, а более традиционно — при помощи системы звезд. Чтобы определить, сколько битов Малтина требуется, сперва необходимо разобраться в его системе. Малтин оценивает фильм в некоторое количество звезд (от одной до четырех), причем звезда может делиться и пополам. (Кста- ти, одну звезду Мартин никогда не присваивает; вместо этого такой фильм по- лучает рейтинг КРАХ.) Вот семь возможностей, и это означает, что для пред- ставления любой оценки достаточно трех бит: 000 = КРАХ; 001 = ; 010 = ; 011 = ; 100 = ; 101 = ; 110 = . 86 Код «Что же насчет 111?» — могли бы спросить вы. Да, этот код ничего не зна- чит. Он не определен. Если бы мы использовали двоичный код 111 в рейтингах Малтина, это бы свидетельствовало об ошибке. (Вероятно, ошибся компьютер, ведь люди никогда не ошибаются!) Напомню, что, когда мы представляли оценки Сискела и Эберта при по- мощи двух битов, левый бит относился к Сискелу, правый — к Эберту. Есть ли в данном случае какое-либо значение у отдельных битов? Да, в некотором роде. Если взять числовое значение такого битового кода, прибавить к нему 2, а за- тем разделить результат на 2, то получится количество звезд. Это возможно лишь потому, что мы определяли коды продуманно и непротиворечиво. Мы вполне могли определить коды и так: 000 = ; 001 = ; 010 = ; 011 = ; 101 = ; 110 = ; 111 = КРАХ. Этот код столь же адекватен, как и предыдущий, если всем понятно его значение. Если бы Малтину попался фильм, не заслуживающий даже единствен- ной звезды, он мог бы присвоить ему рейтинг в половину звезды. Определен- но, кодов на это ему бы хватило. В таком случае коды следовало бы перерас- пределить так: 000 = БОЛЬШОЙ КРАХ; 001 = КРАХ; 010 = ; 011 = ; 100 = ; 101 = ; 110 = ; 111 = . Однако если бы затем нашелся такой провальный фильм, который даже половины звезды не заслуживает (МЕГАКРАХ?), то понадобился бы еще один бит: 3-битных кодов больше не осталось. Глава 9. За битом бит 87 В журнале Entertainment Weekly оцениваются не только фильмы, но и те- лешоу, CD, книги, сайты. Оценки варьируются от A+ до F (правда, есть ощу- щение, что такой чести удостаиваются лишь фильмы Поли Шора). Если под- считать все возможные оценки, их наберется тринадцать. Для представления этой системы понадобится четыре бита: 0000 = F; 0001 = D–; 0010 = D; 0011 = D+; 0100 = C–; 0101 = С; 0110 = C+; 0111 = B–; 1000 = B; 1001 = B+; 1010 = A–; 1011 = A; 1100 = A+. У нас осталось три неиспользованных кода: 1101, 1110 и 1111, а всего их шестнадцать. Рассуждая о битах, мы часто говорим о конкретном числе битов. Чем боль- ше битов у нас в распоряжении, тем больше возможностей удается с их по- мощью описать. Естественно, с десятеричными числами складывается точно такая же си- туация. Например, сколько всего региональных телефонных кодов? Региональ- ный телефонный код в США состоит из трех цифр. Если все эти коды будут задействованы (на самом деле пока не все, но мы это проигнорируем), полу- чится 10 3 , или 1000 таких кодов, — от 000 до 999. Сколько семизначных теле- фонных кодов может быть в зоне действия регионального кода 212? 10 7 , или 10 000 000. Сколько телефонных номеров может быть в зоне действия регио- нального кода 212, причем с префиксом 260? 10 4 , или 10 000. Аналогично в двоичной системе количество возможных кодов всегда рав- но двойке в некоторой степени, где степень — количество битов. |