c++ - 在缓冲区中打包 3 个值的数组

Question

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

我有一个数据类型可以取 3 个可能的值 (0,1,2)。我有一个包含 20 个这种数据类型元素的数组。

因为我想在最少的内存上对信息进行编码，所以我做了以下操作:

• 考虑每个元素最多可以有 4 个值(2 位)
• 每个 char 有 8 位，所以我可以放 4 次一个元素
• 5 char 有 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)

Answer 1

您应该能够使用 4 个字节来执行您所说的操作。假设您将这 20 个值存储到一个名为 value 的 int32_t 中，下面是您将如何提取任何特定元素:

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;
}

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

value = 0;
for (i=19;i>=0;i--)
    value = value * 3 + element[i];