这段代码如何反转位数？

Question

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;
}

这是如何运作的？

Answer 1

假设我有一张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

完成.

您可以按不同的顺序执行此操作.为什么？因为交换相对于彼此是稳定的.例如,当我们将卡片的上半部分与下半部分交换时,这些卡片保持相同的顺序.或者当我们交换对时,这两半保持相同的顺序.

这就是代码在位操作中所做的事情.例如,对于交换对,我们可以使用掩码01010101来选择偶数位,使用按位AND运算来使用10101010来挑出奇数位:

  ABCDEFGH     ABCDEFGH
& 01010101   & 10101010
----------   ----------
= 0B0D0F0H     A0C0E0G0

请记住,和的规则是给定一些位值X,X&1 = X和X&0 = 0.掩码中的1位保留该值,掩码中的0位产生0.这称为掩码因为它看起来就像喷涂等中使用的面具.1位"覆盖"你不想"涂"零的地方.

接下来,左边的结果向左移动一位,右边的结果向右移动.这带来了交换:

  B0D0F0H0     0A0C0E0G

最后,两者结合逻辑OR.OR的规则是X或0是X.这两个部分各有0,而另一个非零,所以这些位只是合并:

  B0D0F0H0
| 0A0C0E0G
----------
= BADCFEHG

现在交换了对.

Answer 2

通过归纳可以理解.

从基础案例开始,两位数

input = (input & 0x1) <<  1 | (input & 0x2) >>  1;

现在进展到四位数

input = (input & 0x5) <<  1 | (input & 0xA) >>  1; // swap bits
input = (input & 0x3) <<  2 | (input & 0xc) >>  2; // swap bit pairs

进展到8位数

input = (input & 0x55) <<  1 | (input & 0xAA) >>  1; // swap bits
input = (input & 0x33) <<  2 | (input & 0xCC) >>  2; // swap bit pairs
input = (input & 0x0F) <<  4 | (input & 0xF0) >>  4; // swap bit nibbles

等等.

Answer 3

代码首先交换单个相邻的位,然后是相邻的位对,依此类推,每次将交换的大小加倍,直到最后交换整数大小的一半的块.交换是通过屏蔽要用AND移动的位,移动它们然后将结果进行OR运算来完成的.

下面的动画有助于可视化正在发生的事情,记住当交换大小按顺序增加时,每个大小的所有交换都是并行发生的.