Как переводить числа между позиционными системами счисления?

В позиционной системе вклад цифры определяется её значением и разрядом. Запись aₙ…a₀ в основании p означает сумму aᵢ · pⁱ, причём каждая цифра меньше p. Эта формула служит и определением, и надёжной проверкой любого алгоритма перевода.

Из основания p в десятичную запись

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

Из десятичной записи в основание p

Целую часть последовательно делят на p, сохраняя остатки. Остатки возникают от младшего разряда к старшему, поэтому результат читают в обратном порядке. Для дробной части выполняют последовательные умножения на p и выписывают получаемые целые части уже в прямом порядке.

Быстрые переходы для степеней двойки

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

Арифметика и признаки

Сложение и умножение выполняются по тем же школьным правилам, только перенос происходит при достижении основания p. Последняя цифра показывает остаток при делении на p; несколько последних цифр — остаток по соответствующей степени основания. Эти свойства помогают решать задачи без полного перевода числа.

Контроль результата

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

Универсальный алгоритм перевода

Для целой части удобно повторять деление на основание и собирать остатки в обратном порядке. Ноль рассматривают отдельно: без этого цикл вернёт пустую строку. Проверка цифры при обратном преобразовании обязательна, иначе запись «19» случайно будет принята для восьмеричной системы.

DIGITS = "0123456789ABCDEF"

def to_base(number: int, base: int) -> str:
    if not 2 <= base <= 16:
        raise ValueError("base must be from 2 to 16")
    if number == 0:
        return "0"
    result: list[str] = []
    while number > 0:
        number, remainder = divmod(number, base)
        result.append(DIGITS[remainder])
    return "".join(reversed(result))

print(to_base(255, 2), to_base(255, 16))

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

Практика: перевод с обратным контролем

Реализуйте также функцию из основания 2…16 в десятичное число по схеме Горнера. Проверьте пары 0, 1, 31, 255 и 1024 для оснований 2, 8 и 16: обратный перевод должен восстановить исходное значение. Добавьте тесты на недопустимое основание и цифру. Затем без программы объясните, почему двоичную запись можно группировать тройками для восьмеричной системы и четвёрками для шестнадцатеричной.