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

Система счисления — способ записывать числа. Мы выбираем:

набор цифр (множество);
правило, как «весит» каждая позиция в записи.

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

Основные системы

Двоичная (2): \(D_2 = \{0, 1\}\).
Восьмеричная (8): \(D_8 = \{0, 1, 2, 3, 4, 5, 6, 7\}\).
Десятичная (10): \(D_{10} = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\).
Шестнадцатеричная (16): \(D_{16} = \{0, 1, \dots, 9, A, B, C, D, E, F\}\).

Основание системы \(b\) — число разных цифр, которые допускаются в записи числа. Множество цифр этой системы:

\[ D_b = \{0, 1, 2, \dots, b-1\}. \]

Поэтому \(|D_b| = b\).

Корректная запись числа в системе с основанием \(b\) — это такая запись, где каждая цифра принадлежит \(D_b\).

Например, \(2 \in D_4\), но \(4 \notin D_4\), значит \((402)_4\) — некорректная запись.

Запись вида \((10110)_2\) читается так: «число \(10110\) в двоичной системе». Нижний индекс показывает основание.

Позиционная запись

Запись числа — это цепочка цифр: порядок важен. Например, \(12\) и \(21\) — разные числа.

Позиционная запись числа \(a_k a_{k-1}\dots a_0\) в системе с основанием \(b\) означает:

\[ (a_k a_{k-1}\dots a_0)_b = a_k b^k + a_{k-1} b^{k-1} + \dots + a_1 b + a_0. \]

Разряды и вес

Каждая позиция соответствует разряду: справа налево это \(b^0, b^1, b^2\) и так далее. Цифра \(a_i\) умножается на вес разряда \(b^i\).

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

\[ 347_{10} = 3\cdot 10^2 + 4\cdot 10^1 + 7\cdot 10^0. \]

А в восьмеричной:

\[ (507)_8 = 5\cdot 8^2 + 0\cdot 8^1 + 7\cdot 8^0. \]

Разряд — позиция цифры в записи числа. Старшие разряды стоят слева, младшие — справа.

Цифры для оснований больше 10

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

Цифра	Значение
A	10
B	11
C	12
D	13
E	14
F	15

Например, \((2F)_{16} = 2\cdot 16 + 15 = 47\).

Заметьте: ведущие нули не меняют значение числа, например \((007)_8 = (7)_8\).

Сколько разных записей?

Если длина записи фиксирована и равна \(k\), то на каждом месте можно выбрать одну из \(b\) цифр. По правилу произведения получаем \(b^k\) разных цепочек.

Если это именно \(k\)-значные числа (первая цифра не ноль), то вариантов \((b-1)\cdot b^{k-1}\).

Пример для двоичной системы:

цепочек длины 3: \(2^3 = 8\) (от \(000\) до \(111\));
трёхзначных чисел: \(1\cdot 2^2 = 4\) (\(100, 101, 110, 111\)).

Задача:

Найдите значение числа \((3042)_5\).

Решение:

\[ (3042)_5 = 3\cdot 5^3 + 0\cdot 5^2 + 4\cdot 5^1 + 2\cdot 5^0 = 3\cdot 125 + 0 + 20 + 2 = 397. \]

Задачи для тренировки

1. Найдите значения чисел:

a) \((10110)_2\)

b) \((735)_8\)

c) \((2A)_{16}\)

Ответ

a) \(22\).

b) \(7\cdot 8^2 + 3\cdot 8 + 5 = 477\).

c) \(2\cdot 16 + 10 = 42\).

2. Запишите множества цифр \(D_b\) для оснований \(2\), \(5\) и \(12\).

Ответ

\(D_2 = \{0, 1\}\).

\(D_5 = \{0, 1, 2, 3, 4\}\).

\(D_{12} = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B\}\).

3. Какие записи корректны для указанного основания?

a) \((2041)_5\)

b) \((402)_4\)

c) \((1201)_2\)

d) \((19F)_{16}\)

e) \((1B7)_{12}\)

Ответ

a) корректна.

b) некорректна (цифра 4 недопустима).

c) некорректна (цифра 2 недопустима).

d) корректна.

e) корректна.

4. Сколько разных цепочек длины 3 можно составить в системе с основанием \(3\)? Сколько среди них трёхзначных чисел?

Ответ

Всего \(3^3 = 27\) цепочек. Трёхзначных чисел: \((3-1)\cdot 3^2 = 18\).