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

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

Содержание

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

В позиционных системах счисления величина, обозначаемая цифрой в записи числа, зависит от её положения в числе (позиции). Количество используемых цифр называется основанием системы счисления.

Определение

b-ричная система счисления определяется натуральным числом b > 1, называемым основанием системы счисления. Для представления числа x в b-ричной системе счисления его представляют в виде линейной комбинации степеней числа b:

x = \sum_{k=0}^n a_k b^k, где ak — целые, 0 \leq a_k < b.

Примеры

Наиболее распространена индо–арабская десятичная система счисления с основанием b = 10. Индийцы первыми использовали ноль для указания позиционной значимости величины в строке цифр.

Например, число 103 записывается именно как «103» в десятичной системе счисления, так как

103 \equiv 0103 \equiv 0 \cdot 10^{3} + 1 \cdot 10^{2} + 0 \cdot 10^{1} + 3 \cdot 10^0.

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

Запись

Для записи чисел системы счисления с основанием до 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 и т. д.

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

12310 — это число 123 в десятичной системе счисления;
11110112 — то же число, но в двоичной системе.

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

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

Свойства

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

  1. Основание системы счисления в ней самой всегда записывается как 10; например, в двоичной системе счисления 10 означает число 2.
  2. Для записи числа x в b-ричной системе счисления требуется [logb(x)] + 1 цифр, где [\cdot]целая часть числа.
  3. Сравнение чисел. Сравним числа 321 и 312. Для этого слева направо сравниваем цифры, стоящия на одних и тех же позициях: 3 = 3 — результат сравнения чисел не определён; 2 > 1 — первое число больше независимо от оставшихся цифр.
  4. Сложение чисел. Сложим 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-2} \cdot b^1 + a_n \cdot b^0,

либо, наконец, в виде схемы Горнера:

((\ldots(a_1 \cdot b + a_2) \cdot b + a_3) \ldots ) \cdot b + a_n.

Например:

1011002 =
= 1 · 25 + 0 · 24 + 1 · 23 + 1 · 22 + 0 · 21 + 0 · 1 =
= 1 · 32 + 0 · 16 + 1 · 8 + 1 · 4 + 0 · 2 + 0 · 1 =
= 32 + 8 + 4 + 0 = 4410

Пример на С выглядит примерно так

void perevod () {
  int num = 18;
  int base = 7;
   char str[5] = "0000";
     int rem, i = 0;

     while (num >= base) {
       rem = num / base;
       str[3 - i++] = '0' + rem;
       num = num % base;
    }

   str[3 - i++] = '0' + num;
   printf("%s\n", str);
}

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

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

Пример:

4410 переведём в двоичную систему
44 делим на 2. частное 22, остаток 0
22 делим на 2. частное 11, остаток 0
11 делим на 2. частное  5, остаток 1
 5 делим на 2. частное  2, остаток 1
 2 делим на 2. частное  1, остаток 0
теперь, записав последнее частное, а за ним цифры всех остатков, получаем число 1011002

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

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

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

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

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

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

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

x = \sum_{k=0}^n a_{k}b_k, где на коэффициенты ak (называемые как и прежде цифрами) накладываются некоторые ограничения.

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

Если bk = bk для некоторого 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, где Fk — числа Фибоначчи, 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.

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

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

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

Каноническим примером фактически непозиционной системы счисления является римская, в которой в качестве цифр используются латинские буквы:
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}).

Перевод чисел из СОК в десятичную систему счисления

Формула перевода имеет вид:

A = a1*B1+a2*B2+…+an*Bn-r*P, где a1, …, an - представление числа А в СОК с основаниями p1, p2, …, pn;

P = p1, p2, …, pn;

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

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

Пример.

А = (2,4,6) в системе с основаниями: p1 = 3, p2 = 5, p3 = 7.

P = p1*p2*p3 = 3*5*7 = 105.

B1 = 105/3*k1 = 35*2 =70;

B2 = 105/5*k1 = 21*1 =21;

B3 = 105/7*k1 = 15*1 =15;

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

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

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
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
0 1 2 3 4 5 6 7 8 9 Home