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

这是如何运作的？

4

5 回答 5

16

假设我有一手 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 来挑选偶数位，使用掩码 10101010 来挑选奇数位，使用按位与运算：

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

请记住，and 的规则是给定一些位值 X，X & 1 = X 和 X & 0 = 0。掩码中的 1 位保留该值，掩码中的 0 位产生 0。这称为掩码因为它看起来就像在喷漆等中使用的面具。1 位“覆盖”你不想用零“绘画”的地方。

接下来，左结果左移一位，右结果右移。这带来了交换：

  B0D0F0H0     0A0C0E0G

最后，将两者与逻辑或结合起来。OR 的规则是 X 或 0 是 X。这两个部分各有 0，而另一个有非零，因此这些位简单地合并：

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

现在这些对被交换了。

于 2012-04-17T03:43:30.927 回答
8

可以通过归纳来理解。

从基本情况开始，一个两位数

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

等等。

于 2012-04-17T02:15:59.783 回答
8

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

下面的动画有助于可视化正在发生的事情，记住虽然交换大小按顺序增加，但每个大小的所有交换都是并行发生的。

交换

于 2012-04-17T15:30:51.527 回答
3

让b[0], b[1], b[2], ..., b[31]是input从最低有效位开始的位。然后b[1], b[0], b[3], b[2], ..., b[31], b[30]将是位

input = (input & 0x55555555) <<  1 | (input & 0xAAAAAAAA) >>  1;

基本上，它交换input. 类似地，其他 4 行交换相邻对、4 组、8 组，最后是 16 位组。

于 2012-04-17T02:12:30.687 回答
0 
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;
     printf("\nvalue = %x",input);
     return input;
}

int _tmain()
{
    // TODO: Please replace the sample code below with your own.

    int value;
    signed int res,bit;
    signed int stPos, len;
    value = 0x12345678;

    reverse_bits(value);
    printf("\nvalue = %x",value);
    char buffer [33];
    itoa (value,buffer,2);
    printf ("\nbinary: %s\n",buffer);

    return 0;
}
于 2012-10-17T08:20:46.883 回答