我有一个整数数组，假设它们的类型是int64_t. 现在，我知道只有每个n整数的每个第一位都是有意义的（也就是说，我知道它们受到某些界限的限制）。
以删除所有不必要的空间的方式转换数组的最有效方法是什么（即我有第一个整数a[0]，第二个整数a[0] + n bits等等）？
我希望它尽可能地通用，因为n会不时变化，尽管我猜可能会有针对特定n的 2 或某事物的智能优化。
当然我知道我可以迭代价值而不是价值，我只是想问你 StackOverflowers 是否能想到一些更聪明的方法。
编辑：
这个问题不是关于压缩数组以尽可能少地占用空间。我只需n bits要从每个整数中“剪切”，并且给定数组，我知道我可以安全剪切的确切n位。
今天我发布了：PackedArray: Packing Unsigned Integers Tightly（github项目）。
它实现了一个随机访问容器，其中项目以位级别打包。换句话说，它的作用就像您能够操作 eguint9_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
我同意 keraba 的观点，即您需要使用 Huffman 编码或 Lempel-Ziv-Welch 算法之类的东西。您所说的位打包方式的问题是您有两个选择：
第一个选项相对容易实现，但除非所有整数都相当小，否则真的会浪费很多空间。
第二个选项的主要缺点是您必须以某种方式在输出比特流中传达 n 的变化。例如，每个值都必须有一个与之关联的长度。这意味着您要为每个输入值存储两个整数（尽管整数较小）。您很有可能会使用此方法增加文件大小。
Huffman 或 LZW 的优势在于，它们以这样一种方式创建码本，即可以从输出比特流中导出代码的长度，而无需实际存储长度。这些技术使您可以非常接近香农极限。
我决定尝试一下您的原始想法（常量 n，删除未使用的位并打包），这是我想出的天真的实现：
#include <sys/types.h>
#include <stdio.h>
int pack(int64_t* input, int nin, void* output, int n)
{
int64_t inmask = 0;
unsigned char* pout = (unsigned char*)output;
int obit = 0;
int nout = 0;
*pout = 0;
for(int i=0; i<nin; i++)
{
inmask = (int64_t)1 << (n-1);
for(int k=0; k<n; k++)
{
if(obit>7)
{
obit = 0;
pout++;
*pout = 0;
}
*pout |= (((input[i] & inmask) >> (n-k-1)) << (7-obit));
inmask >>= 1;
obit++;
nout++;
}
}
return nout;
}
int unpack(void* input, int nbitsin, int64_t* output, int n)
{
unsigned char* pin = (unsigned char*)input;
int64_t* pout = output;
int nbits = nbitsin;
unsigned char inmask = 0x80;
int inbit = 0;
int nout = 0;
while(nbits > 0)
{
*pout = 0;
for(int i=0; i<n; i++)
{
if(inbit > 7)
{
pin++;
inbit = 0;
}
*pout |= ((int64_t)((*pin & (inmask >> inbit)) >> (7-inbit))) << (n-i-1);
inbit++;
}
pout++;
nbits -= n;
nout++;
}
return nout;
}
int main()
{
int64_t input[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
int64_t output[21];
unsigned char compressed[21*8];
int n = 5;
int nbits = pack(input, 21, compressed, n);
int nout = unpack(compressed, nbits, output, n);
for(int i=0; i<=20; i++)
printf("input: %lld output: %lld\n", input[i], output[i]);
}
这是非常低效的，因为一次只执行一步，但这是在不处理字节顺序问题的情况下实现它的最简单方法。我也没有使用广泛的值对此进行测试，只是测试中的值。此外，没有边界检查，并且假定输出缓冲区足够长。所以我要说的是，这段代码可能只用于教育目的，让你开始。
大多数压缩算法都将接近编码整数所需的最小熵，例如霍夫曼编码，但像数组一样访问它并非易事。
从 Jason B 的实现开始，我最终编写了自己的版本，它处理位块而不是单个位。一个区别是它是 lsb：它从最低输出位开始到最高。这只会使使用二进制转储（如 Linux）更难读取xxd -b。作为一个细节，int*可以简单地更改为int64_t*，它应该更好unsigned。我已经用几百万个数组测试了这个版本，它看起来很可靠，所以我分享剩下的：
int pack2(int *input, int nin, unsigned char* output, int n)
{
int obit = 0;
int ibit = 0;
int ibite = 0;
int nout = 0;
if(nin>0) output[0] = 0;
for(int i=0; i<nin; i++)
{
ibit = 0;
while(ibit < n) {
ibite = std::min(n, ibit + 8 - obit);
output[nout] |= (input[i] & (((1 << ibite)-1) ^ ((1 << ibit)-1))) >> ibit << obit;
obit += ibite - ibit;
nout += obit >> 3;
if(obit & 8) output[nout] = 0;
obit &= 7;
ibit = ibite;
}
}
return nout;
}
int unpack2(int *oinput, int nin, unsigned char* ioutput, int n)
{
int obit = 0;
int ibit = 0;
int ibite = 0;
int nout = 0;
for(int i=0; i<nin; i++)
{
oinput[i] = 0;
ibit = 0;
while(ibit < n) {
ibite = std::min(n, ibit + 8 - obit);
oinput[i] |= (ioutput[nout] & (((1 << (ibite-ibit+obit))-1) ^ ((1 << obit)-1))) >> obit << ibit;
obit += ibite - ibit;
nout += obit >> 3;
obit &= 7;
ibit = ibite;
}
}
return nout;
}
我知道这似乎是显而易见的事情，因为我确信实际上有一个解决方案，但为什么不使用较小的类型，比如uint8_t(max 255)？或uint16_t（最大 65535）？我相信您可以对int64_t使用定义的值和/或操作等进行位操作，但是，除了学术练习之外，为什么？
关于学术练习，Bit Twiddling Hacks是一本不错的读物。
如果您有固定的大小，例如您知道您的数字是 38 位而不是 64 位，您可以使用位规格构建结构。有趣的是，您还可以将较小的元素放入剩余空间中。
struct example {
/* 64bit number cut into 3 different sized sections */
uint64_t big_num:38;
uint64_t small_num:16;
uint64_t itty_num:10;
/* 8 bit number cut in two */
uint8_t nibble_A:4;
uint8_t nibble_B:4;
};
如果没有一些跳跃，这不是大/小端安全的，因此只能在程序中使用，而不是在导出的数据格式中使用。它经常用于将布尔值存储在单个位中，而无需定义移位和掩码。
我认为您无法避免遍历元素。AFAIK 霍夫曼编码需要“符号”的频率，除非您知道生成整数的“过程”的统计信息，否则您将不得不计算（通过遍历每个元素）。