2010年4月2日金曜日

ビットスワップ

2kswapを使い, 64ビットj(j5j4j3j2j1j0)2をjπ=(j0j1j2j3j4j5)2に置換したいというfftのビット変換の解も見事であるが, TAOCPの演習問題7.1.3-53にはもっと驚くことが書いてある.

jπ=(j0j1j2j3j4j5)2をさらに一般的にし, jπ=(j(d-1)ψ...jj)2と書く. ここで{0,1,...,d-1}の置換ψがt個の循環を持ち, d-t個の交換(u1v1)...(ud-tvd-t)について(ただしvi>uiとする), この順の積がψになるなら, この順に&mud,v&¬&muuのマスクで(2v-2u)swapをすればビットスワップが出来るというのだ.

完全シャッフルでは 5ψ=0, 4ψ=5, 3ψ=4, 2ψ=3, 1ψ=2, 0ψ=1だから(0 5 4 3 2 1) -> (5 4 3 2 1 0)には0→1→2→3→4→5→0と1個の循環しかないので, (0 1) (0 2) (0 3) (0 4) (0 5)の交換が必要である. 一方fftでは, 5→0→5, 4→1→4, 3→2→3の3個の循環があり, (u v) = (0 5) (1 4) (2 3)でビットスワップが出来ることになる.

それっというので, 早速前回のスワップをやってみる.
δは25-20=31, 24-21=14, 23-22=4で, マスクは

0000000000000000000000000000000010101010101010101010101010101010

0000000000000000110011001100110000000000000000001100110011001100

0000000011110000000000001111000000000000111100000000000011110000

である.

前回のような図も直ぐ書ける.



前回と殆んど同じ推論が出来る.

31swapでは,
右端の"/"を見るとj0=0, j5=0の時, j0は変らず, j5=0も変らず.
左端の"A"を見るとj0=1, j5=1の時, j0は変らず,j5=0も変らず.
右端の2番目"+"を見るとj0=1, j5=0の時, j0は変る, j5=0も変る.
左端の2番目"B"を見るとj0=0, j5=1の時, j0は変る, j5=0も変る.

これを表にしてみると:



なんのことはない, j0'=j5; j5'=j0であった. つまりビットj0とj5が交換できた. 後は推して知るべし. ビットは左右反転できたのである.

面白いなぁ.

0 件のコメント: