2

我有以下问题，我无法优雅地解决。

我有一个可以采用 3 个可能值（0、1、2）的数据类型。我有一个包含 20 个这种数据类型元素的数组。

由于我想在最少的内存上对信息进行编码，因此我执行了以下操作：

  • 考虑到每个元素最多可以取 4 个值（2 位）
  • 每个char都有 8 位，所以我可以放 4 次元素
  • 5char包含 40 位，所以我可以存储 20 个元素。

我已经做到了，它的工作时间。

但是，我有兴趣评估通过使用我的元素只能取 3 个值而不是 4 这个事实获得的空间。每个可能的组合都给我们 3 的 20 次方，即 3,486,784,401。然而 256 的 4 次方给我们 4,294,967,296 ，这是更大的。这意味着我可以在 4 上编码我的数据char。

有没有一种通用的方法来做第二个想法？第一个想法很容易通过位掩码/位移位实现。但是，由于 3 个值不适合整数位数，我不知道如何将这些值中的任何一个编码/解码为 4 个字符的数组。

您对它的完成方式有任何想法或参考吗？我认为必须有一个通用的方法。如果有什么我对这个的可行性感兴趣的话

编辑：这可以简化为：如何将 0 到 2 的 5 个值仅存储到 1 个字节中（如 256 >= 3^5 = 243）

4

2 回答 2

5

您应该能够使用 4 个字节完成您所说的操作。假设您将 20 个值存储到一个int32_tcalledvalue中，以下是提取任何特定元素的方法：

element[0] = value % 3;
element[1] = (value / 3) % 3;
element[2] = (value / 9) % 3;
...
element[19] = (value / 1162261467) % 3; // 1162261467 = 3 ^ 19

或者作为一个循环：

for (i=0;i<20;i++) {
    element[i] = value % 3;
    value /= 3;
}

value要从构建element，您只需执行相反的操作，如下所示：

value = 0;
for (i=19;i>=0;i--)
    value = value * 3 + element[i];
于 2015-03-11T22:41:58.773 回答
0

有一种通用方法可以确定您需要多少位：

如果您的数据类型有N个不同的值，那么您需要log(N) / log(2)位来存储该值。例如，在您的示例中，log(3) / log(2)等于 1.585 位。

当然，实际上您会将固定数量的值打包成整数位数，因此您必须将此 1.585 乘以该数量并向上取整。例如，如果您打包其中的 5 个：

1.585 × 5 = 7.925，这意味着您的 5 个值恰好适合一个 8-bit char。

解压值的方法已在 JS1 的答案中显示。解包的通用公式是element[i] = (value / (N ^ i) ) mod N

最后一点，这仅在您确实需要优化内存使用时才有意义。为了比较，这里有一些人们打包这些值类型的流行方式。大多数情况下，占用的额外空间不是问题。

  • 一个数组bool： 使用 8 位存储一个bool。而且很多人真的不喜欢std::vector<bool>.
  • enum Bla { BLA_A, BLA_B, BLA_C};一个数组或向量Bla可能每个元素使用 32 位 ( sizeof(Bla) == sizeof(int))。
于 2015-03-11T23:39:19.830 回答