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

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

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

Системы счисления подразделяются на:
 позиционные (, );
 непозиционные;
 смешанные.

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

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

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

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

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

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

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

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

Наиболее известным примером смешанной системы счисления является представление времени в виде количества суток, часов, минут и секунд. При этом величина « дней,  часов,  минут,  секунд» соответствует значению  секунд.

Факториальная система счисления 
В факториальной системе счисления основаниями являются последовательность факториалов , и каждое натуральное число  представляется в виде:

 , где .

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

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

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

Фибоначчиева система счисления основывается на числах Фибоначчи. Каждое натуральное число  в ней представляется в виде:
 , где  — числа Фибоначчи, , при этом в коэффициентах  есть конечное количество единиц и не встречаются две единицы подряд.

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

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

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

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

 , где 

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

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

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором попарно взаимно простых модулей  с произведением  так, что каждому целому числу  из отрезка  ставится в соответствие набор вычетов , где
 
 
 …
 
При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка .

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

Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел, представленных в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям .

Система счисления Штерна-Броко 
Система счисления Штерна-Броко — способ записи положительных рациональных чисел, основанный на дереве Штерна-Броко.

См. также 
 История математики
 Алфавитная запись чисел
 Число
 Счёты
 Логарифмическая система счисления

Примечания

Ссылки 

  
 
 
 Цифры и системы счисления. Онлайн Энциклопедия Кругосвет.
 
 Микушин А. В. Системы счисления. Курс лекций «Цифровые устройства и микропроцессоры»
 Butler J. T., Sasao T. Redundant Multiple-Valued Number Systems В статье рассмотрены системы счисления, использующие цифры больше единицы и допускающие избыточность в представлении чисел