首页 > 解决方案 > 2 个整数的非幂的包装集

问题描述

我有一组整数,每个整数都有一个特定的范围:

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

这可以节省我一大笔钱!

这就是我的问题所在:使用这种布局加载和存储数字的最佳方式是什么?

标签: algorithmintegercompressionbit-manipulation

解决方案


具有不同范围的变量列表,如下所示:

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

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

直接使用打包表示通常很棘手,除了在知道不会溢出的情况下从元素中添加和减去。


推荐阅读