Юрий Ревич - Занимательная микроэлектроника

Позиционные и непозиционные системы счисления

Из понятия числа, как объективно существующей абстракции, вытекает, что его материальное представление может быть произвольным, лишь бы оно подчинялось тем же правилам, что и сами числа. Проще всего считать палочками (и в детском саду нас учат именно такому счету), в качестве которых могут выступать и пластмассовые стерженьки, и пальцы, и черточки на бумаге. Один — одна палочка, два — две палочки, десять — десять палочек. А сто палочек? Уже посчитать затруднительно, поэтому придумали сокращение записи: доходим до пяти палочек, ставим галочку, доходим до десяти — ставим крестик:

1 2 5 7 10 11

I II V VII X XI

Узнаете? Конечно, это всем знакомая римская система, сохранившаяся до настоящих времен на циферблатах часов или в нумерации столетий. Она представляет собой пример непозиционной системы счисления, потому что значение определенного символа, обозначающего то или иное число, в ней не зависит от позиции относительно других символов — все значения в записи просто суммируются . Следовательно, записи «XVIII» и «IIIХV» в принципе Должны означать одно и то же. На самом деле это не совсем так: в современной традиции принято в целях сокращения записи учитывать и позицию символа: скажем, в записи «IV» факт, что палочка стоит перед галочкой, а не после нее, означает придание ей отрицательного значения, т. е. в данном случае единица не прибавляется, а вычитается из пяти (то же самое относится и к записи девятки «IX»). Если вы человек наблюдательный, то могли заметить, что на часах четверку пишут почти всегда, как «IIII, а не как «IV», что, несомненно, более отвечает духу непозиционной системы. Однако, при всех возможных отклонениях главным здесь остается факт, что в основе системы лежит операция суммирования .

Большие числа в римской системе записывать трудно. Поэтому были придуманы позиционные системы, к которым, в частности, принадлежала и упомянутая вавилонская шестидесятеричная (см. рис. 7.4).

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

Заметки на полях

В Европе позиционную систему переоткрыл (видимо) Архимед, затем от греков она была воспринята индусами и арабами, и на рубеже I и II тысячелетий н. э. опять попала в Европу [6] Перевод соответствующего трактата арабского ученого аль Хорезми на латынь относится к 1120 году (на самом деле его звали Мухаммед аль Хорезми, т. е. «Муххамед из Хорезма»; между прочим, от его прозвища произошло слово алгоритм). — с тех пор мы называем цифры арабскими, хотя по справедливости их следовало бы назвать индийскими. Это была уже современная десятичная система в том виде, в котором мы ее используем по сей день, у арабов отличается только написание цифр. С тем фактом, что заимствована она именно у арабов, связано не всеми осознаваемое несоответствие порядка записи цифр в числе и привычным нам порядком следования текста: арабы, как известно, пишут справа налево. Поэтому значение цифры в зависимости от позиции ее в записи числа возрастает именно справа налево, что в европейском языке нелогично — приходится заранее обозревать число целиком и готовить ему место в тексте.

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

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

а n р n+ а n-1 р n-1 + … + a 1 р 1+ a 0 p 0. (7.4)

В самой записи числа степени основания подразумеваются, а не пишутся (и для записи основания даже нет специального значка), т. е. запись будет представлять собой просто последовательность а n… а 0(обратим внимание на то, что запись производится справа налево по старшинству — обычная математическая запись выглядела бы наоборот). Отдельные позиции в записи числа называются разрядами.

Заметки на полях

Еще один нюанс, дошедший до нас из древнегреческих времен, связан с тем, что греки и римляне не знали нуля. Именно поэтому первым годом нового века и тысячелетия считается 2001, а не 2000 год — год с двумя нулями относится к предыдущему столетию или тысячелетию — после последнего года до нашей эры (минус первого) идет сразу первый год нашей эры, а не нулевой. Однако именно нулевой логично считать первым, вдумайтесь: ведь когда мы говорим «первые годы XX века», мы имеем в виду именно 1903 или 1905, а не 1913 или 1915. Но древние греки были совсем не такие дураки и ноль игнорировали не по скудоумию. Дело в том, что в последовательности объектов, нумерованных от нуля до, например, девяти, содержится не девять предметов, а десять! Чтобы избежать этой путаницы, в быту обычно нумеруют, начиная с единицы, тогда последний номер будет одновременно означать и количество. В электронике же и в программировании обычно принято нумеровать объекты, начиная с нуля, и всегда следует помнить, что номер и количество различаются на единицу (так, в байте 256 возможных символов, но номер последнего равен 255). На всякий случай всегда следует уточнять, откуда ведется нумерация, иначе можно попасть в неприятную ситуацию (скажем, элементы строки в языке Pascal нумеруются с единицы, а в языке С — с нуля).

В десятичной системе (т. е. в системе с основанием р = 10) полное представление четырехразрядного числа, например, 1024 таково: 1∙10 3+ 0∙10 2+ 2∙10 1+ 4∙10 0.

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

Ну, а как можно представить число в системе счисления с другим основанием? Для любой системы с основанием р нужно не меньше (и не больше) чем р различных цифр — то есть значков для изображения чисел. Для десятичной системы их десять — это и есть известные всем символы от 0 до 9. Выбор начертания этих значков совершенно произволен — так, у арабов и по сей день 1 обозначается, как и у нас, палочкой. А вот цифра 2 обозначается знаком, похожим на латинскую строчную «г», причем тройка тоже имеет похожее начертание, и я плохо себе представляю, как Усама бен Ладен их там отличает. Впрочем, это дело привычки, у нас тоже значки «5» и «6» в некоторых случаях различить непросто, не говоря уж о сходстве между нулем «0» и буквой «О». В ручном написании текстов программ, а также в матричных компьютерных шрифтах, которые были в ходу до появления графического интерфейса, для этого ноль даже изображали перечеркнутым, наподобие знака диаметра: « ». Попробуйте различить записи «150 м» и «150 м», если пробел забыли поставить в нужном месте — в случае матричных шрифтов или ручной записи, да и в любом случае, если символов «0» и «О» рядом не стоит, это неразрешимая задача, если только из контекста не ясно, когда идет речь об омах, а когда — о метрах.