кр гаряев. Чарльз Петцольд - Код_ тайный язык информатики-Манн, Иванов и Фе. Книга принадлежит Контакты владельца Культовая книга талантливого преподавателя стала для многих первым уверенным шагом в программировании
 Скачать 6.11 Mb.
|
|
+ 0 1 2 3 4 5 6 7 8 9 0 0 1 2 3 4 5 6 7 8 9 1 1 2 3 4 5 6 7 8 9 10 2 2 3 4 5 6 7 8 9 10 11 3 3 4 5 6 7 8 9 10 11 12 4 4 5 6 7 8 9 10 11 12 13 Глава 7. Наши десять цифр + 0 1 2 3 4 5 6 7 8 9 5 5 6 7 8 9 10 11 12 13 14 6 6 7 8 9 10 11 12 13 14 15 7 7 8 9 10 11 12 13 14 15 16 8 8 9 10 11 12 13 14 15 16 17 9 9 10 11 12 13 14 15 16 17 18 Найдите в верхнем ряду и в левом столбце два числа, которые хотите сло- жить. Следуйте от них по прямой к центру, пока линии не пересекутся, и по- лучите сумму. Например, 4 плюс 6 равно 10. Аналогично, если требуется перемножить два десятеричных числа, выпол- няется более сложная процедура, которая тем не менее подразделяется на мел- кие этапы, связанные с перемножением однозначных десятеричных чисел. Помните, в начальной школе мы должны были учить и таблицу умножения. × 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 8 9 2 0 2 4 6 8 10 12 14 16 18 3 0 3 6 9 12 15 18 21 24 27 4 0 4 8 12 16 20 24 28 32 36 5 0 5 10 15 20 25 30 35 40 45 6 0 6 12 18 24 30 36 42 48 54 7 0 7 14 21 28 35 42 49 56 63 8 0 8 16 24 32 40 48 56 64 72 9 0 9 18 27 36 45 54 63 72 81 Главная прелесть позиционной нотации не в том, как хорошо она рабо- тает, а в том, как хорошо она применима в системах счисления, основанных не на десятке. Наша система счисления кому-то может показаться неудобной. Например, у большинства героев-мультяшек всего по четыре пальца на руке (или на лапе), поэтому им было бы сподручнее пользоваться системой с осно- ванием 8. Довольно интересно следующее: бóльшая часть правил, известных нам по десятеричной системе, вполне применима и в восьмеричной. 64 Глава 8 Альтернативы десятке Число 10 — исключительно важное для человека. У большинства из нас по де- сять пальцев на руках и на ногах, и мы, конечно, предпочитаем, чтобы и тех, и других было по десять. Поскольку на пальцах удобно считать, человек вы- строил всю систему счисления на основании числа 10. 1 2 3 4 5 10 9 8 7 6 Как упоминалось в предыдущей главе, такая система называется «систе- ма с основанием 10», или «десятеричная». Она кажется нам столь естествен- ной, что поначалу сложно даже найти альтернативу. Действительно, когда ви- дим число 10, нас тянет представить, что оно означает, например, десять уток. 10 = Единственная причина, по которой возникает такая ассоциация, в том, что уток столько же, сколько и пальцев у нас на руках. Если бы у человека было иное количество пальцев, то и считали бы мы по-другому, и число 10 означало бы нечто иное. Например, число 10 может указывать и на такое количество уток. 10 = Глава 8. Альтернативы десятке 65 Или так. 10 = Или даже так. 10 = Как только мы поймем, в каком случае 10 означает двух уток, можно будет приступать к разговору о представлении чисел при работе с переключателями, проводами, лампочками и реле (далее — и с компьютерами). Что, если бы у людей было всего по четыре пальца на руке, как у мультя- шек? Вероятно, нам бы даже не пришло в голову разрабатывать десятеричную систему счисления. Напротив, мы бы считали нормальным, естественным, ра- зумным, неизбежным, неопровержимым и бесспорно верным построить сис- тему счисления с основанием 8. Она называлась бы не десятеричной, а вось- меричной, или системой с основанием 8. Если бы наша система счисления была построена на основании 8, то вот этот символ нам бы не требовался: 9. Покажите этот символ мультяшке, и герой спросит: «Что это? Зачем это нужно?» Если задуматься, то и без этого символа можно обойтись: 8. В десятеричной системе счисления нет специального символа для десят- ки, соответственно в восьмеричной системе счисления его нет для восьмерки. В десятеричной системе счисления мы считаем: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, а потом 10. В восьмеричной системе считаем: 0, 1, 2, 3, 4, 5, 6, 7, а потом что? Цифры кончились. Остается лишь 10, и это правильный ответ. В восьмеричной системе за 7 следует 10. Но в таком случае 10 соответствует не десяти пальцам, которые есть на двух руках у человека. В восьмеричной системе 10 — это ко- личество пальцев у мультяшек. 66 Код 1 2 3 4 10 7 6 5 Давайте считать дальше на четырехпалых ступнях. 11 12 13 14 20 17 16 15 Имея дело с иными системами счисления, кроме десятеричной, можно не путаться, если называть число 10 «один-ноль». Аналогично 13 будет «один- три», а 20 — «два-ноль». Чтобы вообще обойтись без путаницы, можно гово- рить «два-ноль с основанием восемь» или «два-ноль восьмеричных». Даже когда у нас кончатся пальцы на руках и ногах, можно и далее считать в восьмеричной системе. В принципе, процесс не отличается от счета в десяте- ричной, просто мы пропускаем все числа, в которых есть 8 или 9. Естественно, конкретные числа обозначают уже другие величины. 0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 16, 17, 20, 21, 22, 23, 24, 25, 26, 27, 30, 31, 32, 33, 34, 35, 36, 37, 40, 41, 42, 43, 44, 45, 46, 47, 50, 51, 52, 53, 54, 55, 56, 57, 60, 61, 62, 63, 64, 65, 66, 67, 70, 71, 72, 73, 74, 75, 76, 77, 100… Последнее число называется «один-ноль-ноль». Это общее количество паль- цев мультяшки, умноженное само на себя. При записи десятеричных и восьмеричных чисел можно избежать путаницы, записывая все числа с нижними индексами, обозначающими принадлежность Глава 8. Альтернативы десятке 67 к той или иной системе счисления. Нижний индекс ДЕСЯТЬ означает «основа- ние десять», то есть десятеричную систему, а нижний индекс ВОСЕМЬ — «ос- нование восемь», или восьмеричную систему. Итак, Белоснежка повстречала 7 ДЕСЯТЬ , или 7 ВОСЕМЬ , гномов. У мультяшек по 8 ДЕСЯТЬ , или 10 ВОСЕМЬ , пальцев на руке. Бетховен написал 9 ДЕСЯТЬ , или 11 ВОСЕМЬ , симфоний. У человека 10 ДЕСЯТЬ , или 12 ВОСЕМЬ , пальцев на руках. В году 12 ДЕСЯТЬ , или 14 ВОСЕМЬ , месяцев. В двух неделях 14 ДЕСЯТЬ , или 16 ВОСЕМЬ , дней. Паспорт выдают в 16 ДЕСЯТЬ , или 20 ВОСЕМЬ , лет. В сутках 24 ДЕСЯТЬ , или 30 ВОСЕМЬ , часов. В латинице 26 ДЕСЯТЬ , или 32 ВОСЕМЬ , букв. В английской кварте 907 ДЕСЯТЬ , или 1134, граммов. В покерной колоде 52 ДЕСЯТЬ , или 64 ВОСЕМЬ , карт. Самый известный адрес по Сансет-Стрип — 77 ДЕСЯТЬ , или 115 ВОСЕМЬ Длина поля для американского футбола — 91 ДЕСЯТЬ , или 131 ВОСЕМЬ , метров. На старте женского одиночного зачета в Уимблдонском турнире — 128 ДЕСЯТЬ , или 200 ВОСЕМЬ , участниц. Площадь Мемфиса равна 640 ДЕСЯТЬ , или 1000 ВОСЕМЬ , квадратных километров. Обратите внимание: в этом списке есть несколько круглых восьмерич- ных чисел. Круглым называется число, оканчивающееся на один или несколь- ко нулей. Если десятеричное число оканчивается двумя нулями, значит, оно кратно 100 ДЕСЯТЬ , а 100 ДЕСЯТЬ — это 10 ДЕСЯТЬ , умноженное на 10 ДЕСЯТЬ . В восьме- ричной системе два нуля в конце числа означают, что число кратно 100 ВОСЕМЬ , то есть 10 ВОСЕМЬ умножить на 10 ВОСЕМЬ (или 8 ДЕСЯТЬ умножить на 8 ДЕСЯТЬ , что рав- но 64 ДЕСЯТЬ ). Возможно, вы также заметили, что такие круглые восьмеричные чис- ла, как 100 ВОСЕМЬ , 200 ВОСЕМЬ и 400 ВОСЕМЬ , в десятеричной системе соответствуют 64 ДЕСЯТЬ , 128 ДЕСЯТЬ и 256 ДЕСЯТЬ , и все эти десятеричные числа — степени двойки. Это логично. Например, число 400 ВОСЕМЬ , равно 4 ВОСЕМЬ умножить на 10 ВОСЕМЬ и умножить на 10 ВОСЕМЬ , и все это — степени двойки. Всякий раз при умно- жении степени двойки на степень двойки мы получаем еще одну степень двойки. В следующей таблице даны некоторые степени двойки в десятеричном и восьмеричном представлении. 68 Код Степень двойки Десятеричная система Восьмеричная система 2 0 1 1 2 1 2 2 2 2 4 4 2 3 8 10 2 4 16 20 2 5 32 40 2 6 64 100 2 7 128 200 2 8 256 400 2 9 512 1000 2 10 1024 2000 2 11 2048 4000 2 12 4096 10 000 Круглые числа из правого столбца подсказывают, что системы счисле- ния, отличающиеся от десятеричной, удобны для работы с двоичными кодами. Структурно восьмеричная система аналогична десятеричной. Отличия лишь в деталях. Например, каждая позиция в восьмеричном числе — это циф- ра, умноженная на степень восьмерки. Количество единиц Количество восьмерок Количество шестьдесят четверок Количество пятьсот двенадцаток Количество четыре тысячи девяносто шестерок Количество тридцать две тысячи семьсот шестьдесят восьмерок Следовательно, восьмеричное число 3725 ВОСЕМЬ можно разбить: 3725 ВОСЕМЬ = 3000 ВОСЕМЬ + 700 ВОСЕМЬ + 20 ВОСЕМЬ + 5 ВОСЕМЬ Эту последовательность можно переписать несколько иначе. Например, при помощи степеней восьмерки в их десятеричном представлении: 3725 ВОСЕМЬ = 3 × 512 ДЕСЯТЬ + 7 × 64 ДЕСЯТЬ + 2 × 8 ДЕСЯТЬ + 5 × 1. Глава 8. Альтернативы десятке 69 То же самое, записанное при помощи степеней восьмерки в восьмерич- ном представлении: 3725 ВОСЕМЬ = 3 × 1000 ВОСЕМЬ + 7 × 100 ВОСЕМЬ + 2 × 10 ВОСЕМЬ + 5 × 1. А можно сделать вот так: 3725 ВОСЕМЬ = 3 × 8 3 + 7 × 8 2 + 2 × 8 1 + 5 × 8 0 Если выполнить эти расчеты в десятеричной системе, получится 2005 ДЕСЯТЬ Таким образом восьмеричные числа преобразуются в десятеричные. Восьмеричные числа складываются и перемножаются в точности как де- сятеричные. Разница в том, что таблицы умножения и сложения для восьме- ричных чисел строятся иначе. Вот таблица сложения восьмеричных чисел. + 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 10 2 2 3 4 5 6 7 10 11 3 3 4 5 6 7 10 11 12 4 4 5 6 7 10 11 12 13 5 5 6 7 10 11 12 13 14 6 6 7 10 11 12 13 14 15 7 7 10 11 12 13 14 15 16 Например, 5 ВОСЕМЬ + 7 ВОСЕМЬ = 14 ВОСЕМЬ , то есть восьмеричные числа мож- но складывать в столбик. 135 + 643 1000 70 Код Начинаем справа: 5 плюс 3 равно 10, 0 пишем, 1 в уме; 1 плюс 3 плюс 4 равно 10, 0 пишем, 1 в уме; 1 плюс 1 плюс 6 равно 10. Аналогично дважды два и в восьмеричной системе равно четырем. Но триж- ды три не равно девяти. А как? Трижды три равно 11 ВОСЕМЬ , это столько же, сколько и 9 ДЕСЯТЬ . Далее полностью приведена восьмеричная таблица умножения. × 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 2 0 2 4 6 10 12 14 16 3 0 3 6 11 14 17 22 25 4 0 4 10 14 20 24 30 34 5 0 5 12 17 24 31 36 43 6 0 6 14 22 30 36 44 52 7 0 7 16 25 34 43 52 61 Здесь у нас 4 × 6 равно 30 ВОСЕМЬ , но 30 ВОСЕМЬ равно 24 ДЕСЯТЬ , то есть 4 × 6 в десятеричной системе. Восьмеричная система счисления столь же полноценна, как и десятеричная. Мы разработали систему счисления для мультяшек. Теперь давайте со- здадим такую же систему для омаров. У омаров нет пальцев, но на кончиках передних лап у них клешни. Омарам подойдет четверичная система счисления с основанием четыре. 1 2 3 10 Глава 8. Альтернативы десятке 71 Вот как считают в четверичной системе: 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 × 4 4 + 1 × 4 3 + 2 × 4 2 + 3 × 4 1 + 2 × 4 0 72 Код Если мы выполним вычисления в десятичной системе счисления, то об- наружим, что 31 232 ЧЕТЫРЕ — это 878 ДЕСЯТЬ Теперь мы сделаем еще один прыжок, на этот раз окончательный. Пред- ставьте, что мы дельфины и можем использовать для подсчета два плавника. В данном случае мы имеем дело с системой счисления с основанием 2, или дво- ичной, или, иначе, бинарной (от лат. binary — «двойной», «состоящий из двух частей»). Понятно, что у нас будет только две цифры: 0 и 1. С нулем и единицей мало что можно сделать, и, чтобы привыкнуть к дво- ичным числам, требуется практика. Проблема в том, что сразу заканчивают- ся цифры. Например, на следующем рисунке показано, как дельфин считает на плавниках. 1 10 Да, в двоичной системе счисления за 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 ДВА Глава 8. Альтернативы десятке 73 Количество планет в Cолнечной системе, включая Плутон, — 9 ДЕСЯТЬ , или 1001 ДВА Количество центнеров в тонне — 10 ДЕСЯТЬ , или 1010 ДВА В двоичном числе, состоящем из большого количества цифр, позиции знаков соответствуют степени двойки. Количество единиц Количество двоек Количество четверок Количество восьмерок Количество шестнадцаток Количество тридцатидвушек Таким образом, каждый раз, когда встречаем двоичное число, состоящее из единицы и следующих за ней нулей, мы понимаем, что это число соответ- ствует какой-либо из степеней двойки. Эта степень равна количеству нулей в этом двоичном числе. Вот наша расширенная таблица степеней двойки, де- монстрирующая такое правило. Степень двойки Десятичная система Восьмерич- ная система Четверич- ная система Двоичная система 2 0 1 1 1 1 2 1 2 2 2 10 2 2 4 4 10 100 2 3 8 10 20 1000 2 4 16 20 100 10000 2 5 32 40 200 100000 2 6 64 100 1000 1000000 2 7 128 200 2000 10000000 2 8 256 400 10000 100000000 2 9 512 1000 20000 1000000000 2 10 1024 2000 100000 10000000000 2 11 2048 4000 200000 100000000000 2 12 4096 10000 1000000 1000000000000 Допустим, у нас есть двоичное число 101101011010. Его можно записать так: 74 Код 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 × 2 11 + 0 × 2 10 + 1 × 2 9 + 1 × 2 8 + 0 × 2 7 + 1 × 2 6 + 0 × 2 5 + 1 × 2 4 + 1 × 2 3 + 0 × 2 2 + 1 × 2 1 + 0 × 2 0 Если просто сложить все слагаемые в десятичной системе, получим 2048 + 512 + 256 + 64 + 16 + 8 + 2, что составляет 2906 ДЕСЯТЬ Для более легкого преобразования двоичных чисел в десятичные можно использовать следующую схему. × 128 + × 64 × 32 × 16 × 8 × 4 × 2 × 1 + + + + + + = Эта схема позволяет конвертировать числа, содержащие до восьми дво- ичных разрядов; ее можно легко расширить. Введите до восьми цифр в восемь Глава 8. Альтернативы десятке 75 верхних полей, по одной цифре в каждый квадрат. Выполните восемь операций умножения и введите их результаты в восемь нижних полей. Сложите числа в этих восьми полях для получения окончательного результата. Этот пример демонстрирует процесс нахождения десятичного эквивалента двоичного чис- ла 10010110. × 128 + × 64 × 32 × 16 × 8 × 4 × 2 × 1 + + + + + + = 1 0 0 1 0 1 1 0 128 0 0 16 0 4 2 0 150 Преобразовать десятичные числа от 0 до 255 в двоичные не так просто, однако вы можете использовать следующую схему. : 128 : 64 : 32 : 16 : 8 : 4 : 2 : 1 Процесс преобразования сложнее, чем кажется, поэтому внимательно следуйте указаниям. Поместите десятичное число (меньшее или равное 255) в верхний левый квадрат. Разделите это число (делимое) на первый делитель (128), как показано на схеме. Поместите целую часть в нижнее поле (левый нижний квадрат), а остаток от деления — в поле справа (второй квадрат в верхнем ряду). Этот первый остаток является делимым, которое будет уча- ствовать в следующей операции деления, где в качестве делителя использу- ется число 64. Помните, что каждая целая часть будет равна либо 0, либо 1. Если делимое меньше делителя, то целая часть от деления будет равна 0, а остаток — само- му делимому. Если делимое больше или равно делителю, то целая часть от де- ления будет равна 1, а остаток — разности между делимым и делителем. Вот как преобразуется число 150. 150 22 22 22 6 6 2 0 0 0 1 0 1 1 0 1 : 128 : 64 : 32 : 16 : 8 : 4 : 2 : 1 Если вам нужно сложить или перемножить два двоичных числа, вероятно, будет легче выполнить вычисления в двоичной системе, не преобразуя числа в десятичные. Это должно понравиться. Представьте, как быстро вы могли бы освоить сложение, если бы потребовалось запомнить только это. |