c - 有什么方法可以在位集中表示约 27 个整数并有效地访问它们吗？

Question

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

Answer 1

是的，这叫做位打包，虽然位集可能不是表达它的正确方式。位集(至少在 C++ 和 Java 中)占用的空间比数据位多，这违背了您的目的。

相反，在 C 中，您可以使用位域 或自行调整位。位域是结构中具有指定位大小的元素。它们专门设计用于节省空间。但是在您的情况下，这种方法有两个问题:

1. 鉴于您的字段相对较大(20 位)，它们可能不会像您希望的那样打包。与单词边界相关的一些选择是 implementation defined ，因此您可能会发现编译器最终还是浪费了太多空间。
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 位值打包和解包到一个紧密打包的数组中。

现在谈到性能问题 - 查看 getter 和 setter 会给您一个好主意。取一次取，而不是一次乘法和除法，取 3 次取和一些位操作。 Dan Lemire在这个话题上有一些很好的结果。简短的回答是“不会更糟”，但最终这将与您的编译器和架构有很大关系。