Система счисления

Шаблон:Системы счисления Систе́ма счисле́ния — символический метод записи чисел, представление чисел с помощью письменных знаков.

Система счисления:

даёт представления множества чисел (целых и/или вещественных);
даёт каждому числу уникальное представление (или, по крайней мере, стандартное представление);
отражает алгебраическую и арифметическую структуру чисел.

Системы счисления подразделяются на:

позиционные;
непозиционные;
смешанные.

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

Шаблон:Main В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен. Изобретение позиционной нумерации, основанной на поместном значении цифр, приписывается шумерам и вавилонянам; развита была такая нумерация индусами и имела неоценимые последствия в истории человеческой цивилизации. К числу таких систем относится современная десятичная система счисления, возникновение которой связано со счётом на пальцах. В средневековой Европе она появилась через итальянских купцов, в свою очередь заимствовавших её у арабов.

Под позиционной системой счисления обычно понимается однородная $b$ -ичная система счисления, которая определяется целым числом $b > 1$ , называемым «основанием» системы счисления. Целое число без знака $x$ в такой $b$ -ичной системе счисления представляется в виде конечной линейной комбинации степеней числа $b$ :

x = \sum_{k = 0}^{n - 1} a_{k} b^{k}

, где

a_{k}

— это целые числа, называемые «цифрами», удовлетворяющие неравенству

0 \leq a_{k} \leq (b - 1)

.

Каждая степень $b^{k}$ в такой записи называется «весовым коэффициентом разряда». Старшинство разрядов и соответствующих им цифр определяется значением показателя $k$ (номером разряда). Обычно в записи ненулевых чисел начальные нули опускаются.

Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число $x$ записывают в виде последовательности его $b$ -ичных цифр, перечисляемых по убыванию старшинства разрядов слева направо:

x = a_{n - 1} a_{n - 2} \dots a_{0} .

Например, число сто три представляется в десятичной системе счисления в виде:

103 = 1 \cdot 1 0^{2} + 0 \cdot 1 0^{1} + 3 \cdot 1 0^{0} .

Наиболее часто употребляемыми в настоящее время однородными позиционными системами являются:

2 — двоичная (в дискретной математике, информатике, программировании);
3 — троичная;
4 — четверичная^[1] (кватричная)^[2];
5 — пятиричная^[3];
8 — восьмеричная;
10 — десятичная (используется повсеместно);
12 — двенадцатеричная (счёт дюжинами);
16 — шестнадцатеричная (используется в программировании, информатике);
20 — двадцатеричная;
60 — шестидесятеричная (единицы измерения времени, измерение углов и, в частности, координат, долготы и широты).

В позиционных системах чем больше основание системы счисления, тем меньшее количество разрядов (то есть записываемых цифр) требуется при записи числа.

Смешанные системы счисления

Смешанная система счисления является обобщением $b$ -ичной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел ${b_{k}}_{k = 0}^{\infty}$ , и каждое число $x$ в ней представляется как линейная комбинация:

x = \sum_{k = 0}^{n - 1} a_{k} b_{k}

, где на коэффициенты

a_{k}

, называемые как и прежде «цифрами», накладываются некоторые ограничения.

Записью числа $x$ в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса $k$ , начиная с первого ненулевого.

В зависимости от вида $b_{k}$ как функции от $k$ смешанные системы счисления могут быть степенными, показательными. Когда $b_{k} = b^{k}$ для некоторого $b$ , смешанная система счисления совпадает с показательной $b$ -ичной системой счисления.

Наиболее известным примером смешанной системы счисления является представление времени в виде количества суток, часов, минут и секунд. При этом величина « $d$ дней, $h$ часов, $m$ минут, $s$ секунд» соответствует значению $d \cdot 24 \cdot 60 \cdot 60 + h \cdot 60 \cdot 60 + m \cdot 60 + s$ секунд.

Факториальная система счисления

В факториальной системе счисления основаниями являются последовательность факториалов $b_{k} = k!$ , и каждое натуральное число $x$ представляется в виде:

x = \sum_{k = 1}^{n} d_{k} k!

, где

0 \leq d_{k} \leq k

.

Факториальная система счисления используется при декодировании перестановок списками инверсий: имея номер перестановки, можно воспроизвести её саму следующим образом: номер перестановки (нумерация начинается с нуля) записывается в факториальной системе счисления, при этом коэффициент при числе $i!$ будет обозначать число инверсий для элемента $i + 1$ в том множестве, в котором производятся перестановки (число элементов меньших $i + 1$ , но стоящих правее его в искомой перестановке).

Пример: рассмотрим множество перестановок из пяти элементов, всего их — 5! = 120 (от перестановки с номером 0 — (1,2,3,4,5) до перестановки с номером 119 — (5,4,3,2,1)), найдём перестановку с номером 100:

100 = 4! \cdot 4 + 3! \cdot 0 + 2! \cdot 2 + 1! \cdot 0 = 96 + 4;

положим $t_{i}$ — коэффициент при числе $i!$ , тогда $t_{4} = 4$ , $t_{3} = 0$ , $t_{2} = 2$ , $t_{1} = 0$ , тогда: число элементов меньших 5, но стоящих правее равно 4; число элементов меньших 4, но стоящих правее равно 0; число элементов меньших 3, но стоящих правее равно 2; число элементов меньших 2, но стоящих правее равно 0 (последний элемент в перестановке «ставится» на единственное оставшееся место) — таким образом, перестановка с номером 100 будет иметь вид: (5,3,1,2,4). Проверка данного метода может быть осуществлена путём непосредственного подсчёта инверсий для каждого элемента перестановки.

Фибоначчиева система счисления

Шаблон:Main Фибоначчиева система счисления основывается на числах Фибоначчи. Каждое натуральное число $n$ в ней представляется в виде:

n = \sum_{k} f_{k} F_{k}

, где

F_{k}

— числа Фибоначчи,

f_{k} \in {0, 1}

, при этом в коэффициентах

f_{k}

есть конечное количество единиц и не встречаются две единицы подряд.

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

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

К наиболее распространённым сегодня непозиционным системам счисления относятся римские цифры.

Биномиальная система счисления

В Шаблон:Не переведено число x представляется в виде суммы биномиальных коэффициентов:

x = \sum_{k = 1}^{n} (\binom{c_{k}}{k})

, где

0 \leq c_{1} < c_{2} < \dots < c_{n} .

При всяком фиксированном значении $n$ каждое натуральное число представляется уникальным образом^[4].

Система остаточных классов (СОК)

Шаблон:Main Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором попарно взаимно простых модулей $(m_{1}, m_{2}, \dots, m_{n})$ с произведением $M = m_{1} \cdot m_{2} \cdot \dots \cdot m_{n}$ так, что каждому целому числу $x$ из отрезка $[0, M - 1]$ ставится в соответствие набор вычетов $(x_{1}, x_{2}, \dots, x_{n})$ , где

x \equiv x_{1} (\mod m_{1});

x \equiv x_{2} (\mod m_{2});

…

x \equiv x_{n} (\mod m_{n}) .

При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка $[0, M - 1]$ .

В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в $[0, M - 1]$ .

Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел, представленных в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям $(m_{1}, m_{1} \cdot m_{2}, \dots, m_{1} \cdot m_{2} \cdot \dots \cdot m_{n - 1})$ .