Предположим, на нас откуда-то свалилось ограничение по размеру ячейки ... например, только 2 байта (или даже - один!).

А нам нужно организовать некое подобие счетчиков, чтобы отслеживать частоты ...

Мы говорим: давайте будем хранить в ячейке не САМУ частоту, а - ее логарифм!

Вопрос: сколько НА САМОМ ДЕЛЕ потребуется ТАКИХ ячеек (у каждой "отслеживаемой сущности") чтобы такой счетчик организовать?

Дык! Округленно, есссно!! Например:
1 - частоты от 1 до 3
2 - частоты от 4 до 7
3 - частоты от 8 до 15
255 - частоты, начиная с 2^255 ;-)