整数数组的比特打包
我有一个整数数组，让我们假设它们的类型是int64_t。现在，我知道只有每个整数的前n位是有意义的(也就是说，我知道它们受到一些界限的限制)。
在删除所有不必要的空格的情况下，转换数组的最有效方法是什么(例如，第一个整数位于a[0]，第二个整数位于a[0] + n bits，依此类推)？
我希望它尽可能通用，因为n会随时间而变化，尽管我猜可能会有针对特定n的智能优化，比如2的幂或某物的幂。
当然我知道我可以在值上迭代值，我只想问你，StackOverflowers，你能不能想出更聪明的方法。
编辑：
这个问题不是关于压缩数组以占用尽可能少的空间。我只需要从每个整数中“剪切”n bits，并给出数组，我就知道可以安全地剪切的确切n位。
回答 7
Stack Overflow用户
发布于 2013-08-04 08:04:54
今天我发布了：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, i6Stack Overflow用户
发布于 2010-03-09 00:53:59
我同意keraba的观点，你需要使用像Huffman编码或者Lempel-Ziv-Welch算法之类的东西。你所说的比特打包方式的问题在于你有两种选择：
- 选择一个常数n，这样最大的整数可以是represented.
- Allow n，以便随值的不同而变化。
第一种选择相对容易实现，但除非所有整数都相当小，否则会浪费大量空间。
第二种选择的主要缺点是，您必须以某种方式在输出位流中传达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]);
}这是非常低效的，因为它是一次一点的步骤，但这是实现它的最简单的方法，而不处理字节顺序问题。我也没有使用广泛的值来测试这一点，只使用测试中的值。此外，没有边界检查，并且假设输出缓冲区足够长。所以我要说的是，这段代码可能只是为了教育目的，让你入门。
Stack Overflow用户
发布于 2010-03-08 04:56:43
几乎任何压缩算法都会接近编码整数所需的最小熵，例如，霍夫曼编码，但像访问数组一样访问它将不是微不足道的。
https://stackoverflow.com/questions/2397655
复制相似问题
腾讯云开发者
