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

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

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

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

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

Определение

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 - номер разряда, n - число разрядов.

Примеры

Например, число "сто три" представляется в десятичной системе счисления в виде: $$103 = 1 \cdot 10^{2} + 0 \cdot 10^{1} + 3 \cdot 10^{0}.$$

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

Также распространены системы счисления с основаниями:

• 2 — двоичная (в дискретной математике, информатике, программировании)
• 8 — восьмеричная (в программировании)
• 12 — двенадцатеричная (широко использовалась в древности, в некоторых частных областях используется и сейчас)
• 16 — шестнадцатеричная (наиболее распространена в программировании, а также в шрифтах)
• 60 — шестидесятеричная (измерение углов и, в частности, долготы и широты)

Запись

Для записи чисел системы счисления с основанием до 36 включительно в качестве цифр используются арабские цифры (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) и затем буквы латинского алфавита (a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z). При этом, a = 10, b = 11 и т. д., иногда x = 10.

При одновременной работе с несколькими системами счисления для их различения основание системы обычно указывается в виде нижнего индекса, который записывается в десятичной системе: $$123_{10}$$— это число 123 в десятичной системе счисления; $$1111011_2$$— то же число, но в двоичной системе.

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

• в ассемблере и записях общего рода, не привязанных к конкретному языку, буквой h (от hexadecimal) в конце числа (синтаксис Intel);
• в Паскале знаком «$» в начале числа;
• в C и многих других языках комбинацией 0x или 0X (от hexadecimal) в начале.

В некоторых диалектах языка Си по аналогии с «0x» используется префикс «0b» для обозначения двоичных чисел. (Обозначение «0b» не входит в стандарт ANSI C.)

Свойства

Позиционная система счисления обладает рядом важных свойств:

1. Основание системы счисления в ней самой всегда записывается как 10; например, в двоичной системе счисления 10 означает число 2.
2. Для записи числа x в b-ричной системе счисления требуется $[log_b(x)] + 1$ цифр, где $[\cdot]$ — целая часть числа.
3. Сравнение чисел. Сравним числа 321 и 312. Для этого слева направо сравниваем цифры, стоящия на одних и тех же позициях: 3 = 3 — результат сравнения чисел не определён; 2 > 1 — первое число больше независимо от оставшихся цифр.
5. Сложение чисел. Сложим 321 и 312. Для этого справа налево складываем отдельные цифры:

   3 + 3 = 6

   2 + 1 = 3

   1 + 2 = 3, итого 633.

   Таким же образом можно сложить числа произвольной длины.

Переход к другому основанию

Перевод произвольной позиционной системы счисления в десятичную

Если число в b-ричной системе счисления равно $$a_1\;a_2\;a_3 \ldots a_n,$$

то для перевода в десятичную систему вычисляем такую сумму: $$\sum_{i=1}^n a_i\cdot b^{n-i}$$

или, в более наглядном виде: $$a_1\cdot b^{n-1} + a_2 \cdot b^{n-2} + \ldots + a_{n-1} \cdot b^1 + a_n \cdot b^0,$$

либо, наконец, в виде схемы Горнера: $$((\ldots(a_1 \cdot b + a_2) \cdot b + a_3) \ldots ) \cdot b + a_n.$$

Например:

101101₂ =

= 1 · 2⁵ + 0 · 2⁴ + 1 · 2³ + 1 · 2² + 0 · 2¹ + 0 · 1 =

= 1 · 32 + 0 · 16 + 1 · 8 + 1 · 4 + 0 · 2 + 0 · 1 =

= 32 + 8 + 4 + 0 = 44₁₀

Пример на C для перевода 18 в 7-ричную систему выглядит так: (корректно работает до основания 10, дальше появятся «цифры» :;<=>?@012 и т.д.)

void perevod( unsigned int num, unsigned int base )
{
  #define LENGTH ( 8 * sizeof( unsigned int ) ) /* размер с запасом */

  char str[ LENGTH + 1]; /* +1 для символа [[EOS]] */
  char *pstr = str + LENGTH - 1; /* начинаем заполнять цифрами с конца */

  str[ LENGTH ] = '\0'; /* добавляем EOS */

  if( num == 0 ) *pstr = '0'; /* если цикл не будет крутиться */
  else
    do
    {
      *pstr-- = '0' + num % base; /* заполняем цифрами, сдвигаясь влево */
      num /= base;
    }
    while( num > 0 );

  printf( "%s\n", pstr + 1 ); /* печатаем, начиная с 1го ненулевого символа */

  #undef LENGTH /* уже не нужно */
}

void main()
{
  perevod( 18, 7 );
}

Перевод из десятичной в произвольную позиционную систему счисления

Для перевода необходимо делить число с остатком на основание счисления до тех пор, пока частное больше основания счисления.

Пример: $44_{10}$ переведём в двоичную систему

44 делим на 2. частное 22, остаток 0
22 делим на 2. частное 11, остаток 0
11 делим на 2. частное  5, остаток 1
 5 делим на 2. частное  2, остаток 1
 2 делим на 2. частное  1, остаток 0
 1 делим на 2. частное  0, остаток 1
Частное равно нулю, деление закончено. Теперь записав все остатки справа налево получим число \(101100_2\)

Перевод из двоичной в восьмеричную и шестнадцатеричную системы

Для этого типа операций существует упрощенный алгоритм.

Для восьмеричной — разбиваем число на триплеты, преобразуем триплеты по таблице

000 0 100 4
001 1 101 5
010 2 110 6
011 3 111 7

Для шестнадцатеричной — разбиваем на квартеты, преобразуем по таблице

0000 0 0100 4 1000 8 1100 C 
0001 1 0101 5 1001 9 1101 D
0010 2 0110 6 1010 A 1110 E
0011 3 0111 7 1011 B 1111 F

Пример:

преобразуем 1011002
восьмеричная — 101 100 → 548
шестнадцатеричная — 0010 1100 → 2C16

Перевод из восьмеричной и шестнадцатеричной систем в двоичную

Для этого типа операций существует упрощенный алгоритм-перевёртыш.

Для восьмеричной — преобразуем по таблице в триплеты

0 000 4 100
1 001 5 101
2 010 6 110
3 011 7 111

Для шестнадцатеричной — преобразуем по таблице в квартеты

0 0000 4 0100 8 1000 C 1100 
1 0001 5 0101 9 1001 D 1101
2 0010 6 0110 A 1010 E 1110
3 0011 7 0111 B 1011 F 1111

Пример:

преобразуем 
548 → 101 100
2C16 → 0010 1100

См. Таблица порядков двоичных, шестнадцатеричных и десятичных чисел

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

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

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

Рассмотрим пример: число 103,625 можно представить как

$103,625 = 1 \cdot 10^{2} + 0 \cdot 10^{1} + 3 \cdot 10^{0} + 6 \cdot 10^{-1} + 2 \cdot 10^{-2} + 5 \cdot 10^{-3}.$

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

Перевод из произвольной системы счисления в десятичную

Рассмотрим пример перевода двоичного числа 1100,011₂ в десятичное. Целая часть этого числа равна 12 (см. выше), а вот перевод дробной части рассмотрим подробнее:

$0,011 = 0 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3} = 0 + 0,25 + 0,125 = 0,375.$

Итак, число 1100,011₂ = 12,375₁₀.

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

Для удобства перевода, целую и дробную части числа почти всегда переводят по-отдельности, а результат потом суммируют.

Перевод из двоичной системы в 8- и 16-ричную

Перевод дробной части из двоичной системы счисления в системы счисления с основаниями 8 и 16 осуществляется точно также, как и для целых частей числа, за тем лишь исключением, что разбивка на октавы и тетрады идёт вправо от десятичной запятой, недостающие разряды дополняются нулями справа. Например, рассмотренное выше число 1100,011₂ будет выглядеть как 14,3₈ или C,6₁₆.

Перевод из десятичной системы в произвольную

Для перевода дробной части числа в другие системы счисления нужно обратить целую часть в нуль и начать умножение получившегося числа на основание той системы, в которую нужно перевести. Если в результате умножения будут снова появляться целые части, их нужно повторно обращать в нуль, предварительно запомнив (записав) значение получившейся целой части. Операция заканчивается, когда дробная часть полностью обратится в нуль. Ниже приводится пример перевода числа 103,625₁₀ в двоичную систему счисления.

Переводим целую часть по правилам, описанным выше, получаем 10310 = 11001112.
0,625 умножаем на 2. Дробная часть 0,250. Целая часть 1.
0,250 умножаем на 2. Дробная часть 0,500. Целая часть 0.
0,500 умножаем на 2. Дробная часть 0,000. Целая часть 1.
Итак, сверху вниз получаем число 1012
103,62510 = 1100111,1012

Точно также осуществляется перевод в системы счисления с любым основанием.

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

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

Такие системы счисления отличаются от обычных тем, что используют цифры не из множества $(0, \ldots, b-1)$, а из множества $(-\frac{b-1}{2}, -\frac{b-3}{2}, \ldots, \frac{b-1}{2})$. Чтобы цифры были целыми, нужно, чтобы b было нечётным. В симметричных системах счисления не требуется дополнительных обозначений для знака числа. Кроме того, вычисления в симметричных системах удобны тем, что не требуется особых правил округления — оно сводится к простому отбрасыванию лишних разрядов, что резко уменьшает систематические ошибки вычислений.

Чаще всего используется симметричная троичная система счисления с цифрами (-1,0,1). Она применяется в троичной логике и была технически реализована в вычислительной машине «Сетунь».

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

Смешанная система счисления является обобщением $b$-ричной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел $\{b_k\}_{k=0}^{\infty}$ и каждое число $x$ представляется как линейная комбинация: $$x = \sum_{k=0}^n a_{k}b_k,$$ где на коэффициенты $a_{k}$ (называемые как и прежде цифрами) накладываются некоторые ограничения. Записью числа $x$ в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса $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$ секунд.

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

Фибоначчиева система счисления основывается на числах Фибоначчи. $$x = \sum_{k=0}^n f_k F_k,$$ где $F_k$ — числа Фибоначчи, $f_k\in\{0,1\}$, при этом в записи $f_nf_{n-1}\dots f_0$ не встречается две единицы подряд.

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

Представление $$x = \sum_{k=1}^n d_k k!,$$ где $0\leq d_k \leq k$.

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

Представление, использующее биномиальные коэффициенты $$x = \sum_{k=1}^n {c_k\choose k},$$ где $0\leq c_1 < c_2 < \dots < c_n$.

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

Майя использовали 20-ричную систему счисления за одним исключением: во втором разряде было не 20, а 18 ступеней, то есть за числом (17)(19) сразу следовало число (1)(0)(0). Это было сделано для облегчения расчетов календарного цикла, поскольку (1)(0)(0) = 360 примерно равно числу дней в солнечном году.

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

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

Римская система счисления

Каноническим примером фактически непозиционной системы счисления является римская, в которой в качестве цифр используются латинские буквы:
I обозначает 1,
V — 5,
X — 10,
L — 50,
C — 100,
D — 500,
M — 1000

Например, II = 1 + 1 = 2
здесь символ I обозначает 1 независимо от места в числе.

На самом деле, римская система не является полностью непозиционной, так как меньшая цифра, идущая перед большей, вычитается из неё, например:

IV = 4, в то время как:
VI = 6

См. римские цифры.

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

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором взаимно-простых модулей $(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 \pmod{m_1};$$ $$x \equiv x_2 \pmod{m_2};$$

…

$$x \equiv x_n \pmod{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})$.

</script>",">====Перевод чисел<script type="text/javascript" src="http://ru.wikipedia.org/w/index.php?title=MediaWiki:Wikificator.js&action=raw&ctype=text/javascript&dontcountme=s"></script> из СОК в десятичную систему счисления==== Формула перевода имеет вид:

A = a₁*B₁+a₂*B₂+…+a_n*B_n-r*P, где a₁, …, a_n - представление числа А в СОК с основаниями p₁, p₂, …, p_n;

P = p₁, p₂, …, p_n;

r = 0,1,2,… (целые числа), причем r выбирают так, чтобы разность между левой и правой частью выражения была меньше P;

B_i = (P/p_i)*k_i, где k_i = 1, 2, …, p_i, причем k_i выбирается таким, чтобы остаток от деления B_i/p_i был равен 1.

Пример.

А = (2,4,6) в системе с основаниями: p₁ = 3, p₂ = 5, p₃ = 7.

P = p₁*<script type="text/javascript" src="http://ru.wikipedia.org/w/index.php?title=MediaWiki:Wikificator.js&action=raw&ctype=text/javascript&dontcountme=s"></script>p₂*p₃ = 3*5*7 = 105.

B₁ = 105/3*k₁ = 35*2 =70;

B₂ = 105/5*k₁ = 21*1 =21;

B₃ = 105/7*k₁ = 15*1 =15;

A = 2*70+4*21+6*15 - r*105;

A = 314 - r*105 = 104, где r=2.

<script type="text/javascript" src="http://ru.wikipedia.org/w/index.php?title=MediaWiki:Wikificator.js&action=raw&ctype=text/javascript&dontcountme=s"></script>=",">== Ссылки ==

• Л. Н. Беляева., «Системы счисления и признаки делимости».
• С. Б. Гашков. Системы счисления и их применение, Серия "Библиотека «Математическое просвещение»", выпуск 29, 2004. После нажатия на PDF(333Kb) нужно стронуть боковую рамку окна браузера.
• С. В. Фомин, «Системы счисления». «Популярные лекции по математике», выпуск 40, М., «Наука» 1987 г., 48 стр.
• Яглом И., «Системы счисления», Квант, № <script type="text/javascript" src="http://ru.wikipedia.org/w/index.php?title=MediaWiki:Wikificator.js&action=raw&ctype=text/javascript&dontcountme=s"></script>6, 1970.
• Каевченко М. А., курс лекций в СФ МЭИ по дисциплине «Теория автоматов».
• SZTAKI Desktop Grid
• Что такое система счисления?