Какая задача стоит за вопросом о битах
Бит — это один разряд двоичной системы с двумя возможными значениями. Два бита дают 2² = 4 комбинации, три — 8, десять — 1024. Число комбинаций растёт степенно, а потому обратная задача, то есть поиск длины кода по числу вариантов, решается логарифмом.
Типичные поводы для расчёта: пронумеровать 1000 товаров, закодировать 26 букв алфавита, выделить поле под номер месяца или завести счётчик на заданное число состояний. Во всех случаях нужно наименьшее целое k, при котором 2ᵏ не меньше числа вариантов.
Как логарифм связан с длиной кода
Условие bᵏ ≥ N равносильно неравенству k ≥ log_b N. Раз k должно быть целым, подходит наименьшее целое, которое не меньше логарифма: это и есть округление вверх. Например, log₂ 26 = 4,70, значит для 26 букв хватит пяти бит: 2⁴ = 16 мало, а 2⁵ = 32 уже достаточно.
Логарифм по произвольному основанию выражается через натуральный: log_b N = ln N / ln b. Именно так устроен расчёт, поэтому результат для степеней основания получается целым (например, log₂ 512 = 9), а для остальных чисел — дробным.
Разбор чисел: от тысячи вариантов до границы у степени двойки
Для 1000 вариантов log₂ 1000 = 9,9658, значит нужно 10 бит. Девяти бит мало: 2⁹ = 512, а десятью можно закодировать 1024 значения. Запас в 24 значения — обычная цена фиксированной длины кода.
Наиболее поучительна граница у степени двойки. Для 256 вариантов результат ровно 8 и хватает 8 бит, то есть одного байта. Для 257 вариантов логарифм равен 8,0056, и приходится брать девятый бит, хотя лишний вариант всего один. Поэтому нельзя округлять «по правилам арифметики»: нужно именно вверх.
Другие основания: восьмеричные, десятичные, шестнадцатеричные
Тот же расчёт работает для любой системы счисления с основанием не меньше 2. Для 512 вариантов log₈ 512 = 3: достаточно трёх восьмеричных цифр. Для 65 536 вариантов log₁₆ 65 536 = 4: это четыре шестнадцатеричные цифры, то есть 16 бит.
Десятичный вариант полезен для номеров и кодов, которые читают люди. Для миллиона вариантов нужно ровно 6 десятичных разрядов, потому что номера идут от 000000 до 999999. Если же вариантов на один больше, то есть 1 000 001, логарифм чуть превышает 6 и понадобится седьмая цифра.
Игра «угадай число» как проверка результата
Удобная проверка здравым смыслом — игра в вопросы с ответами «да» и «нет». Каждый ответ делит множество вариантов пополам, поэтому число вопросов для гарантированного угадывания равно ⌈log₂ N⌉. Число от 1 до 1000 угадывается не более чем за 10 вопросов, а от 1 до миллиона — не более чем за 20, ведь log₂ 1 000 000 = 19,93.
Тот же аргумент объясняет, почему лишний вопрос удваивает охват: 20 вопросов различают 1 048 576 вариантов, а 21 вопрос — уже 2 097 152.
Что калькулятор не учитывает
Расчёт даёт минимальную длину кода фиксированной длины для равновероятных вариантов. Если вероятности различаются, коды переменной длины могут оказаться короче в среднем, но это уже область сжатия данных и другая задача.
Не входят в расчёт и служебные разряды: контрольные суммы, признаки начала и конца, запас на будущее расширение. Проектируя реальный формат, добавляйте их отдельно. Из-за представления дробных чисел результат может отличаться от целого в последних знаках; значения вроде 5,9999999 для миллиона в десятичной системе считайте целыми.
Формула расчёта
k = ⌈log_b N⌉ = ⌈ln N / ln b⌉
Проверенные примеры
Сколько бит нужно, чтобы пронумеровать 1000 различных предметов?
log₂ 1000 = 9,9658. Округляем вверх: 10 бит. Проверка: 2⁹ = 512 < 1000 ≤ 1024 = 2¹⁰.
Сколько бит нужно для 256 вариантов и для 257?
log₂ 256 = 8, хватает 8 бит. log₂ 257 = 8,0056, поэтому нужен 9-й бит.
Сколько шестнадцатеричных цифр нужно для 65 536 значений?
log₁₆ 65 536 = 4: четыре цифры, от 0000 до FFFF.
Как пользоваться онлайн-калькулятором
- Введите число различных вариантов N, которые нужно отличать друг от друга.
- Укажите основание системы счисления: 2 для битов, 16 для шестнадцатеричных цифр, 10 для десятичных.
- Нажмите «Вычислить» и получите логарифм log_b N.
- Округлите результат вверх до целого: это число разрядов. Если логарифм целый, округлять не нужно.