2010年4月1日木曜日

ビットスワップ

3月12日のブログ, ビットスワップの続きである.

2kswapを使い, 64ビットの各ビットj(j5j4j3j2j1j0)2をjπ=(j0j1j2j3j4j5)2で置換したい. そのためのマスクθkを見つけよという問題である(演習問題7.1.3-52).

始めての事ゆえ, 見当もつかず, これもTAOCPの解答を見てみると,

d)0<=k<=5について θk6,k5-k; 0<=k<=2についてθ'kk; θ'3=θ'4=0.

とある. なぜか. 解明したい.

これだけ眺めていても埒があかないので, 64の各ビットがそれぞれのδswapでどこへ移動するかを描いてみた. 幾何の証明の時と同じで出来るだけ正確な図を描くのが肝心である. 幸いとPostScriptがあれば, 一発だ.



この図は
http://www.iijlab.net/~ew/images/bitswapchart.gif

にあるので, これが小さければ, 直接それを見た方がよいかも知れぬ.

δ=1,2,4,8,16,32についての移動パターンは規則的である. 置換πも規則的なので, そうなっても不思議はない.

少し調べてみると, 1swapでは
0****00****1 になり,
0****10****0 になり,
1***** は不変
であることが分かる. *はドントケアを表す.

この伝で他のswapも見たところ

32swap c****t
16swap *c**t*
8swap **ct**
4swap **tc**
2swap *t**c*
1swap t****c
であることが判明した. この読み方で, *はドントケア, tはテストビット, cはチェンジビットで, tが1なら不変, tが0ならcの0と1を変えるのである.

図も規則的だが, ビット変更も規則的である.

さてこれで j5j4j3j2j1j0が j0j1j2j3j4j5になるであろうか.

swapは図のようにδ=1,2,4,8,16,32,4,2,1の順に行う.

1swapではj5=0ならj0は反転し, j5=0ならj0は反転しないから, j'0←j0⊕j5⊕1 と書ける. (変化後のビットにはダッシュ(','')をつけて区別しよう. このように場合を区別するのに, ifを使わず, ⊕などで単一の式で表すのが味噌である.)

同様に, 続く2swap,4swapでj'1←j1⊕j4⊕1; j'2←j2⊕j3⊕1 となる.

次の8swapでも同様にj3が変化するが, これは新しいj'2がtビットなので,
j'3←j3⊕j'2⊕1=j3⊕(j2⊕j3⊕1)⊕1=j2.

同様にして16swapでj'4←j1; 32swapでj'5←j0 となる.

次の4swapではj'2=j2⊕j3⊕1 が新しいj'3つまりj2に従って変化する.
j''2←j'2⊕j'3⊕1=(j2⊕j3⊕1)⊕j2⊕1=j3.

同様にして2swapでj''1←j4; 1swapでj''0←j5 となり, 無事にビットが反転された. QED. めでたしめでたし.

0 件のコメント: