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

Question

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

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

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

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

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

但是我有兴趣评估 space 通过使用我的元素只能取 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];

Answer 2

有一种通用方法可以计算出您需要多少位：

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

当然在现实中你会在整数位数中打包固定数量的值，所以你必须将这个 1.585 乘以该数量并四舍五入。例如，如果您打包 5 个：

1.585 × 5 = 7.925，意思是你的5个值正好适合一个8位char.

解包方式在JS1的回答中有说明。解包的通用公式是 element[i] = (value / (N ^ i) ) mod N

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

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

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

packing an array of 3 values in buffer

c

c++

memory

bit-manipulation

information-theory