英文:
Fast way to switch bits order?
问题
我有一个二进制数如下:
10011011
我的数据存储形式是 10,01,10,11
,但我想要重新排序成如下形式:
11100110
数据看起来像是 11,10,01,10
。这个操作类似于字节顺序转换,但是在位级别上进行。
有没有一种快速的位操作方法可以实现这个?
目前,我必须将其解码为四个整数,然后合并为一个整数。
英文:
I have a binary like this
10011011
My data store like this 10,01,10,11
, but I want to reorder like this
11100110
The data look like 11,10,01,10
.This operation same as ByteOrder convert but in bits level.
Any fast bitop way to do this ?
Currently, I have to decode this to four int then merge to one.
答案1
得分: 3
你可以使用位掩码和位移操作一步完成,而不需要将其分解为4个不同的变量:
Go解决方案(在Go Playground上尝试):
i := 0x9b // 10011011
fmt.Printf("%b\n", i)
i = (i&0x03)<<6 | (i&0x0c)<<2 | (i&0x30)>>2 | (i&0xc0)>>6
fmt.Printf("%b\n", i)
输出:
10011011
11100110
Java中的解决方案:
int i = 0x9b; // 10011011
System.out.printf("%x\n", i);
i = (i & 0x03) << 6 | (i & 0x0c) << 2 | (i & 0x30) >> 2 | (i & 0xc0) >> 6;
System.out.printf("%x\n", i);
输出(它是十六进制,但表示相同的数字):
9b
e6
由于每个位组(2位的组)必须从输入中的原始位置移动,我认为你不能用更少的步骤(掩码和位移操作)来完成。如果这对你来说不够快,使其更快的唯一选择是预先计算转换并将结果存储在数组中,如@ruakh的答案中所述。当然,如果我们允许超过8位,这将变得不可行。
英文:
You can do it using bitmasks and bitshift in one step without breaking it into 4 different variables:
Go solution (try it on the Go Playground):
i := 0x9b // 10011011
fmt.Printf("%b\n", i)
i = (i&0x03)<<6 | (i&0x0c)<<2 | (i&0x30)>>2 | (i&0xc0)>>6
fmt.Printf("%b\n", i)
Output:
10011011
11100110
In Java:
int i = 0x9b; // 10011011
System.out.printf("%x\n", i);
i = (i & 0x03) << 6 | (i & 0x0c) << 2 | (i & 0x30) >> 2 | (i & 0xc0) >> 6;
System.out.printf("%x\n", i);
Output (it is hex, but represents the same numbers):
9b
e6
Since each bit-group (group of 2 bits) has to be moved from its original place in the input, I don't think you can do it in fewer steps (steps as masking and shifting). If this is not fast enough for you, your only option to make it faster is to pre-compute the transformation and store the results in an array as detailed in @ruakh's answer. Of course this becomes unfeasible if we allow more than just 8 bits.
答案2
得分: 2
最快的方法可能是预先计算所有值的表格:
final int[] values = new int[256];
for (int i = 0; i < 256; ++i) {
values[i] = (i & 0b1100_0000) >> 6
| (i & 0b0011_0000) >> 2
| (i & 0b0000_1100) << 2
| (i & 0b0000_0011) << 6;
}
然后使用数组查找而不是位操作。
当然,你会想要进行性能分析。
英文:
The fastest way might be to precompute a table of all the values:
final int[] values = new int[256];
for (int i = 0; i < 256; ++i) {
values[i] = (i & 0b1100_0000) >> 6
| (i & 0b0011_0000) >> 2
| (i & 0b0000_1100) << 2
| (i & 0b0000_0011) << 6;
}
and then use array lookups rather than bit manipulation.
Naturally, you'll want to profile.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论