请问这个code工作，以扭转位数？ [英] How does this code work to reverse bits in number?

问题描述

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

是如何工作的？

推荐答案

假设我有800张牌：

7 8 9 10 J Q K A

我们可如何扭转呢？一种方法是交换相邻对

How can we reverse them? One way is to swap adjacent pairs:

8 7 10 9 Q J A K

然后，交换两个相邻组：交易所8 7和10 9，等：

Then, swap adjacent groups of 2: exchange 8 7 and 10 9, etc:

10 9 8 7 A K Q J

最后，四个交换基，它是8的一半大小

Finally, exchange groups of four, which is half the size of 8:

A K Q J 10 9 8 7

完成。

您可以按不同的顺序执行此操作。为什么？因为交流是的稳定的相对于对方。当我们与下半部交换的卡的上半部分，例如，在对停留在相同的顺序。或者，当我们交换对，一半留在相同的顺序。

You can do this in different orders. Why? Because the exchanges are stable with respect to each other. When we exchange the upper half of the cards with the lower half, for instance, the pairs stay in the same order. Or when we exchange pairs, the halves stay in the same order.

这是什么code与位操作做。例如交换对，我们可以使用面膜01010101挑选出偶数位，10101010挑出来的边角余料，采用位与操作：

This is what the code is doing with the bit operations. For instance to swap pairs we can use the mask 01010101 to pick out the even bits, and 10101010 to pick out the odd bits, using the bitwise AND operation:

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

记住，对于规则是，给予一定的位值X，X放大器; 1 = X和X安培; 0 = 0在掩模preserve的1个位的值，并且在掩模的0位产生0。这是所谓的掩蔽，因为它看起来酷似于喷漆使用的掩模等。1比特覆盖漆你不想要的地方零。

Remember, the rule for and is that given some bit value X, X & 1 = X and X & 0 = 0. The 1 bits in the mask preserve the value, and the 0 bits in the mask produce 0. This is called masking because it looks exactly like a mask used in spray-painting, etc. The 1 bits "cover" the places you don't want to "paint" with zero.

接着，将左结果左移一位，并在正确的结果向右移位。这带来的调剂：

Next, the left result is shifted left one bit, and the right result shifted right. This brings about the swap:

  B0D0F0H0     0A0C0E0G

Finaly，两者相结合，与逻辑OR。对于规则或是X或0 X.两个部分各有0，如果另一方有非零，所以干脆位合并：

Finaly, the two are combined with logical OR. The rule for OR is that X or 0 is X. The two parts each have 0 where the other has nonzero, and so the bits simply merge:

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

和现在对被调换了。

这篇关于请问这个code工作，以扭转位数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！