有没有办法在位集中表示 ~27 个整数并有效地访问它们?

Question

我有一个包含 27 个有符号整数数组的结构。打包字节后，此结构大约占用 112 字节的内存。我想减小结构的大小。由于这些整数不能大于 400k，我只需要 20 位来表示它们。我浪费了相当多的内存，因为我需要有很多这样的结构。有什么方法可以降低内存成本，同时仍然能够访问每个 int 而不会造成太大的性能损失？实现位集是最好的方法吗？

Answer 1

是的，这被称为位打包，尽管位集可能不是正确的表达方式。至少在C++和 Java 中，位集比数据位占用更多的空间，这违背了您的目的。

相反，在 C 中，您可以使用位字段或自己进行位摆弄。位字段是结构中具有指定大小(以位为单位(的元素。它们经过专门设计，可节省空间。但在您的情况下，这种方法有两个问题：

1. 鉴于您的字段相对较大(20 位(，它们可能不会像您想要的那样打包。与字边界相关的一些选择是实现定义的，因此您可能会发现编译器最终浪费了太多空间。
位字段不允许
2. 使用数组，因此指定 27 个单独的字段可能很麻烦。

所以我建议自己做。只需将您的数组声明为 27*20/8(向上舍入(字节数组：

#define ROUND_UP(n,d) (((n) + (d) - 1) / (d));
unsigned char myPackedIntArray[ROUND_UP(27*20,8)];

然后写一个getter和一个setter：

int unpack(unsigned char packedArray[], int index)
{
struct {signed int i:20;} res; //handy way to do the sign extension from 20 bits to int width.
int byteIndex = index*20 / 8;
if(index%2 == 0) //even 20-bit fields start on a byte boundary
{
res.s =  (packedArray[byteIndex  ]<<12);
res.s += (packedArray[byteIndex+1]<<4);
res.s += (packedArray[byteIndex+2]>>4);
}
else //odd 20-bit fields start halfway through the byte
{
res.s =  ((packedArray[byteIndex  ]&0x0F) << 16);
res.s += ((packedArray[byteIndex+1]     ) << 8);
res.s += ((packedArray[byteIndex+2]     );
}
return (int)(res.s);
}
int pack(unsigned char packedArray[], int index)
{
//left as exercise to the reader
}

将 20 位值打包和解压缩到紧密打包的数组中。

现在来看性能问题 - 查看吸气器和二传手会给你一个好主意。而不是一次提取，将有大约一个乘法和除法，3个获取和一些位运算。Dan Lemire在这个话题上取得了一些出色的成绩。简短的回答是"不差多少"，但最终它将与编译器和架构有很大关系。