Упаковочные наборы без силы 2 целых числа

Question

У меня есть набор целых чисел, каждое с определенным диапазоном:

foo = [1, 5]
bar = [1, 10]
baz = [1, 200]

Я могу рассчитать, сколько бит требуется для хранения каждого числа отдельно, основываясь на количестве различных состояний, которые они могут иметь:

foo = 5 possible states   ~ 3 bits
bar = 10 possible states  ~ 4 bits
baz = 200 possible states ~ 8 bits

Что дает мне всего 15 битов.Но у каждого числа есть диапазон, который не используется, приводя к потраченному впустую месту.Вместо этого я могу рассчитать требуемые биты для всего набора, вычислив все возможные состояния всех чисел:

5 * 10 * 200 = 10000 possible states ~ 14 bits

Это может сэкономить мне целый бит!

И это гдеу меня возникает вопрос: как лучше всего загружать и хранить номера, используя этот тип макета?

Answer 1

Список переменных с различными диапазонами, например:

foo = [1, 5]
bar = [1, 10]
baz = [1, 200]

Может (почти?) Интерпретироваться как представление числа со смешанным основанием.Если бы они начинались с нуля, соответствие было бы немедленным, но поскольку они начинаются с одного (или вообще: если они любой конечный набор возможностей), они должны быть сначала немного переназначены, здесь просто путем вычитания одногодля преобразования в «упакованное» состояние и добавления одного обратно при его декодировании.

Кодировка удобна и проста, включает только дешевые операции:

packed = (foo - 1) + 5 * (bar - 1) + (5 * 10) * (baz - 1)

Коэффициенты масштабирования получены изколичество возможных состояний конечно.Каждый элемент должен быть переназначен в непрерывный диапазон, начиная с нуля, а затем масштабирован произведением # состояний предыдущих элементов, причем первый масштаб масштабируется на 1 (пустой продукт).Кстати, обратите внимание, что [1 .. 5] имеет 5 состояний, а не 4.

Декодирование включает в себя остатки и деления, самый простой (но не самый быстрый) способ - извлечь цифру за цифрой:

// extract foo
foo = packed % 5 + 1
// drop foo from packed representation
packed /= 5
// extract bar (which is now the lowest digit in 'packed')
bar = packed % 10 + 1
// drop bar
packed /= 10
// top digit is left over
baz = packed + 1

Для более крупных примеров было бы более эффективно сначала «нарезать» упакованное число на несколько отдельных частей, а затем декодировать их независимо.Это предотвращает наличие длинной цепочки зависимых операций, что, естественно, приводит к результату цифр-за-цифрой.

Работать напрямую с упакованным представлением обычно сложно, за исключением сложения и вычитания из элементов , если Вы знаете, что это не переполнится.