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

Системы счисления — самая «сквозная» тема информатики: она появляется в четырёх разных линиях ЕГЭ, и в трёх из них её присутствие неочевидно.

Линия 14 — прямо про них: «значение выражения записали в системе счисления с основанием 9, сколько цифр 8 в записи».

Линия 8 — про слова, но слово из отсортированного алфавита это число в системе с основанием, равным размеру алфавита, и номер слова считается ровно как значение такого числа.

Линия 5 — исполнитель, который приписывает к двоичной записи числа разряды в зависимости от делимости. Без свободного перевода туда-обратно задание не решается.

Линии 7 и 11 — объём данных: там всё меряется степенями двойки, и переводы Кбайт → байт → бит это те же переходы между разрядами.

Поэтому тему стоит освоить до автоматизма: не «уметь перевести с подсказкой», а переводить быстро и в обе стороны, понимая, откуда берётся каждый шаг. В этом уроке — механика переводов с полными трассировками, программные способы и арифметика прямо в двоичной системе.

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

Непозиционная система — та, в которой значение знака не зависит от его места в записи. Пример, который знают все, — римская: в записи XXX каждая X означает ровно десять, где бы она ни стояла.

Правда, и в римской системе есть след позиционности: в IX единица вычитается, а в XI прибавляется. Но «вес» самой буквы при этом не меняется — меняется только знак действия. Настоящая позиционность устроена иначе.

Позиционная система — та, в которой вклад цифры зависит от её позиции. В числе 555 три одинаковые цифры означают пятьсот, пятьдесят и пять.

Почему это важно практически: в непозиционной системе нельзя построить простой алгоритм сложения столбиком. Попробуйте перемножить MCMXLIV на XXVII — и станет понятно, почему европейская математика не двигалась, пока не приняла позиционную запись. Вычисления в римской системе делались не на бумаге, а на счётной доске — абаке.

Исторические системы, о которых полезно знать:

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

Ключевым изобретением здесь был именно ноль как цифра: без знака «в этом разряде пусто» позиционная запись неоднозначна.

Основание системы счисления — количество различных цифр, используемых для записи. В системе с основанием q цифры — это числа от 0 до q − 1. Отсюда сразу два правила проверки:

— в двоичной записи не может быть цифры 2, в восьмеричной — цифры 8; — наибольшая цифра всегда на единицу меньше основания.

Развёрнутая форма — запись числа как суммы произведений цифр на степени основания.

Например, 1011₂ означает 1·2³ + 0·2² + 1·2¹ + 1·2⁰ = 8 + 0 + 2 + 1 = 11₁₀.

А 3A₁₆ означает 3·16¹ + 10·16⁰ = 48 + 10 = 58₁₀. Здесь буква A обозначает десять: в шестнадцатеричной системе цифр шестнадцать, и после 9 идут A, B, C, D, E, F со значениями 10, 11, 12, 13, 14, 15.

Развёрнутая форма — это и есть способ перевода в десятичную систему: разложили и сложили.

Обратный перевод, из десятичной в систему с основанием q, выполняется делением с остатком: число делят на q, записывают остаток, частное снова делят на q, и так до нуля. Остатки, выписанные снизу вверх (от последнего к первому), и дают запись.

• • Переведём 25 в двоичную:
• • 25 : 2 = 12, остаток 1;
• • 12 : 2 = 6, остаток 0;
• • 6 : 2 = 3, остаток 0;
• • 3 : 2 = 1, остаток 1;
• • 1 : 2 = 0, остаток 1.
• • Читаем остатки снизу вверх: 11001₂. Проверка: 16 + 8 + 1 = 25.

Полезные ориентиры, которые экономят время на экзамене. Степени двойки до 2¹⁰ надо знать наизусть: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. Число, равное степени двойки, в двоичной записи выглядит как единица и нули; число вида 2^k − 1 — как k единиц подряд. Эти два факта решают половину задач на двоичную запись без вычислений.

Прямой способ — развёрнутая форма: сложить произведения цифр на веса разрядов. Для 725₈ это 7·64 + 2·8 + 5 = 469.

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

Для 725₈: начинаем с нуля. 0 · 8 + 7 = 7. Затем 7 · 8 + 2 = 58. Затем 58 · 8 + 5 = 469. Тот же ответ, но без возведения в степень и без счёта разрядов — а значит, без самой частой ошибки «перепутал, какой разряд нулевой».

Почему это работает? Раскроем скобки: ((0·8 + 7)·8 + 2)·8 + 5 = 7·8² + 2·8 + 5. Это ровно развёрнутая форма, только вынесены общие множители.

В коде схема Горнера занимает три строки:

n = 0

for c in '725':

n = n * 8 + int(c)

А для оснований до 36 в Python есть готовое средство: int('725', 8) сразу даёт 469, а int('3B', 16) — 59. Второй аргумент — основание. Это самый короткий способ перевода в десятичную, и на экзамене пользоваться им можно и нужно.

В задании 14 и в задачах на исполнителей часто требуется сложить или вычесть числа прямо в p-ичной записи. Правила те же, что в столбик в десятичной, — меняется только момент переноса.

Сложение. Складываем разряды справа налево. Если сумма достигла основания или превысила его, вычитаем основание и переносим единицу в следующий разряд. В двоичной это выглядит совсем просто: 1 + 1 = 10, то есть в разряде ноль, а единица уходит влево.

Вычитание. Если уменьшаемый разряд меньше вычитаемого, занимаем единицу у старшего разряда — она приходит как целое основание. В двоичной 0 − 1 превращается в 10 − 1 = 1 с заёмом.

Умножение на основание — приписывание нуля справа, как умножение на 10 в десятичной. Деление нацело на основание — отбрасывание последней цифры. Отсюда же признак делимости: число делится на p тогда и только тогда, когда его запись оканчивается нулём, и делится на p^k, если на конце k нулей.

Последнее правило регулярно решает задания целиком. «Сколько нулей на конце записи числа 12³⁰ в системе с основанием 6?» — 12 = 6 · 2, значит 12³⁰ = 6³⁰ · 2³⁰, и нулей на конце ровно 30.

Целую часть переводят делением на основание, дробную — умножением. Правила зеркальны, и путать их нельзя: в аналитике линии 14 это отмечено как отдельная ловушка.

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

Переведём 0,375 в двоичную. 0,375 · 2 = 0,75 — целая часть 0. 0,75 · 2 = 1,5 — целая часть 1, остаётся 0,5. 0,5 · 2 = 1,0 — целая часть 1, остаётся 0. Процесс закончился.

Цифры выписываем сверху вниз (в порядке получения, а не наоборот, как для целой части): 0,011₂. Проверка: 0·½ + 1·¼ + 1·⅛ = 0,25 + 0,125 = 0,375 ✔

А теперь переведём 0,2. 0,2 · 2 = 0,4 → 0; 0,4 · 2 = 0,8 → 0; 0,8 · 2 = 1,6 → 1; 0,6 · 2 = 1,2 → 1; 0,2 · 2 = 0,4 → 0 — и мы вернулись к началу. Получилась бесконечная периодическая дробь 0,0011(0011)₂.

Это не любопытный факт, а объяснение вполне практической вещи: именно поэтому 0.1 + 0.2 == 0.3 в Python даёт ложь. Конечная десятичная дробь становится бесконечной двоичной, компьютер хранит её приближённо, и крошечная погрешность вылезает при сравнении. Отсюда правило, важное для линий 26 и 27: дробные числа не сравнивают на равенство, а где можно — переводят данные в целые.

Конечной двоичная запись дроби будет только тогда, когда знаменатель несократимой дроби — степень двойки: ½, ¼, ⅜, 0,375 = ⅜. Для одной пятой такого не бывает.

Позиционная система задаётся одним числом — основанием p. Цифр в ней ровно p, от 0 до p − 1, и значение цифры определяется её позицией: разряд номер k весит p^k, нумерация разрядов идёт справа и с нуля.

Перевод в десятичную — это развёрнутая форма или, короче, схема Горнера: идти по цифрам слева направо, умножая накопленное на основание и прибавляя цифру. В Python это одна строка: int('725', 8).

Перевод из десятичной — деление с остатком до нуля, остатки читаются снизу вверх. В Python — bin, oct, hex или цикл s = str(n % p) + s; n //= p.

Если основания связаны степенью (8 = 2³, 16 = 2⁴), перевод делается группировкой разрядов, и группы отсчитываются от младшего разряда, то есть справа; неполную левую группу дополняют нулями слева.

Арифметика внутри системы работает по школьным правилам столбика: сумму разряда делим на основание, остаток пишем, частное переносим; при вычитании заём приходит как целое основание. Умножение на p — приписать ноль, и отсюда признак: k нулей на конце записи означают делимость на p^k.

Эти механики понадобятся в линиях 14, 8, 5, 7 и 11 — то есть примерно в каждом пятом задании работы.