О двоичной и других системах счисления

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

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

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

Десятичная система

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

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

Узнаете? Конечно, это всем знакомая римская система, сохранившаяся до настоящих времен на циферблатах часов или в нумерации столетий. Она представляет собой пример непозиционной системы счисления – потому что значение определенного символа, обозначающего то или иное число, в ней не зависит от позиции относительно других символов – все значения в записи просто суммируются. То есть записи «XVIII» и «IIIXV» в принципе должны означать одно и то же. На самом деле это не совсем так – в современной традиции принято в целях сокращения записи использовать и позицию: скажем, в записи «IV» факт, что палочка стоит перед галочкой, а не после нее, означает придание ей отрицательного значения, т. е. в данном случае единица не прибавляется, а вычитается из пяти (то же самое относится и к записи девятки «IX»). Если вы человек наблюдательный, то могли заметить, что на часах четверку часто обозначают как «ИИ», а не как «IV» (см. рис. 14.5), что, несомненно, более отвечает духу непозиционной системы. Однако при всех возможных отклонениях главным здесь остается факт, что в основе системы лежит операция суммирования .

Рис. 14.5. Циферблат часов с римскими числами

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

* * *

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

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

* * *

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

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

а_n ·р ⁿ + a_n‑1 ·p^n‑1 +… + a₁ ·p¹ + a₀ ·p⁰ . (4)

В самой записи числа степени основания подразумеваются, а не пишутся (и для записи основания даже нет специального значка), поэтому запись будет представлять собой просто последовательность а_n … а ₀ (еще раз обратим внимание на то, что запись производится справа налево по старшинству, – обычная математическая запись выглядела бы наоборот). Отдельные позиции в записи числа называются разрядами. Например, в десятичной системе (т. е. в системе с основанием 10) полное представление четырехразрядного числа 1024 таково:

1·10³ + 0·10²+ 2·10¹ + 4·10⁰

Ну а как можно представить число в системе счисления с другим основанием? Для любой системы с основанием р нужно ровно р различных цифр – т. е. значков для изображения чисел. Для десятичной системы их десять – это и есть известные всем символы от 0 до 9. Заметим, что выбор начертания этих значков совершенно произволен – так, у арабов и по сей день 1 обозначается, как и у нас, вертикальной палочкой, а вот цифра 2 – знаком

, похожим на латинскую строчную «r ».

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