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

В позиционной системе с основанием p число записывается цифрами от 0 до p − 1, а вес цифры зависит от её позиции:

a_k … a_1 a_0 (в системе p) = a_k·p^k + … + a_1·p + a_0

Для оснований больше 10 после цифры 9 используют буквы: A = 10, B = 11, C = 12, D = 13, E = 14, F = 15.

Перевод в десятичную систему

Умножайте каждую цифру на степень основания и складывайте.

• 1011 в двоичной системе: 1·8 + 0·4 + 1·2 + 1 = 11.
• 2A3 в шестнадцатеричной: 2·256 + 10·16 + 3 = 512 + 160 + 3 = 675.

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

Делите число на p с остатком, пока не получите 0. Остатки, прочитанные снизу вверх, и есть запись числа.

Пример: переведём 45 в двоичную систему.

Читаем остатки снизу вверх: 101101. Проверка: 32 + 8 + 4 + 1 = 45.

Двоичная, восьмеричная, шестнадцатеричная

Так как 8 = 2³ и 16 = 2⁴, переводить между ними можно без вычислений — группами цифр.

• В восьмеричную: разбейте двоичную запись справа налево на группы по 3 цифры.
• В шестнадцатеричную: на группы по 4 цифры.

Пример: 1101011 (двоичная) → 001 101 011 → 153 (восьмеричная); и 0110 1011 → 6B (шестнадцатеричная). Все три записи равны числу 107.

Полезные признаки

• Последняя цифра записи числа в системе p — это остаток от деления числа на p.
• Запись оканчивается на 0 тогда и только тогда, когда число делится на p. Оканчивается на два нуля — когда делится на p².
• Число N записывается ровно k цифрами в системе p, если p^(k−1) ≤ N < p^k.
• В двоичной системе число 2ⁿ — это единица и n нулей, а 2ⁿ − 1 — это n единиц.
• Чтобы узнать, сколько раз число делится на 2, посчитайте нули в конце его двоичной записи.

Подбор основания

Задачи вида «в системе с основанием p число 25 записывается как 31» решаются уравнением: 3·p + 1 = 25, откуда p = 8. Всегда проверяйте, что все цифры записи меньше найденного p.

Арифметика в системе с основанием p

Складывайте и вычитайте столбиком, как в десятичной системе, но перенос происходит при достижении p, а не 10.

Пример в пятеричной системе: 34 + 23. Сначала 4 + 3 = 7 = 1·5 + 2, пишем 2 и переносим 1. Затем 3 + 2 + 1 = 6 = 1·5 + 1, пишем 1 и переносим 1. Получаем 112. Проверка: 19 + 13 = 32, и 1·25 + 1·5 + 2 = 32.

Проверка в Python

print(bin(45), oct(45), hex(675))      # 0b101101 0o55 0x2a3
print(int('2A3', 16), int('1011', 2))  # 675 11

def to_base(n, p):
    digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    s = ''
    while n:
        s = digits[n % p] + s
        n //= p
    return s or '0'

print(to_base(45, 2))  # 101101

Если в задаче нужно перебрать много чисел, пишите перебор: to_base(n, p) и проверка условия на строке обычно проще, чем рассуждения.

Типичные ошибки

• Читают остатки сверху вниз вместо снизу вверх.
• Забывают, что цифра не может быть равна или больше основания.
• В группах по 3 или 4 разряда разбивают запись слева, а не справа, и теряют нули.