unsigned reverse_bits(unsigned input)
{
//works on 32-bit machine
input = (input & 0x55555555) << 1 | (input & 0xAAAAAAAA) >> 1;
input = (input & 0x33333333) << 2 | (input & 0xCCCCCCCC) >> 2;
input = (input & 0x0F0F0F0F) << 4 | (input & 0xF0F0F0F0) >> 4;
input = (input & 0x00FF00FF) << 8 | (input & 0xFF00FF00) >> 8;
input = (input & 0x0000FFFF) << 16 | (input & 0xFFFF0000) >> 16;
return input;
}
这是如何运作的？
假设我有一手8张牌：
7 8 9 10 J Q K A
我们怎样才能逆转它们呢？一种方法是交换相邻对：
8 7 10 9 Q J A K
然后，交换相邻的 2 组：交换 8 7 和 10 9 等：
10 9 8 7 A K Q J
最后，四人一组交换，这是 8 人的一半：
A K Q J 10 9 8 7
Done.
您可以按不同的顺序执行此操作。为什么？因为交换是stable彼此尊重。例如，当我们将卡片的上半部分与下半部分交换时，两对卡片的顺序保持不变。或者当我们交换对时，两半保持相同的顺序。
这就是代码对位操作所做的事情。例如，要交换对，我们可以使用掩码 01010101 来挑选偶数位，使用 10101010 来挑选奇数位，使用按位 AND 运算：
ABCDEFGH ABCDEFGH
& 01010101 & 10101010
---------- ----------
= 0B0D0F0H A0C0E0G0
请记住， 和 的规则是给定某个位值 X，X & 1 = X 且 X & 0 = 0。掩码中的 1 位保留该值，掩码中的 0 位生成 0。这称为掩码因为它看起来就像喷漆等中使用的遮罩。1 位“覆盖”您不想用零“绘制”的地方。
接下来，左结果左移一位，右结果右移。这带来了交换：
B0D0F0H0 0A0C0E0G
最后将两者用逻辑或结合起来。 OR 的规则是 X 或 0 是 X。这两部分各有 0，另一部分有非零，因此这些位简单地合并：
B0D0F0H0
| 0A0C0E0G
----------
= BADCFEHG
现在这两对交换了。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
