CODEWITHSUNDEEP
algorithmintegercompressionbit-manipulation
Rick de Water
Rick de Water

Reputation: 2642

Packing sets of non power of 2 integers

I have a set of integers, each with a specific range:

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

I can calculate how many bits are required to store each number separately based on the number of different states that they can have:

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

Which gives me a total of 15 bits. But every number has a range that is unused, resulting in wasted space. I can instead calculate the required bits for the whole set by calculating all the possible states of all the numbers combined:

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

This could save me a whole bit!

And this is where my question comes in: what is the best way to load and store numbers using this type of layout?

Upvotes: 2

Views: 132

Answers (1)

user555045
user555045

Reputation: 64903

A list of variables with different ranges like this:

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

Can (almost?) be interpreted as a mixed-radix number representation. If they started at zero the correspondence would be immediate, but since these start at one (or in general: if they are any finite set of possibilities) they must be remapped a little first, here just by subtracting one for conversion to the "packed" state and adding one back when decoding it again.

The encoding is nice and easy, involving only cheap operations:

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

The scale factors come from the number of possible states of course. Every element needs to be remapped into a contiguous range starting at zero, and then scaled by the product of the #states of the preceding elements, with the first being scaled by 1 (the empty product). By the way note that [1 .. 5] has 5 states, not 4.

Decoding involves remainders and divisions, the simplest (but not in general the fastest) way is extracting digit-by-digit:

// 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

For larger examples it would be more efficient to first "chop" the packed number into a few separate parts, and then decode those independently. This prevents having a long chain of dependent operations, which the digit-by-digit method naturally results in.

Working directly with the packed representation is generally tricky, except to add and subtract from the elements if you know that would not overflow.

Upvotes: 5

Related Questions