Основание системы счисления

Основание задаёт алфавит и веса разрядов

Основание системы счисления, оно же радикс, — это конкретное число b, определяющее две вещи сразу. Во-первых, размер алфавита: допустимых цифр ровно b штук, от 0 до b − 1. Во-вторых, шаг между весами соседних разрядов: каждая позиция влево тяжелее предыдущей ровно в b раз. При b = 10 цифр десять, веса 1, 10, 100; при b = 2 цифр две, веса 1, 2, 4, 8.

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

Когда цифр не хватает, алфавит расширяют буквами. В шестнадцатеричной системе значения от 10 до 15 обозначают символами A–F, в тридцатишестеричной задействован весь латинский алфавит. Чтобы читатель понимал, какое основание имелось в виду, запись помечают: индексом справа внизу в математике или префиксом в технике — 0b для двоичной, 0o для восьмеричной, 0x для шестнадцатеричной. Без пометки строка 101 равно допускает чтение как пять, как шестьдесят пять и как сто один.

Как основание влияет на длину записи

Число разрядов для представления величины N равно ⌈log_b(N + 1)⌉ — то есть с ростом основания запись укорачивается, но логарифмически, а не пропорционально. Наглядная таблица для одного байта, где максимум равен 255: двоичная запись занимает 8 символов, восьмеричная 3, десятичная 3, шестнадцатеричная 2.

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

Особый и самый удобный случай — когда одно основание является степенью другого. Тогда перевод сводится к группировке разрядов без всякой арифметики: 16 = 2⁴, поэтому одна шестнадцатеричная цифра соответствует ровно четырём двоичным, и байт всегда записывается двумя символами. По той же причине три байта ровно укладываются в четыре символа алфавита из 64 знаков: 64 = 2⁶, 24 бита делятся на четыре группы по шесть. Этим свойством и живёт кодирование Base64, переносящее двоичные данные через текстовые каналы. Когда основание не является степенью двойки, ровной укладки нет и приходится либо терять биты, либо считать длинную арифметику.

Почему на практике выбирают то или иное основание

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

• 2 — вычислительная техника. Элемент с двумя различимыми состояниями терпит наибольший разброс параметров: чем меньше состояний, тем шире зазор между ними и тем реже помеха превращает одно в другое.
• 16 — человекочитаемое представление двоичных данных: адреса, цвета, хеши, дампы памяти. Компактнее двоичной в четыре раза и переводится в неё без вычислений.
• 10 — идентификаторы, предназначенные для диктовки и ручного набора: товарные номера, счета, телефоны. Алфавит из десяти цифр не даёт путать символы на слух и в рукописи.
• 36 и 62 — короткие ссылки и внутренние идентификаторы: цифры плюс буквы позволяют упаковать миллиарды значений в 5–6 символов адреса.
• 58 — идентификаторы, которые люди копируют глазами: из алфавита исключены 0, O, I и l, чтобы исключить ошибки распознавания похожих начертаний.
• 64 — не система счисления в бытовом смысле, а транспортная кодировка двоичных данных с алфавитом из 64 символов и знаком дополнения.

Ту же логику видно в устройстве двумерных кодов. Цифровой режим QR трактует тройку цифр как число с основанием 10 и укладывает её в 10 бит, потому что 1000 меньше 1024. Буквенно-цифровой режим работает с алфавитом из 45 символов и пакует пару знаков в 11 бит, поскольку 45² = 2025 меньше 2048. Чем меньше основание набора символов, тем плотнее упаковка и тем больше данных влезает в символ заданной версии — прямое влияние на ёмкость QR-кода. Практический вывод: адрес, набранный заглавными буквами и цифрами, помещается в код меньшего размера, чем тот же адрес в смешанном регистре.

Основание и количество информации

Один символ алфавита из b знаков несёт log₂b бит информации при равновероятных значениях. Десятичная цифра — примерно 3,32 бита, шестнадцатеричная — ровно 4, символ из алфавита в 62 знака — около 5,95. Отсюда прямой расчёт для практики: короткий идентификатор длиной 6 символов из алфавита 62 покрывает около 56,8 млрд комбинаций, а тот же идентификатор из одних цифр — только миллион. Строгий разбор меры количества информации даёт термин энтропия информации.

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

Частые вопросы

Чем основание отличается от позиционной системы?

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

Почему компьютеры работают с основанием 2?

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

Почему для дампов выбрали шестнадцатеричную, а не восьмеричную?

Потому что 16 = 2⁴ ровно делит байт пополам: две шестнадцатеричные цифры дают ровно 8 бит. Восьмеричная цифра покрывает 3 бита, и байт в ней занимает 2 целых и 2/3 цифры, из-за чего границы байтов в длинной записи размываются. Восьмеричная система осталась в наследство от машин с 12- и 36-битными словами и до сих пор используется для прав доступа в файловых системах.

Что такое Base58 и зачем он нужен?

Это алфавит из 58 символов, полученный из 62 буквенно-цифровых удалением четырёх легко путаемых начертаний: цифры 0, заглавной O, заглавной I и строчной l. Применяется там, где идентификатор человек читает глазами и переписывает вручную — прежде всего в адресах криптовалют. Плата за читаемость невелика: запись длиннее, чем в Base64, примерно на 4%.

Может ли основание быть равным единице?

Позиционной системы с основанием 1 не существует: алфавит состоял бы из одной цифры 0, а все веса были бы равны единице, и никакое число, кроме нуля, записать не удалось бы. Унарный счёт палочками иногда называют системой с основанием 1, но он непозиционен — значение равно количеству символов, а длина записи растёт линейно, а не логарифмически.