Блог Хеллера's Journal

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

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

После того как мы определили понятие натурального числа, встаёт вопрос о том, как натуральные числа записывать. Пока мы ввели только символы 0, 1, 2, 3 и 4 для нескольких чисел. Мы могли бы продолжить процесс и дальше (пока продолжим этот ряд последовательно символами 5, 6, 7, 8, 9, A), однако довольно быстро возникает проблема: множество бесконечное, и соответственно символов нам потребуется бесконечно много, что, видимо, невозможно. Нам нужен способ, который позволит записывать любое натуральные число используя конечное число символов.

Пусть у нас есть некоторое число , которое надо записать. Выберем некоторое произвольное , которое будем называть основанием нашей системы счисления и поделим одно на другое с остатком:

(1)

Здесь и . Поделим теперь на с остатком значение : и подставим это выражение в (1):

(2)

Аналогично можно представить подставив его в (2), затем , и так далее. Легко увидеть, что последовательность с каждым следующим элементом убывает, и, стало быть, в какой-то момент найдётся такое , что . На этом процесс прекратится и мы получим такое выражение для :

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

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

Рассмотрим пример. Как представить число в двоичной системе? (Напомню, что за мы обозначили число, следующее за числом 9). Проделывая процедуру с делением, описанную в начале параграфа, мы приходим к записи

Здесь . Можно кратко записать это как упорядоченный набор: , или же даже еще короче, опустив скобки и запятые: 1010. Это и есть двоичное представления числа A. Чтобы не путать системы счисления, удобно так же обозначать основание рядом с числом. В нашем случае получится . Впрочем, иногда нам будет удобно пользоваться и записью , так что следует иметь её ввиду, по крайней мере в течение ближайших нескольких параграфов. Количество символов, необходимых для представления числа, мы будем называть разрядностью, а выражение -ым разрядом. Иногда нам будет удобно считать, что число имеет больше разрядов чем необходимо, тогда старшие разряды будут иметь значение 0. Таким образом число можно было бы эквивалентно записать как . Потенциально мы можем считать, что слева в записи числа стоит бесконечное число нулей — это соображение часто упрощает рассуждения и мы будем пользоваться им ниже.

В повседневной жизни чаще всего применяется десятичная система счисления, в которой и помимо 0 и 1 используются так же символы 2, 3, 4, 5, 6, 7, 8, 9. Рассмотрим, для примера, как представить число в десятичной системе счисления. Повторяя еще раз процедуру деления с остатком, получаем:

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

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

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

Причина, по которой программисты любят шестнадцатеричную систему счисления, заключается в том, что она очень легко переводится в двоичную систему счисления и обратно. По сути для этого надо знать лишь представление в двоичной системе 16-ти цифр. Для примера выше мы уже видели, что , так же легко увидеть, что и . Чтобы получить отсюда двоичную запись, достаточно объединить двоичные записи для отдельных шестнадцатеричных цифр:

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

Теорема. Записи в системах счисления с основаниями и связаны следующим образом:

В компьютерной памяти чаще всего двоичные значения 0 и 1 (их называют битами) объединены в группы по восемь бит (число восемь берется из соображений, близких к только что упомянутой теореме). Такая группа бит называется байтом. Во многих системах один байт представляет собой один печатный символ. Если же рассматривать байт как число, что его значения могут варьироваться от 0 до 255 (всего 256 различных значений), и таким образом каждому символу можно сопоставить некоторое числовое значение. Всего у нас может быть максимум 256 символов.

Если рассматривать не один, а сразу последовательность байт, то их можно считать числом, записанном в 256-ричной системе счисления. Это часто применяется в компьютерах для записи больших чисел. Если рассматривать два байта, то их максимальным значением может быть 65535. Если считать за символ не один байт, а два байта, то это значит, что наша система сможет поддерживать 65535 символов, что хватит даже китайцам с несколькими их диалектам, Египтянам, латинянам и евреям. Если нам и этого мало, то можно рассматривать четырехбайные значения. В этом случае мы сможем записать число 4294967295, то есть четыре байта позволяют записывать девятизначные числа и некоторые десятизначные. С точки зрения символов мы сможем уместить сюда не только все распространенные в мире языки, но и все вымершие языки, смайлики, музыкальные обозначения, матемаетические знаки, несколько вариантов древней клинописи и так далее. Если нам и этого не хватит, то можно взять 8-байтные целые, которые позволят работать с 19-значными числами.

Если мы будет рассматривать текст как последовательность символов, то мы так же эту последовательность можем интерпретировать как некоторое большое число. Например, для кодирования английского текста чаще всего применяется стандарт ASCII, устанавливающий какой букве соответствует какое число. Букве F в нём соответствует число 70, а букве o — 111 (ASCII использует только 1 байт для кодирования символов). Как число слово Foo в ASCII можно представить следующим образом:

Подобное отношение к тексту позволяет применять к нему математические функции. Например, многие криптосистемы представляют собой всего лишь некоторые арифметические действия над числами и даже не догадываются о том, что пользователь рассматривает данные как текст. Самым ярким примером является криптосистема RSA, на которой сейчас построена значительная доля всей криптографии, используемой на практике, и которую мы рассмотрим в четвертой главе. Используя действия над числами можно так же сжимать данные, чтобы они занимали меньше места. Этот подход называется арифметическим кодированием и мы так же рассмотрим его в четвертой главе. В четвертом параграфе этой главы мы будем рассматривать математические формулы как обычный текст, который в свою очередь мы будем рассматривать как обычное число. Довольно неожиданным образом это позволит сделать нам фундаментальные выводы относительно всей математики в целом.