我有一个整数数组，假设它们的类型为int64_t。现在，我知道每个整数只有前n位是有意义的（也就是说，我知道它们受到某些限制）。
最有效的方式是如何将该数组转换为移除所有不必要空间（即，第一个整数位于a[0]，第二个整数位于a[0]+n位，以此类推）？
我希望它尽可能通用，因为n会随着时间而变化，不过我猜对于特定的n，比如2的幂之类的，可能会有一些聪明的优化方法。
当然，我知道我可以遍历每个值，但我只是想问问StackOverflower是否能想到更聪明的方法。
编辑：
这个问题不是关于压缩数组以占用尽可能少的空间。我只需要从每个整数“剪切”n位，并且给定数组，我知道我可以安全地剪切的确切n位。
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
#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]);
}
这种方法非常低效，因为它每次只处理一位，但这是最简单的实现方式，避免了字节序问题。我还没有对更多数值进行测试，只测试了测试中的数值。此外，没有边界检查，假设输出缓冲区足够长。因此，我想说的是，这段代码可能只适用于教育目的，帮助你入门。
大多数压缩算法都可以接近编码整数所需的最小熵，例如Huffman编码，但像数组一样访问它将是非常困难的。
从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（最大255）？或者uint16_t（最大65535）？我相信你可以使用定义的值和位操作等在int64_t上进行位操作，但除了学术练习外，为什么呢？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;
};
如果没有一些花式操作，这个程序不支持大小端安全，因此只能在程序内部使用，而不能用于导出的数据格式。它经常被用来在单个位中存储布尔值，而无需定义移位和掩码。
int[] 占用更多的空间！关键是通过在原地（可能）移动位来节省空间。 - pajton我认为你无法避免迭代元素。 据我所知，霍夫曼编码需要“符号”的频率，除非你知道生成整数的“过程”的统计数据，否则你必须计算（通过迭代每个元素）。