反转整数 x 中的位
位反转
我发现这段代码用于反转整数 x 中的位（假设为 32 位值）：
unsigned int
reverse(register unsigned int x)
{
x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
return((x >> 16) | (x << 16));
}
我无法理解这段代码背后的逻辑/算法。所有神奇数字的目的是什么？
Bit Reversal
I found this code for reversing the bits in an integer x (assume a 32bit value):
unsigned int
reverse(register unsigned int x)
{
x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
return((x >> 16) | (x << 16));
}
I am unable to understand the logic/algorithm behind this code. What is the purpose of all the magic numbers?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
让我们看看它是如何处理 8 位值的：
函数中的第一行采用每隔一个位并将其向左或向右移动：
第二行采用两位一组并向左或向右移动：
第三行采用四位一组位并向左或向右移动：
现在位被反转。对于 32 位值，您还需要两个步骤来移动 8 和 16 组中的位。
Let's look at how it's done for an 8 bit value:
The first line in the function takes every second bit and moves it left or right:
The second line takes groups of two bits and moves left or right:
The third line takes groups of four bits and moves left or right:
Now the bits are reversed. For a 32 bit value you need two more steps that moves bits in groups of 8 and 16.
那是位掩码。将它们写成二进制形式并记住按位与的工作原理。您还可以拿一张纸写下每个步骤的掩码、输入和结果来进行整理。
That's bit masks. Write them in binary form and remember how
bitwise andworks. You can also take a piece of paper and write down every step's masks, input and result to sort it out.