Кодирование: сколько бит и байт занимают данные
Есть серийные номера или пароли, каждый символ кодируют одинаковым числом бит. Надо узнать, сколько памяти займёт вся база, или найти алфавит по известной памяти. Всё решается руками, кода здесь нет.
Что проверяет номер
Есть набор возможных значений: символы, номера, цвета. Каждое значение кодируют одинаковым числом бит. Надо найти, сколько памяти займёт запись или вся база.
Сюжет на экзамене почти всегда один: серийные номера, идентификаторы или пароли. Меняется только то, что спрашивают.
Шесть шагов
- Сколько значений N? Нужно наименьшее i, при котором 2i ≥ N. Это число бит на одно значение.
- Сколько значений в одной записи? Бит на запись = число значений × i.
- Переводим биты в байты и округляем вверх: запись хранится целыми байтами.
- Умножаем на число записей.
- Дополнительные данные, одинаковые для каждой записи, прибавляем к байтам.
- Переводим единицы: 1 Кбайт = 1024 байта, 1 Мбайт = 1024 Кбайт.
Степени двойки, которые надо знать:
| Степень | Число | Степень | Число |
|---|---|---|---|
| 2¹ | 2 | 2⁶ | 64 |
| 2² | 4 | 2⁷ | 128 |
| 2³ | 8 | 2⁸ | 256 |
| 2⁴ | 16 | 2⁹ | 512 |
| 2⁵ | 32 | 2¹⁰ | 1024 |
Где и как округлять
| Что считаем | Куда |
|---|---|
| Бит на значение | Всегда вверх |
| Биты записи в байты | Вверх |
| Максимум символов при заданной памяти | Вниз |
Примеры
1. Сколько занимает база
Пароль из 105 символов, в наборе 1510 символов. Записей 16 384. Сколько Кбайт занимают пароли?
- 2¹¹ = 2048 ≥ 1510, значит i = 11 бит.
- 105 · 11 = 1155 бит. 1155 / 8 = 144,4, вверх получаем 145 байт.
- 145 · 16 384 / 1024 = 2320 Кбайт.
2. Дополнительные данные
Код участника: 25 букв из 26-буквенного алфавита. На каждого участника хранят ещё 35 байт других данных. Сколько байт нужно на одного?
- 26 значений это 5 бит, 25 · 5 = 125 бит.
- 125 / 8 = 15,6, вверх получаем 16 байт.
- 16 + 35 = 51 байт.
3. Максимальная длина пароля
На 862 пользователя выделили 276 Кбайт. Алфавит 530 символов. Сколько символов максимум может быть в пароле?
- На одного: 276 · 1024 / 862 = 327,9, вниз получаем 327 байт. Больше выделить нельзя.
- 530 символов это 10 бит, потому что 2¹⁰ = 1024.
- 327 · 8 = 2616 бит. 2616 / 10 = 261,6, вниз получаем 261 символ.
4. Две части в одной записи
Номер состоит из 17 букв из 32 символов и кода региона из 366 вариантов. На человека выделено 50 байт. Сколько осталось под дополнительные данные?
- 32 символа это 5 бит, 17 · 5 = 85 бит.
- 366 вариантов это 9 бит.
- 85 + 9 = 94 бита, вверх получаем 12 байт.
- 50 − 12 = 38 байт.
Пароль из 40 символов, в наборе 100 символов. Паролей 2048. Сколько Кбайт они занимают?
Настоящие задачи: перебор i
Вот какие вопросы встречаются на экзамене:
| Что просят | Как решать |
|---|---|
| Максимальная мощность алфавита при «не более X памяти» | Перебираем i, берём наибольшее подходящее. Ответ 2i |
| Минимальная мощность при «не менее» | Берём наименьшее подходящее i. Ответ 2i−1 + 1 |
| Максимальная или минимальная длина номера | Сначала память на один номер, потом биты, потом длина |
| Составной алфавит | «Десятичные цифры и символы из 120-символьного алфавита» это 10 + 120 = 130 символов |
| Код и порядковый номер в одной записи | Биты на запись = L · i + биты на номер |
| Два типа записей | Считаем байты каждого типа, складываем, ищем i перебором |
| Объём в Мбайт | Байты умножаем на число записей и дважды делим на 1024 |
Таблица перебора
Когда ищем алфавит, выписываем таблицу: i бит, байт на номер, вся память. Смотрим, где ещё влезает.
Пример. Номер из 200 символов, номеров 100 000, памяти не более 25 Мбайт. Какая максимальная мощность алфавита?
| i | Бит на номер | Байт на номер | Всего, Мбайт |
|---|---|---|---|
| 10 | 2000 | 250 | ≈ 23,8, влезает |
| 11 | 2200 | 275 | ≈ 26,2, не влезает |
Значит, i = 10, а максимальная мощность 2¹⁰ = 1024.
Минимальная мощность
Почему при «не менее» ответ не 2i? Пример: номер из 400 символов, на один номер нужно не менее 150 байт. При i = 2 получается 100 байт, мало. При i = 3 получается 150 байт, хватает.
Три бита используются при алфавите от 5 до 8 символов: при 4 символах хватило бы двух бит. Поэтому наименьшая мощность 2² + 1 = 5, а не 8.
Номер из 80 символов, на один номер нужно не менее 50 байт. Какова минимальная мощность алфавита?
Ловушки и домашка
| Ловушка | Как не попасться |
|---|---|
| Минимальная мощность при «не менее» | 2i−1 + 1, а не 2i |
| Мбайт, Гбайт, Кбайт вперемешку | Приводи всё к байтам |
| «Семнадцатеричная» и «шестнадцатеричная» | Читай слово внимательно: 17 цифр или 16 |
| Дробное число байт | Запись всегда занимает целое число байт, округляй вверх |
| Округлили i не вверх | Для N = 1000 нужно 10 бит, а не 9,97 |
| 1000 вместо 1024 | Здесь всегда 1024 |
| «Всего» и «на одного» | Перед ответом перечитай вопрос |
| Бит и байт в конце | Подпиши единицы на каждом шаге |
Домашка
Шесть задач с настоящих экзаменов и из банка ФИПИ. Решай на листочке и вписывай ответ.
Примеры и задачи «Попробуй сам» учебные, в домашке задачи с настоящих экзаменов и из банка ФИПИ.