ビットマップを90度回転させる方法の説明

Question

私は最近that SO questionを見つけました。

Rhubbarbの回答と回答はうまくいきますが、どのように動作するのか分かりません。私は自分のプロジェクトで理解できないコードを使用したくありません。基本的なビット操作（シフト、AND、ORなど）は何かを知っていますが、これらの操作の組み立てがどのように処理しているのか分かりません。

この質問をご覧いただき、ありがたいことに私を助けてくれてありがとうございます。

Answer 1

64ビット整数valueを8×8ブロックとして表されている - のは、次のように、我々は、各セルの「コンテンツ」を理解するだろうふりをしましょう：valueが実際として順次格納されているが

1 2 3 4 5 6 7 8 
9 10 11 12 13 14 15 16 
17 18 19 20 21 22 23 24 
25 26 27 28 29 30 31 32 
33 34 35 36 37 38 39 40 
41 42 43 44 45 46 47 48 
49 50 51 52 53 54 55 56 
57 58 59 60 61 62 63 64 

我々はまた、それをシフトする

に4（ value << 4）の結果によって残されたと言う

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... 

4（value >> 4）で右にシフト0

または

5 6 7 8 9 10 11 12 
13 14 15 16 17 18 19 20 ... 

とは0xFFFFFFFF00000000ull様の作品が少しあり、今

0 0 0 0 1 2 3 4 
    5 6 7 8 9 10 11 12 ... 

のは、ここで

uint64 reflect_vert (uint64 value) 
{ 
    value = ((value & 0xFFFFFFFF00000000ull) >> 32) | ((value & 0x00000000FFFFFFFFull) << 32); 
    value = ((value & 0xFFFF0000FFFF0000ull) >> 16) | ((value & 0x0000FFFF0000FFFFull) << 16); 
    value = ((value & 0xFF00FF00FF00FF00ull) >> 8) | ((value & 0x00FF00FF00FF00FFull) << 8); 
    return value; 
} 

てみましょう提供しますAND演算と組み合わせて、valueからビットを選択するマスク。 また、0xFFは8ビットが設定された1バイトに対応するため、0xFFFFFFFFは4*8=32の選択ビットを効果的に説明しています。各行は8ビット長であるため、これは4行に対応します。

具体的には、value & 0xFFFFFFFF00000000ull選択（保持！）valueの上位32ビット、すなわち、最初の4行、及びvalue & 0x00000000FFFFFFFFullは下位32ビットを選択して最初に破棄しながら、残りを廃棄します。

((value & 0xFFFFFFFF00000000ull) >> 32) 
((value & 0x00000000FFFFFFFFull) << 32) 

で

シフト操作は、下位32ビットまたは上方（<< 32）の位置にこれらのビットをいずれか下向き（>> 32）移動します。それらをOR結合すると、効果的にスワップしたことになります。

value = ((value & 0xFFFFFFFF00000000ull) >> 32) | ((value & 0x00000000FFFFFFFFull) << 32); 

幅16スワップ二列それぞれとのずれを用いて、0xFFFF0000FFFF0000ullと0x0000FFFF0000FFFFullと同じ実行

33 34 35 36 37 38 39 40 \ 
41 42 43 44 45 46 47 48 |__ 
49 50 51 52 53 54 55 56 | | 
57 58 59 60 61 62 63 64/| 
1 2 3 4 5 6 7 8 \ | 
9 10 11 12 13 14 15 16 |__| 
17 18 19 20 21 22 23 24 | 
25 26 27 28 29 30 31 32/

：今下位32ビットはブロックの「下半分」に対応するので、私たちはそうのような行を入れ替え隣人：8スワップ他のすべての行のシフトを有する

49 50 51 52 53 54 55 56 \__ 
57 58 59 60 61 62 63 64/| 
33 34 35 36 37 38 39 40 \__| 
41 42 43 44 45 46 47 48/
17 18 19 20 21 22 23 24 \__ 
25 26 27 28 29 30 31 32/| 
1 2 3 4 5 6 7 8 \__| 
9 10 11 12 13 14 15 16/

最後に、0xFF00FF00FF00FF00ullと0x00FF00FF00FF00FFull、

が得られます

この時点でブロックは正常に垂直に反転されています。

reflect_diagメソッドは、ビットを選択的にスワップする同じ方法を使用します。

0000 0001 0000 0000 
0000 0000 0000 0000 
0000 0000 0000 0000 
0000 0000 0000 0000 

0x0000000000000080ながら（右中央の、下段）八最小を選択

：ここで注意すべきことは、 0x0100000000000000が8最高（中央の左一番上の行）ビットを選択することです

0000 0000 0000 0000 
0000 0000 0000 0000 
0000 0000 0000 0000 
0000 0000 1000 0000 

ビット。それらはちょうど49ビット離れているので、49によってそれらをシフトすると、その位置が入れ替わります。その対応0x0080402010080402が

0000 0000 1000 0000 
0100 0000 0010 0000 
0001 0000 0000 1000 
0000 0100 0000 0010 

を選択し、一方、別の例として

、パターン0x4020100804020100あなたはビット間の距離が全体を可能にするパターンを形成することがわかりますビット

0100 0000 0010 0000 
0001 0000 0000 1000 
0000 0100 0000 0010 
0000 0001 0000 0000 

を選択しますブロックが互いの元の位置と整列するようにシフトされる。

このコードでは、水平および垂直反転されたバージョンと比較して、元の値は上書きされずに新しい出力が作成されます。ミシェルのコードはインプレースでシフトし、シフトを8進数でエンコードするので、>> 010は実際には>> 8を意味し、020は16などを意味します。