blocks|key|2789967|text|我知道这看起来似乎是显而易见的事情，因为我确信实际上有一个解决方案，但是为什么不使用更小的类型，比如uint8_t+(最大255)？或者uint16_t+(最大65535)？我确信您可以使用定义的值和或操作等对int64_t进行位操作，但是，除了学术练习之外，为什么呢？|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2789968|在学术练习的笔记上，Bit+Twiddling+Hacks是一个很好的读物。|2789969|entityMap|0|LINK|mutability|MUTABLE|url|http://graphics.stanford.edu/~seander/bithacks.html^0|1E|7|1W|8|2X|7|0|A|J|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@$9|Q|A|R|B|C]|$9|S|A|T|B|C]|$9|U|A|V|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|W|8|@]|D|@$9|X|A|Y|1|Z]]|E|$]]|$1|H|3|-4|5|6|7|10|8|@]|D|@]|E|$]]]|I|$J|$5|K|L|M|E|$N|O]]]]

I know this might seem like the obvious thing to say as I'm sure there's actually a solution, but why not use a smaller type, like <code>uint8_t</code> (max 255)? or <code>uint16_t</code> (max 65535)?. I'm sure you could bit-manipulate on an <code>int64_t</code> using defined values and or operations and the like, but, aside from an academic exercise, why?

And on the note of academic exercises, <a href="http://graphics.stanford.edu/~seander/bithacks.html" rel="nofollow noreferrer">Bit Twiddling Hacks</a> is a good read.

blocks|key|2017302|text|几乎任何压缩算法都会接近编码整数所需的最小熵，例如，霍夫曼编码，但像访问数组一样访问它将不是微不足道的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2017303|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Most any compression algorithm will get close to the minimum entropy needed to encode the integers, for example, Huffman coding, but accessing it like an array will be non-trivial.

blocks|key|2790062|text|我同意keraba的观点，你需要使用像Huffman编码或者Lempel-Ziv-Welch算法之类的东西。你所说的比特打包方式的问题在于你有两种选择：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2790063|2790064|选择一个常数n，这样最大的整数可以是represented.|unordered-list-item|2790065|Allow+n，以便随值的不同而变化。|2790066|2790067|第一种选择相对容易实现，但除非所有整数都相当小，否则会浪费大量空间。|2790068|第二种选择的主要缺点是，您必须以某种方式在输出位流中传达n中的变化。例如，每个值都必须有一个与之关联的长度。这意味着您为每个输入值存储了两个整数(尽管较小的整数)。使用这种方法很可能会增加文件的大小。|2790069|Huffman或LZW的优点在于，它们以这样一种方式创建码本，即可以从输出比特流推导出代码的长度，而无需实际存储长度。这些技术使您可以非常接近香农极限。|2790070|我决定给你最初的想法(常量n，删除不用的位并打包)，有趣地尝试一下，这里是我想出的天真的实现：|2790071|#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%2B%2B)
++++{
++++++++inmask+=+(int64_t)1+<<+(n-1);
++++++++for(int+k=0;+k<n;+k%2B%2B)
++++++++{
++++++++++++if(obit>7)
++++++++++++{
++++++++++++++++obit+=+0;
++++++++++++++++pout%2B%2B;
++++++++++++++++*pout+=+0;
++++++++++++}
++++++++++++*pout+%7C=+(((input[i]+&+inmask)+>>+(n-k-1))+<<+(7-obit));
++++++++++++inmask+>>=+1;
++++++++++++obit%2B%2B;
++++++++++++nout%2B%2B;
++++++++}
++++}
++++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%2B%2B)
++++++++{
++++++++++++if(inbit+>+7)
++++++++++++{
++++++++++++++++pin%2B%2B;
++++++++++++++++inbit+=+0;
++++++++++++}
++++++++++++*pout+%7C=+((int64_t)((*pin+&+(inmask+>>+inbit))+>>+(7-inbit)))+<<+(n-i-1);
++++++++++++inbit%2B%2B;
++++++++}
++++++++pout%2B%2B;
++++++++nbits+-=+n;
++++++++nout%2B%2B;
++++}
++++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%2B%2B)
++++++++printf("input:+%25lld+++output:+%25lld\n",+input[i],+output[i]);
}|code-block|syntax|javascript|2790072|这是非常低效的，因为它是一次一点的步骤，但这是实现它的最简单的方法，而不处理字节顺序问题。我也没有使用广泛的值来测试这一点，只使用测试中的值。此外，没有边界检查，并且假设输出缓冲区足够长。所以我要说的是，这段代码可能只是为了教育目的，让你入门。|2790073|entityMap^0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Z|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|10|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|11|8|@]|9|@]|A|$]]|$1|F|3|G|5|E|7|12|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|13|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|14|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|15|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|16|8|@]|9|@]|A|$]]|$1|O|3|P|5|6|7|17|8|@]|9|@]|A|$]]|$1|Q|3|R|5|S|7|18|8|@]|9|@]|A|$T|U]]|$1|V|3|W|5|6|7|19|8|@]|9|@]|A|$]]|$1|X|3|-4|5|6|7|1A|8|@]|9|@]|A|$]]]|Y|$]]

I agree with keraba that you need to use something like Huffman coding or perhaps the Lempel-Ziv-Welch algorithm. The problem with bit-packing the way you are talking about is that you have two options:

<ul>
<li>Pick a constant n such that the largest integer can be represented.</li>
<li>Allow n to vary from value to value.</li>
</ul>

The first option is relatively easy to implement, but is really going to waste a lot of space unless all integers are rather small.

The second option has the major disadvantage that you have to convey changes in n somehow in the output bitstream. For instance, each value will have to have a length associated with it. This means you are storing two integers (albeit smaller integers) for every input value. There's a good chance you'll increase the file size with this method.

The advantage of Huffman or LZW is that they create codebooks in such a way that the length of the codes can be derived from the output bitstream without actually storing the lengths. These techniques allow you to get very close to the Shannon limit.

I decided to give your original idea (constant n, remove unused bits and pack) a try for fun and here is the naive implementation I came up with:

<pre><code>#include &lt;sys/types.h&gt;
#include &lt;stdio.h&gt;

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&lt;nin; i++)
 {
 inmask = (int64_t)1 &lt;&lt; (n-1);
 for(int k=0; k&lt;n; k++)
 {
 if(obit&gt;7)
 {
 obit = 0;
 pout++;
 *pout = 0;
 }
 *pout |= (((input[i] &amp; inmask) &gt;&gt; (n-k-1)) &lt;&lt; (7-obit));
 inmask &gt;&gt;= 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 &gt; 0)
 {
 *pout = 0;
 for(int i=0; i&lt;n; i++)
 {
 if(inbit &gt; 7)
 {
 pin++;
 inbit = 0;
 }
 *pout |= ((int64_t)((*pin &amp; (inmask &gt;&gt; inbit)) &gt;&gt; (7-inbit))) &lt;&lt; (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&lt;=20; i++)
 printf("input: %lld output: %lld\n", input[i], output[i]);
}
</code></pre>

This is very inefficient because is steps one bit at a time, but that was the easiest way to implement it without dealing with issues of endianess. I have not tested this either with a wide range of values, just the ones in the test. Also, there is no bounds checking and it is assumed the output buffers are long enough. So what I am saying is that this code is probably only good for educational purposes to get you started.

blocks|key|2017355|text|我不认为你可以避免遍历元素。AFAIK+Huffman编码需要“符号”的频率，除非你知道生成整数的“过程”的统计数据，否则你必须计算(通过迭代每个元素)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2017356|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

I don't think you can avoid iterating across the elements.
AFAIK Huffman encoding requires the frequencies of the "symbols", which unless you know the statistics of the "process" generating the integers, you will have to compute (by iterating across every element).

blocks|key|4903297|text|如果你有固定的大小，例如你知道你的数字是38位而不是64位，你可以使用位规范来构建结构。有趣的是，您还可以在剩余空间中容纳更小的元素。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4903298|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;
};|code-block|syntax|javascript|4903299|这不是没有跳跃的大/小字节顺序安全，所以只能在程序中使用，而不能以导出的数据格式使用。它通常用于在不定义移位和掩码的情况下以单个位存储布尔值。|4903300|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

If you have fixed sizes, e.g. you know your number is 38bit rather than 64, you can build structures using bit specifications. Amusing you also have smaller elements to fit in the remaining space.

<pre><code>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;
};
</code></pre>

This isn't big/little endian safe without some hoop-jumping, so can only be used within a program rather than in a exported data format. It's quite often used to store boolean values in single bits without defining shifts and masks.

blocks|key|2790168|text|今天我发布了：PackedArray:+Packing+Unsigned+Integers+Tightly+(github+project)。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2790169|它实现了一个随机访问容器，其中项以位级别打包。换句话说，它的作用就像你能够操作一个uint9_t或uint17_t数组：|style|CODE|2790170|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:
++%7C--------------------------------------------------+-+-+-
++%7C+++++++b0+++++++%7C+++++++b1+++++++%7C+++++++b2+++++++%7C
++%7C--------------------------------------------------+-+-+-
++%7C+i0+%7C+i1+%7C+i2+%7C+i3+%7C+i4+%7C+i5+%7C+i6+%7C+i7+%7C+i8+%7C+i9+%7C
++%7C--------------------------------------------------+-+-+-

++.+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|code-block|syntax|javascript|2790171|entityMap|0|LINK|mutability|MUTABLE|url|http://pempek.net/articles/2013/08/03/packedarray-random-access-array-tightly-packed-unsigned-integers/|1|https://github.com/gpakosz/PackedArray^0|7|1A|0|1J|E|1|0|15|7|1D|8|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@$A|X|B|Y|1|Z]|$A|10|B|11|1|12]]|C|$]]|$1|D|3|E|5|6|7|13|8|@$A|14|B|15|F|G]|$A|16|B|17|F|G]]|9|@]|C|$]]|$1|H|3|I|5|J|7|18|8|@]|9|@]|C|$K|L]]|$1|M|3|-4|5|6|7|19|8|@]|9|@]|C|$]]]|N|$O|$5|P|Q|R|C|$S|T]]|U|$5|P|Q|R|C|$S|V]]]]

Today I released: <a href="http://pempek.net/articles/2013/08/03/packedarray-random-access-array-tightly-packed-unsigned-integers/" rel="nofollow">PackedArray: Packing Unsigned Integers Tightly</a> (<a href="https://github.com/gpakosz/PackedArray" rel="nofollow">github project</a>).

It implements a random access container where items are packed at the bit-level. In other words, it acts as if you were able to manipulate a e.g. <code>uint9_t</code> or <code>uint17_t</code> array:

<pre><code>PackedArray principle:
 . compact storage of &lt;= 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
</code></pre>

blocks|key|2010700|text|从Jason+B的实现开始，我最终编写了自己的版本，它处理位块而不是单个位。一个区别是它是lsb:它从最低输出位开始到最高输出位。这只会增加使用二进制转储(如Linux+xxd+-b+)进行读取的难度。作为一个细节，int*可以简单地更改为int64_t*，它应该是unsigned更好。我已经用几百万个数组测试了这个版本，它看起来很可靠，所以我将分享剩下的：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2010701|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%2B%2B)
++++++++{
++++++++++++++++ibit+=+0;
++++++++++++++++while(ibit+<+n)+{
++++++++++++++++++++++++ibite+=+std::min(n,+ibit+%2B+8+-+obit);
++++++++++++++++++++++++output[nout]+%7C=+(input[i]+&+(((1+<<+ibite)-1)+%5E+((1+<<+ibit)-1)))+>>+ibit+<<+obit;
++++++++++++++++++++++++obit+%2B=+ibite+-+ibit;
++++++++++++++++++++++++nout+%2B=+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%2B%2B)
++++++++{
++++++++++++++++oinput[i]+=+0;
++++++++++++++++ibit+=+0;
++++++++++++++++while(ibit+<+n)+{
++++++++++++++++++++++++ibite+=+std::min(n,+ibit+%2B+8+-+obit);
++++++++++++++++++++++++oinput[i]+%7C=+(ioutput[nout]+&+(((1+<<+(ibite-ibit%2Bobit))-1)+%5E+((1+<<+obit)-1)))+>>+obit+<<+ibit;
++++++++++++++++++++++++obit+%2B=+ibite+-+ibit;
++++++++++++++++++++++++nout+%2B=+obit+>>+3;
++++++++++++++++++++++++obit+&=+7;
++++++++++++++++++++++++ibit+=+ibite;
++++++++++++++++}
++++++++}
++++++++return+nout;
}|code-block|syntax|javascript|2010702|entityMap^0|2D|6|30|4|3C|8|3P|8|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@$9|N|A|O|B|C]|$9|P|A|Q|B|C]|$9|R|A|S|B|C]|$9|T|A|U|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|V|8|@]|D|@]|E|$I|J]]|$1|K|3|-4|5|6|7|W|8|@]|D|@]|E|$]]]|L|$]]

Starting from Jason B's implementation, I eventually wrote my own version which processes bit-blocks instead of single bits. One difference is that it is lsb: It starts from lowest output bits going to highest. This only makes it harder to read with a binary dump, like Linux <code>xxd -b</code>. As a detail, <code>int*</code> can be trivially changed to <code>int64_t*</code>, and it should even better be <code>unsigned</code>. I have already tested this version with a few million arrays and it seems solid, so I share will the rest:

<pre><code>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&gt;0) output[0] = 0;
 for(int i=0; i&lt;nin; i++)
 {
 ibit = 0;
 while(ibit &lt; n) {
 ibite = std::min(n, ibit + 8 - obit);
 output[nout] |= (input[i] &amp; (((1 &lt;&lt; ibite)-1) ^ ((1 &lt;&lt; ibit)-1))) &gt;&gt; ibit &lt;&lt; obit;
 obit += ibite - ibit;
 nout += obit &gt;&gt; 3;
 if(obit &amp; 8) output[nout] = 0;
 obit &amp;= 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&lt;nin; i++)
 {
 oinput[i] = 0;
 ibit = 0;
 while(ibit &lt; n) {
 ibite = std::min(n, ibit + 8 - obit);
 oinput[i] |= (ioutput[nout] &amp; (((1 &lt;&lt; (ibite-ibit+obit))-1) ^ ((1 &lt;&lt; obit)-1))) &gt;&gt; obit &lt;&lt; ibit;
 obit += ibite - ibit;
 nout += obit &gt;&gt; 3;
 obit &amp;= 7;
 ibit = ibite;
 }
 }
 return nout;
}
</code></pre>

I have an array of integers, lets assume they are of type <code>int64_t</code>. Now, I know that only every first <code>n</code> bits of every integer are meaningful (that is, I know that they are limited by some bounds). 

What is the most efficient way to convert the array in the way that all unnecessary space is removed (i.e. I have the first integer at <code>a[0]</code>, the second one at <code>a[0] + n bits</code> and so on) ?

I would like it to be general as much as possible, because <code>n</code> would vary from time to time, though I guess there might be smart optimizations for specific <code>n</code> like powers of 2 or sth.

Of course I know that I can just iterate value over value, I just want to ask you StackOverflowers if you can think of some more clever way.

Edit:

This question is not about compressing the array to take as least space as possible. I just need to "cut" <code>n bits</code> from every integer and given the array I know the exact <code>n</code> of bits I can safely cut.

Bit packing of array of integers

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我有一个整数数组，让我们假设它们的类型是int64_t。现在，我知道只有每个整数的前n位是有意义的(也就是说，我知道它们受到一些界限的限制)。在删除所有不必要的空格的情况下，转换数组的最有效方法是什么(例如，第一个整数位于a[0]，第二个整数位于a[0] + n bits，依此类推)？我希望它尽可能通用，因为n会随时间...

问整数数组的比特打包
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问整数数组的比特打包EN