非整数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)

比例因子当然来自可能状态的数量。每个元素都需要重新映射到从零开始的连续范围内，然后再根据前面元素的#state乘积进行缩放，第一个元素按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

对于较大的示例，将打包的数据“切”成几个单独的部分，然后独立地对其进行解码会更有效。这样可以避免一连串的依存运算，而这些依存运算自然会导致数位转换。

直接与打包表示工作一般是棘手的，除了添加和元素减去，如果你知道，不会溢出。