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

どうすればそれらを元に戻すことができますか? 1 つの方法は、隣接するペアを交換することです。

8 7 10 9 Q J A K

次に、隣接する 2 のグループを交換します: 8 7 と 10 9 を交換します。

10 9 8 7 A K Q J

最後に、8 の半分のサイズである 4 つのグループを交換します。

A K Q J 10 9 8 7

終わり。

これはさまざまな順序で行うことができます。なんで？交換は互いに安定しているからです。たとえば、カードの上半分と下半分を交換すると、ペアは同じ順序のままになります。または、ペアを交換すると、半分は同じ順序のままです。

これは、コードがビット操作で行っていることです。たとえば、ペアを交換するには、ビットごとの AND 演算を使用して、マスク 01010101 を使用して偶数ビットを選択し、10101010 を使用して奇数ビットを選択できます。

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

and のルールは、特定のビット値 X、X & 1 = X および X & 0 = 0 であることに注意してください。マスクの 1 ビットは値を保持し、マスクの 0 ビットは 0 を生成します。これをマスキングと呼びます。スプレー塗装などで使用されるマスクとまったく同じように見えるためです.1ビットは、「ペイント」したくない場所をゼロで「カバー」します。

次に、左の結果が 1 ビット左にシフトされ、右の結果が右にシフトされます。これにより、スワップが発生します。

  B0D0F0H0     0A0C0E0G

最後に、2 つを論理 OR で結合します。OR のルールは、X または 0 が X であるということです。2 つの部分はそれぞれ 0 で、もう一方は非ゼロであるため、ビットは単純にマージされます。

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

そして今、ペアが交換されています。

于 2012-04-17T03:43:30.927 に答える
8

それは誘導によって理解することができます。

基本ケース、2ビットの数値から始めます

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

次に、4ビットの数値に進みます

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

コードは、最初に 1 つの隣接するビットをスワップし、次に隣接するビットのペアをスワップし、最後に整数のサイズの半分のチャンクがスワップされるまで、毎回スワップのサイズを 2 倍にします。スワップは、移動するビットを 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 に答える