Минимальное число битов для хранения значения

Сколько битов нужно

Часто требуется узнать, сколько битов минимально необходимо, чтобы закодировать заданное количество различных вариантов: символов алфавита, цветов палитры, номеров игроков или клеток поля. Это одна из самых распространённых задач раздела «кодирование информации», и в её основе лежит простая формула N = 2^i, где N — число различных вариантов, а i — число битов на один вариант.

Если число N является точной степенью двойки, число битов находится сразу. Если же N не степень двойки, берут ближайшую большую степень двойки, потому что хранить «дробное» число битов невозможно — ячейка памяти всегда целая.

Правило выбора

Правило. Минимальное число битов i — это наименьшее целое число, при котором выполняется неравенство 2^i ≥ N. Округление всегда идёт вверх: даже если не хватает всего одного варианта, добавляется целый дополнительный бит.

Разбор примера

В алфавите 33 буквы. Сколько битов нужно, чтобы закодировать одну букву равномерным двоичным кодом, при котором все буквы занимают одинаковое число битов?

Решим и обратную задачу: сколько различных вариантов можно закодировать шестью битами? Ответ 2^6 = 64, то есть запас есть — таким кодом можно записать до 64 разных символов, и 33 буквы туда легко помещаются.

Частые ошибки

• Округляют число битов вниз, и тогда вариантов не хватает для всех символов.
• Берут 2^5 = 32 для 33 символов, забывая, что 32 меньше 33.
• Путают, где в формуле число вариантов, а где число битов.
• Пытаются использовать дробное число битов, которого не бывает.

Связь с объёмом сообщения

Эта задача напрямую связана с измерением информации алфавитным подходом. Если каждый символ кодируется i битами, то сообщение из k символов занимает k * i битов. Поэтому, найдя минимальное число битов на символ, мы можем сразу посчитать и общий объём текста. Например, при 6 битах на букву сообщение из 10 букв займёт 10 * 6 = 60 битов.

Полезно помнить и про обычный компьютерный байт: он содержит 8 битов и позволяет закодировать 2^8 = 256 вариантов. Этого хватает для всех букв русского и английского алфавитов, цифр и знаков препинания, поэтому в простых однобайтовых кодировках на каждый символ отводят ровно один байт. Если же символов больше 256, одного байта уже недостаточно, и приходится использовать два байта и более.

Кратко о главном

• Связь числа вариантов и битов задаёт формула N = 2^i.
• Минимальное число битов — наименьшее i, при котором 2^i ≥ N.
• Округление всегда идёт вверх до целого бита.
• Если N — точная степень двойки, i находится напрямую.