algorithm - 非 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)

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

对于较大的示例，首先将打包数字“切”成几个单独的部分，然后独立解码这些部分会更有效。这可以防止出现一长串依赖操作，而逐个数字方法自然会导致这种情况。

直接使用打包表示通常很棘手，除了在元素中添加和减去如果您知道不会溢出。