Системы счисления
Шпаргалка по системам счисления для ЕГЭ и ОГЭ: двоичная, восьмеричная, шестнадцатеричная. Переводы, схема Горнера, арифметика, типичные задания с решениями.
Система счисления — это способ записи чисел с помощью набора символов (цифр). Эта шпаргалка собирает всё, что нужно для ЕГЭ и ОГЭ по информатике: позиционные системы, переводы между основаниями, схему Горнера, деление с остатком, быстрые приёмы 2↔8↔16, двоичную арифметику и разбор типичных заданий с пошаговыми решениями.
Позиционные системы счисления
В позиционной системе вес цифры зависит от её позиции (разряда). Основание системы p — это количество используемых цифр. Любое число можно представить как сумму произведений цифр на степени основания.
Для числа с цифрами a в системе с основанием p:
N = a_n·p^n + a_(n-1)·p^(n-1) + ... + a_1·p^1 + a_0·p^0Например, десятичное число 345 раскладывается так:
345 = 3·10^2 + 4·10^1 + 5·10^0 = 300 + 40 + 5В непозиционных системах (например, римской) значение символа не зависит от позиции — такие системы в заданиях ЕГЭ почти не встречаются, но знать различие полезно.
Основные системы счисления
В информатике чаще всего используют четыре системы. Цифры, превышающие 9, в шестнадцатеричной системе обозначают буквами A–F.
| Система | Основание | Используемые цифры | Где применяется |
|---|---|---|---|
| Двоичная | 2 | 0, 1 | Внутреннее представление в компьютере |
| Восьмеричная | 8 | 0–7 | Компактная запись двоичных кодов |
| Десятичная | 10 | 0–9 | Повседневный счёт |
| Шестнадцатеричная | 16 | 0–9, A–F | Цвета, адреса памяти, байты |
Чтобы указать основание, его пишут нижним индексом: 101 в двоичной — это 1012 = 510. В тексте заданий часто пишут «101 в двоичной системе» или используют запись 101₂.
Таблица соответствия 0–15
Эту таблицу полезно выучить наизусть — она лежит в основе быстрых переводов 2↔8↔16. Обратите внимание: 4 двоичных разряда (тетрада) дают ровно одну шестнадцатеричную цифру, а 3 двоичных разряда (триада) — одну восьмеричную.
| Десятичная | Двоичная (4 бита) | Восьмеричная | Шестнадцатеричная |
|---|---|---|---|
| 0 | 0000 | 0 | 0 |
| 1 | 0001 | 1 | 1 |
| 2 | 0010 | 2 | 2 |
| 3 | 0011 | 3 | 3 |
| 4 | 0100 | 4 | 4 |
| 5 | 0101 | 5 | 5 |
| 6 | 0110 | 6 | 6 |
| 7 | 0111 | 7 | 7 |
| 8 | 1000 | 10 | 8 |
| 9 | 1001 | 11 | 9 |
| 10 | 1010 | 12 | A |
| 11 | 1011 | 13 | B |
| 12 | 1100 | 14 | C |
| 13 | 1101 | 15 | D |
| 14 | 1110 | 16 | E |
| 15 | 1111 | 17 | F |
Перевод в десятичную систему (схема Горнера)
Чтобы перевести число из любой системы в десятичную, нужно умножить каждую цифру на основание в степени её разряда и сложить. Разряды нумеруются справа налево, начиная с 0.
Способ 1: разложение по степеням
Переведём 10112 в десятичную:
1011 = 1·2^3 + 0·2^2 + 1·2^1 + 1·2^0
= 8 + 0 + 2 + 1
= 11Переведём 2A16 в десятичную (помним: A = 10):
2A = 2·16^1 + 10·16^0
= 32 + 10
= 42Способ 2: схема Горнера (быстрее для длинных чисел)
Идём по цифрам слева направо: текущий результат умножаем на основание и прибавляем следующую цифру. Начинаем с 0.
Переведём 1101012 в десятичную по Горнеру:
Начало: r = 0
+1: r = 0·2 + 1 = 1
+1: r = 1·2 + 1 = 3
+0: r = 3·2 + 0 = 6
+1: r = 6·2 + 1 = 13
+0: r = 13·2 + 0 = 26
+1: r = 26·2 + 1 = 53
Ответ: 110101 = 53Схема Горнера удобна тем, что не нужно считать степени — только умножение и сложение в столбик «накопителем».
Перевод из десятичной системы (деление с остатком)
Чтобы перевести десятичное число в систему с основанием p, нужно делить число на p с остатком, записывая остатки. Затем остатки читают снизу вверх (от последнего к первому).
Пример: 53 в двоичную
53 : 2 = 26, остаток 1
26 : 2 = 13, остаток 0
13 : 2 = 6, остаток 1
6 : 2 = 3, остаток 0
3 : 2 = 1, остаток 1
1 : 2 = 0, остаток 1
Читаем остатки снизу вверх: 110101
Ответ: 53 = 110101Пример: 100 в шестнадцатеричную
100 : 16 = 6, остаток 4
6 : 16 = 0, остаток 6
Читаем снизу вверх: 64
Ответ: 100 = 64Пример: 250 в восьмеричную
250 : 8 = 31, остаток 2
31 : 8 = 3, остаток 7
3 : 8 = 0, остаток 3
Читаем снизу вверх: 372
Ответ: 250 = 372Если остаток больше 9 (при переводе в 16-ричную), не забудьте заменить его буквой: 10→A, 11→B, …, 15→F.
Быстрый перевод 2 ↔ 8 ↔ 16
Это самый частый приём на ЕГЭ. Поскольку 8 = 2³ и 16 = 2⁴, перевод выполняется группировкой двоичных цифр без промежуточного перехода в десятичную.
Двоичная → восьмеричная (триады)
Разбиваем двоичное число на группы по 3 цифры справа налево, недостающие слева дополняем нулями, каждую триаду заменяем восьмеричной цифрой.
10110101
Группируем по 3 справа: 10 110 101
Дополняем слева нулями: 010 110 101
По таблице: 2 6 5
Ответ: 10110101 = 265Двоичная → шестнадцатеричная (тетрады)
Разбиваем на группы по 4 цифры справа налево, каждую тетраду заменяем шестнадцатеричной цифрой.
10110101
Группируем по 4 справа: 1011 0101
По таблице: B 5
Ответ: 10110101 = B5Обратно: 8 → 2 и 16 → 2
Каждую восьмеричную цифру заменяем триадой, каждую шестнадцатеричную — тетрадой (с ведущими нулями).
7 5 3 (восьмеричное)
7 → 111, 5 → 101, 3 → 011
Ответ: 753 = 111101011
3 F (шестнадцатеричное)
3 → 0011, F → 1111
Ответ: 3F = 00111111 = 111111Через двоичную: 8 ↔ 16
Прямого правила между 8 и 16 нет — переводят через двоичную: восьмеричное → двоичное (триады) → шестнадцатеричное (тетрады).
Арифметика в двоичной системе
Действия выполняются по тем же правилам столбика, что и в десятичной, но перенос/заём происходит при значении 2, а не 10.
Сложение
Таблица сложения битов: 0+0=0, 0+1=1, 1+0=1, 1+1=10 (ноль, единица в перенос).
1011 (11)
+ 0110 (6)
------
10001 (17)
Поразрядно справа налево:
1+0=1
1+1=10 -> пишем 0, в перенос 1
0+1+1=10 -> пишем 0, в перенос 1
1+0+1=10 -> пишем 0, в перенос 1
перенос 1 -> старший разряд 1Вычитание
При нехватке занимаем единицу из старшего разряда (она равна двум в текущем).
1101 (13)
- 0111 (7)
------
0110 (6)Умножение
Умножение в двоичной — это сдвиги и сложения: умножать можно только на 0 или 1.
101 (5)
× 11 (3)
-----
101
+ 101 (сдвиг на 1 разряд влево)
-----
1111 (15)Полезно помнить: умножение на 2 (102) = приписать ноль справа (сдвиг влево), деление на 2 = отбросить младший разряд (сдвиг вправо).
Типичные задания ЕГЭ и ОГЭ
Сколько единиц в двоичной записи числа
Задача. Сколько значащих единиц в двоичной записи числа 195?
195 : 2 = 97, ост. 1
97 : 2 = 48, ост. 1
48 : 2 = 24, ост. 0
24 : 2 = 12, ост. 0
12 : 2 = 6, ост. 0
6 : 2 = 3, ост. 0
3 : 2 = 1, ост. 1
1 : 2 = 0, ост. 1
195 = 11000011
Единиц: 4Подсказка для проверки: 195 = 128 + 64 + 2 + 1 = 2⁷ + 2⁶ + 2¹ + 2⁰ — четыре слагаемых, значит четыре единицы.
Найти основание системы по уравнению
Задача. В системе счисления с основанием p запись числа 21p равна 1310. Найдите p.
21 в основании p = 2·p + 1
Уравнение: 2·p + 1 = 13
2·p = 12
p = 6
Ответ: основание 6Задача. Решите уравнение 13x + 12x = 31x (все числа в системе с основанием x).
13 = 1·x + 3
12 = 1·x + 2
31 = 3·x + 1
Уравнение: (x+3) + (x+2) = 3x + 1
2x + 5 = 3x + 1
x = 4
Проверка: цифра 3 < 4 — корректно.
Ответ: x = 4Сравнение чисел в разных системах
Задача. Что больше: 1A16 или 358? Переведём оба в десятичную.
1A(16) = 1·16 + 10 = 26
35(8) = 3·8 + 5 = 29
29 > 26, значит 35(8) большеКоличество чисел в диапазоне с заданным числом единиц
Задача. Сколько существует трёхзначных двоичных чисел? Старший разряд не может быть нулём, поэтому он зафиксирован как 1, а два оставшихся — любые: 2² = 4 числа (100, 101, 110, 111).
Признаки делимости в разных основаниях
Признаки делимости тоже зависят от основания. Общая идея: число делится на делитель основания (или на само основание) по последним цифрам.
| Система | Признак | Пояснение |
|---|---|---|
| Двоичная | Чётность — по последней цифре | Оканчивается на 0 → делится на 2; на 00 → на 4; на 000 → на 8 |
| Восьмеричная | Делимость на 2 и 4 — по последней цифре | Последняя цифра делится на 2 → число чётное; основание 8 = 2³ |
| Шестнадцатеричная | Делимость на 2, 4, 8 — по последней цифре | Основание 16 = 2⁴, последняя цифра содержит делимость на степени двойки |
| Десятичная | На 5 и 10 — по последней цифре; на 3 и 9 — по сумме цифр | Классические признаки |
Общее правило. Число в системе с основанием p делится на любой делитель p тогда и только тогда, когда на этот делитель делится его последняя цифра. Например, в десятичной системе (p = 10, делители 2 и 5) чётность и делимость на 5 проверяются по последней цифре.
Признак, аналог «суммы цифр». Число делится на (p − 1) тогда и только тогда, когда на (p − 1) делится сумма его цифр. В десятичной это известный признак делимости на 9. В шестнадцатеричной — это признак делимости на 15, в восьмеричной — на 7.
Системы счисления в Python
Python умеет переводить числа между системами встроенными функциями. Они часто помогают быстро проверить ответ.
Из десятичной в другие: bin(), oct(), hex()
bin(53) # '0b110101' — двоичная (префикс 0b)
oct(250) # '0o372' — восьмеричная (префикс 0o)
hex(100) # '0x64' — шестнадцатеричная (префикс 0x)
# Убрать префикс можно срезом [2:]:
bin(53)[2:] # '110101'
hex(255)[2:] # 'ff'Из любой системы в десятичную: int(x, base)
Функция int(строка, основание) переводит запись числа из указанной системы в десятичную.
int('110101', 2) # 53 — из двоичной
int('372', 8) # 250 — из восьмеричной
int('64', 16) # 100 — из шестнадцатеричной
int('2A', 16) # 42 — буквы можно в любом регистре
int('0b110101', 2) # 53 — префикс тоже допускается
# base=0 определит систему по префиксу автоматически:
int('0xFF', 0) # 255
int('0o17', 0) # 15Подсчёт единиц в двоичной записи
n = 195
ones = bin(n).count('1') # 4 — считаем единицы в строке
print(ones) # 4
# В Python 3.10+ есть готовый метод:
(195).bit_count() # 4Форматирование с ведущими нулями
format(5, '08b') # '00000101' — 8 двоичных разрядов
format(255, '04x') # '00ff' — 4 шестнадцатеричных разряда
f'{10:b}' # '1010' — через f-строкуСовет для ЕГЭ: на экзамене калькулятором и Python пользоваться нельзя, но дома эти функции — отличный способ проверить решение, выполненное вручную.
