Алфавит, биты, байты, объём

Откуда берётся размер

В базе лежат пароли. Все одной длины, все из одного набора символов.

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

Четыре шага

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

Второй. Бит на один символ: наименьшее i, при котором 2ⁱ не меньше мощности алфавита. Коротко — ⌈log₂k⌉.

Третий. Умножаем на длину кода и поднимаемся вверх до целого байта.

Четвёртый. Умножаем на количество кодов.

Округляй один раз — весь код. Не каждый символ по отдельности: так выйдет заметно больше, чем на самом деле.

Разбор: пароль из десяти букв

Демоверсия 2018 года. Пароль — 10 символов, в ход идут только прописные латинские буквы, их 26. Нужен объём для 50 пользователей.

Пяти бит на символ хватает: 2⁵ = 32, а букв 26. Четырёх мало: 2⁴ = 16.

Весь пароль — 10 · 5 = 50 бит. Байт целый, поэтому под пароль уходит 7 байт.

Пятьдесят пользователей: 50 · 7 = 350 байт.

Теперь то же самое программой.

Программа печатает:

5
50
7
350

Опасное место

Формулу ⌈log₂k⌉ часто подменяют на int(log₂k) + 1. Она врёт ровно на круглых числах: 2, 16, 256, 512, 65536.

Программа печатает — верное значение, завышенное и снова верное:

8
9
9

Ловушки

• Забыли часть алфавита: строчные буквы, цифры, спецсимволы. Бит на символ вышло меньше.
• Округлили каждый символ до байта. Округляют один раз, весь код.
• Взяли int(log₂k) + 1 и получили лишний бит на круглом числе.
• Ответ просили в Кбайт, а записали байты.