Целочисленное деление, остаток и округление

Два деления, два правила

1. Сколько байт нужно, чтобы вместить 100 бит?
Округление: всегда вверх (до целого).

• 1 байт = 8 бит.
• Делим: 100 / 8 = 12,5.
• 12 байт вместят только 12 × 8 = 96 бит.
• Значит, нужно 13 байт.

Правило: ищем минимальный контейнер, который гарантированно вместит данные.
Формула: ceil(100 / 8) = 13

2. Сколько записей по 100 бит поместится в килобайт?
Округление: всегда вниз (до целого).

• 1 Кбайт = 1024 байта = 8192 бита.
• Делим: 8192 / 100 = 81,92.
• 82 записи потребовали бы 8200 бит, а у нас только 8192.
• Поместится 81 запись.

Правило: ищем максимальное количество целых объектов, которые можно упаковать.
Формула: floor(8192 / 100) = 81

Золотое правило

Что мы ищем: тару под содержимое или содержимое в тару?

Формулы 

• Биты → байты (вверх):
  Nбайт = ⌈ Nбит / 8 ⌉
• Записи в объём (вниз):
  Nзаписей = ⌊ Vбит / Sзаписи ⌋

Короткая памятка:

• Биты → Байты: всегда с запасом. Округление вверх.
• Записи → Объём: бери сколько влезет. Округление вниз.

Частное, остаток и округление вверх

Два оператора

a // b — сколько целых b помещается в a. a % b — что осталось.

Они связаны: a = b · (a // b) + a % b.

Откуда берётся поправка

Деление вниз даёт k = a // b. Если остаток нулевой — это и есть ответ. Если остаток есть — нужно k + 1.

Значит, единицу добавляют не всегда, и запись a // b + 1 неверна.

Свернём в одну формулу. Прибавим к делимому поправку d: тогда a + d = b·k + (r + d). Частное вырастет на единицу, когда r + d достигнет b, и не должно вырасти на две — значит r + d обязано остаться меньше 2b.

При r = 0 частное меняться не должно: d меньше b. При r = 1 частное должно вырасти: d не меньше b − 1.

Оба условия совмещаются единственным образом.

Поправка — на единицу меньше делителя.

байт = (бит + 7) // 8

13
13

Оба способа дают одно число: формула с поправкой и явная проверка остатка — это одно и то же.

Куда округлять

Сторона выбирается не формулой, а вопросом.

«Сколько нужно, чтобы вместить» — вверх, с поправкой. «Сколько поместится» — вниз, обычное //.

Вместить — вверх, поместится — вниз.

Разбор: сколько памяти под учётные записи

Имя пользователя — 8 символов алфавита из 30 символов. На каждого дополнительно хранят 12 байт. Пользователей 30.

Руками

Четырёх бит хватает на 16 символов, этого мало. Пяти хватает на 32 — берём 5.

Всё имя: 8 · 5 = 40 бит, это 5 байт.

На пользователя: 5 + 12 = 17 байт. На всех: 17 · 30 = 510 байт.

Округляй одну запись, а не итог.

В программе

Минимальное число бит на символ даёт math.ceil(math.log2(m)): это наименьшее целое, при котором двойка в такой степени покрывает алфавит.

5
40
5
510

Глубина, биты, байты и итог. Последнее число — 510 — совпало со счётом руками.

Ловушки

• Написали a // b + 1. Лишний байт там, где делится нацело.
• Округлили итог вместо одной записи. Ответ выйдет меньше.
• Взяли int(math.log2(k)) + 1. На 2, 16, 256 даёт лишний бит.
• Перевели в байты до деления. Остаток пропал, ответ завышен.
• Ответили на другой вопрос: спрашивали «поместится», округлили вверх.