c++ - 整数数组的位封装

Question

我有一个整数数组，假设它们是 int64_t 类型。现在，我知道只有每个整数的前 n 位是有意义的(也就是说，我知道它们受到某些界限的限制)。

以删除所有不必要空间的方式转换数组的最有效方法是什么(即我在 a[0] 处有第一个整数，在 a 处有第二个整数[0] + n 位 等等) ?

我希望它尽可能通用，因为 n 会不时变化，但我猜可能会有针对特定 n 的智能优化，例如2 或某事的幂。

当然我知道我可以迭代 value over value，我只是想问问你 StackOverflowers 是否可以想出一些更聪明的方法。

编辑:

这道题不是关于将数组压缩到尽可能少的空间。我只需要从每个整数中“剪切”n 位 并给定数组，我知道我可以安全剪切的确切 n 位。

Answer 1

今天我发布了:PackedArray: Packing Unsigned Integers Tightly (github project)。

它实现了一个随机访问容器，其中项目以位级别打包。换句话说，它就像你能够操纵一个例如。 uint9_t 或 uint17_t 数组:

PackedArray principle:
  . compact storage of <= 32 bits items
  . items are tightly packed into a buffer of uint32_t integers

PackedArray requirements:
  . you must know in advance how many bits are needed to hold a single item
  . you must know in advance how many items you want to store
  . when packing, behavior is undefined if items have more than bitsPerItem bits

PackedArray general in memory representation:
  |-------------------------------------------------- - - -
  |       b0       |       b1       |       b2       |
  |-------------------------------------------------- - - -
  | i0 | i1 | i2 | i3 | i4 | i5 | i6 | i7 | i8 | i9 |
  |-------------------------------------------------- - - -

  . items are tightly packed together
  . several items end up inside the same buffer cell, e.g. i0, i1, i2
  . some items span two buffer cells, e.g. i3, i6