このコードはどのようにビット数を反転させることができますか？

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 

最後に、半分の4の交換基、一つの方法は、隣接する対を交換することですサイズ8：

A K Q J 10 9 8 7 

完了しました。

これは異なる順序で行うことができます。どうして？お互いの交換はであるので、です。たとえば、カードの上半分を下半分と交換すると、ペアは同じ順序にとどまります。あるいは、ペアを交換するとき、半分は同じ順序にとどまります。

これはコードがビット操作で行っていることです。インスタンスがペアを交換するために我々は、偶数ビットを取り出すためにマスク01010101を使用すると、10101010奇数ビットを選び出すために、ビット単位のAND演算使用することができます

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

は覚えておいて、ルールを、いくつかを与えられたということですマスク内の1ビットは値を保持し、マスク内の0ビットは0を生成する。これは、スプレーで使用されるマスクのように見えるので、マスキングと呼ばれるペイントなど.1ビットは、 "ペイント"したくない場所をゼロで "カバー"します。

次に、左の結果が1ビット左にシフトされ、右の結果が右にシフトされます。これは交換についてもたらします：

B0D0F0H0  0A0C0E0G 

最終的に、2つは論理ORと組み合わされます。

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

今ペアが交換された：ORのルールは、Xまたは0は、2つの部分それぞれは、他が非ゼロ有し0を有し、従ってビットは単にマージX.であることです。

Answer 2

b[0], b[1], b[2], ..., b[31]は、最下位ビットから始まるビットがinputであるとします。次いでb[1], b[0], b[3], b[2], ..., b[31], b[30]は基本的に、それはinputの隣接ビットをスワップ

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

のビットであろう。同様に、他の4本の線は、隣接する対、4の群、8の群、および最後に16ビットの群を交換する。

Answer 3

誘導によって理解できます。

ベースケースとスタート、2ビット数

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

次に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 

などに4ビット数

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

進行する進行しますに。

Answer 4

コードは最初に1つの隣接ビットをスワップし、隣接するビットのペアをスワップします。最後にスワップのサイズが整数の半分になるまでスワップのサイズを2倍にします。スワッピングは、移動するビットをANDでマスクし、それらをシフトして結果をOR演算することによって行われます。

以下のアニメーションは、スワップサイズが順次増加する間に、各サイズのすべてのスワップが並行して発生することを想起させるのに役立ちます。

Answer 5

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