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

Введение

Пусть \(d\) — целое положительное число, большее единицы.

Позиционной системой счисления с основанием \(d\) (или, как ещё говорят, \(d\)-ичной системой счисления) называется множество \(D\) (которое далее мы будем называть множеством цифр) и преобразование \(v:D\to\mathbb{N}\), сопоставляющее каждой цифре её числовое значение.

При этом \(v\) должно осуществлять биекцию между \(D\) и числами от \(0\) до \(d-1\). Это означает, что каждое число этого промежутка должно соответствовать ровно одной цифре.

Традиционно множество цифр состоит из знаков 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и букв латинского алфавита. Числовые значения «арабских» цифр стандартны. Числовые значения «латинских» цифр начинаются с десяти и идут в том же порядке, в котором идут латинские буквы. То есть, например, числовое значение буквы «z» равно тридцати пяти.

Под записью мы будем понимать преобразование

\[ W(n) = x_{k}x_{k-1} \ldots x_{0} \]

такое, что:

• если \(n=0\), то \(k=0\) и \(v(x_0)=0\)
• если \(n>0\), то \(x_{k}\ne0\) и выполнено равенство

\[ n = v(x_k) d^k + v(x_{k-1}) d^{k-1} + \ldots + v(x_0) d^0 \]

Например, \(W(42)=2a\) для шестнадцатиричной системы счисления (значком «42» на входе \(W\) обозначено число сорок два).

Чтение устроено чуть проще:

\[ R(x_{k}x_{k-1}\ldots x_{0}) = v(x_k) d^k + v(x_{k-1}) d^{k-1} + \ldots + v(x_0) d^0 \]

Нетрудно заметить, что \(R(W(x))=x\) (а вот с другим порядком \(R\) и \(W\) это неверно).

Если одновременно рассматривается несколько систем счисления, то обычно их помечают нижним индексом. Например, \(R_{3}\) — троичное чтение, а \(W_{2}\) — двоичная запись. Переводом из системы счисления с основанием \(a\) в систему счисления с основанием \(b\) называют последовательное применение \(R_{a}\) и \(W_{b}\)

Во избежание путаницы договоримся далее, что последовательности цифр внутри формул, не сопровождённые нижним индексом, в числовом контексте следует воспринимать как числа, десятично считанные с этих последовательностей. Последовательности цифр же, сопровождённые индексом \(d\), в числовом контексте следует воспринимать как числа, считанные \(d\)-ично.

Это означает, что формулу

\[ 27+14_5+1101_2 \]

следует интерпретировать как

\[ R_{10}(27) + R_{5}(14) + R_{2}(1101) \]

что, в свою очередь, равно сумме двадцати семи, девяти и тринадцати.

Считывание числа

Операция считывания достаточно примитивна: чтобы считать число, достаточно вычислить значение многочлена

\[ v(x_{k}) d^k + v(x_{k-1}) d^{k-1} + \ldots + v(x_{0}) d^0 \]

Единственное, о чём стоит напомнить: иногда многочлен проще вычислять при помощи так называемой схемы Горнера

\[ \sum_k x^k c_k = (\ldots((c_n x + c_{n-1}) x + c_{n-2}) x + \ldots) x + c_0 \]

Для тех, кому эта формула кажется нечитаемой, приведём аналогичный код (на языке Python):

def evaluate(p,x):
    n = degree(p)
    
    total = coeff(p,n)
    for i in range(n,0,-1):
        total = current * x + coeff(p,i-1)
    
    return total

Например, \(123_{7}\) можно считать по схеме Горнера так:

\[ 123_{7} = (1\cdot 7 + 2)\cdot 7 + 3 = 63 + 3 = 66 \]

Запись числа

Запись числа — существенно более сложная операция, чем считывание. Мы способны осуществлять десятичную запись без труда только лишь по той причине, что в нашей ментальной модели в силу исторических и культурных причин числа почти отождествлены с их десятичными записями. Запись в системах счисления, отличных от десятичной, для человека без соответствующей привычки на порядок более трудоёмка.

Сейчас мы приведём два эквивалентных способа записи числа. Первый из них вычисляет цифры, начиная с самой младшей, второй — наоборот, начиная с самой старшей.

Способ первый

Пусть \(N = \sum_k d^k v(a_k)\). Требуется найти цифры \(a_i\) (или хотя бы их числовые значения; будем считать операцию восстановления цифры по числовому значению тривиальной).

Младшую цифру легко определить, если заметить, что

\[ v(a_0) = v(a_0)\bmod d = \left(\sum_k d^k v(a_k)\right)\bmod d \]

Правое из этих двух равенств очевидно, а левое следует из неравенств \(0\leqslant v(a_0) < d\).

Вычтя \(v(a_0)\) из левой и правой частей равенства

\[ N = \sum_k d^k v(a_k) \]

и разделив их на \(d\), получаем такую же по виду задачу для числа \((N-v(a_0))/d\).

Пример

Для того, чтобы записать число \(42\) в троичной системе счисления, можно сделать следующее.

Найдём нулевую цифру: \(v(a_0) = 42 \bmod 3 = 0\).

Далее имеем \(v(a_1) + 3v(a_2) + \ldots = (42-0)/3 = 14\).

Найдём первую цифру: \(v(a_1)=14\bmod 3 = 2\).

Далее имеем \(v(a_2) + 3v(a_3) + \ldots = (14-2)/3 = 4\).

Найдём вторую цифру: \(v(a_2)=4\bmod 3 = 1\).

Далее имеем \(v(a_3) = (4-1)/3 = 1\).

То есть \(W_3(42)=1120\).

Способ второй

Старшую цифру числа \(N\) можно найти так: ищем максимальное \(m\), для которого \(d^m\leqslant N\). Далее ищем максимальное \(c\), для которого \(c d^m\leqslant N\). Это \(c\) и будет числовым значением старшей цифры. Осталось таким же образом найти цифры числа \(N-c d^m\).

Пример

Поскольку \(3^3=27\) «умещается» ровно один раз в числе \(42\), старшая троичная цифра этого числа равна 1.

Остаётся \(42-27=15\). \(3^2=9\) «умещается» в \(15\) тоже один раз. Поэтому следующая троичная цифра числа \(42\) тоже равна 1.

Остаётся \(15-9=6\). \(3^1=3\) «умещается» в \(6\) два раза. Поэтому следующая троичная цифра числа \(42\) равна 2.

Остаётся \(0\), в котором \(3^0=1\) умещается ноль раз. Поэтому последняя цифра троичной записи \(42\) равна 0, а вся запись: 1120.

Быстрый перевод

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

Например, восьмеричных цифр столько же, сколько и троек двоичных. Отсюда следует (поймите, почему!), что число можно перевести из восьмеричной в двоичную, просто заменив каждую цифру на тройку двоичных с тем же значением.

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

Например, переведём 12321 из четверичной системы счисления в восьмеричную:

• каждая четверичная цифра соответствует паре двоичных: 0 — паре 00, 1 — паре 01, 2 — паре 10, 3 — паре 11
• значит, \(12321_{4} = 0110111001_{2}\)
• теперь нужно сгруппировать цифры по три (начиная с самой младшей!): 0 110 111 001
• осталось, наконец, записать соответствующие восьмеричные цифры (отбросив ведущий ноль): 671