ビット反転(ビット逆順)をできるだけ速く行うアルゴリズム

ここでは、マイコンを用いたビット反転(ビット逆順, bit reverse)をできるだけ速く行うアルゴリズム(8bit)のちょっとしたメモを残しています。

雑なメモなので、ミスがあるかも。

ビット反転(ビット逆順)は計算コストが高い処理です。

多くのマイコンにはこのビット逆順命令が無いので何かしら計算する必要があります。

なるべく高速に演算したいときはテーブル使うのが良いですが、RAMまたはプログラムメモリを浪費してしまいます。

メモリ消費を削減したい場合は愚直にビット演算するしかありません。

マイコン(もっと言うとCPU)によって、使える命令や実行するのに必要なサイクル数が違うので、どの方法が一番速いかは簡単に比較できません。

input   = hgfedcba //入力する値(h~aはビット7~ビット0に対応)

output  = abcdefgh //出力したい値

アルゴリズム例はメモ帳にコピーすると見やすくなります。

・ローテーション命令なし①

ネット上でよく見るアルゴリズムです。

8bit以外の多バイト値にも拡張しやすいです。

temp    = hgfedcba //入力 tempにinputを代入

temp1   = ____hgfe //tempを4ビット右にシフトした値をrev_iに代入

temp    = dcba____ //tempを4ビット左にシフトした値をtempに代入

temp    = dcbahgfe //tempとtemp1をビット論理和し、tempに代入

temp1   = __ba__fe //tempと0x33をビット論理積をした値をtemp1に代入

temp1   = ba__fe__ //temp1を2ビット左にシフトした値をtemp1に代入

temp2   = dc__hg__ //tempと0xCCをビット論理積をした値をtemp2に代入

temp2   = __dc__hg //temp2を2ビット右にシフトした値をtemp2に代入

temp    = badcfehg //temp1とtemp2をビット論理和したものをtempに代入

temp1   = _a_c_e_g //tempと0x55をビット論理積をした値をtemp1に代入

temp1   = a_c_e_g_ //temp1を1ビット左にシフトした値をtemp1に代入

temp2   = b_d_f_h_ //tempと0xAAをビット論理積をした値をtemp2に代入

temp2   = _b_d_f_h //temp2を1ビット右にシフトした値をtemp2に代入

output  = abcdefgh //temp1とtemp2をビット論理和したものをoutputに代入

結果      abcdefgh //outputの値

*計算コスト*

シフト回数(ローテーション命令なし) : 14

論理積の回数 : 4

論理和の回数 : 3

条件分岐の数 : 0

保持が必要なバイト数の合計 : 3

ローテーション命令(キャリーなし、8bit回転)が無いようなマイコンやC言語だけで記述する場合に良さそうです。

・ローテーション命令なし②

よくあるアルゴリズムです。

temp   = hgfedcba //inputをtempに代入

rev_i   = ____hgfe //tempを4ビット右にシフトした値をrev_iに代入

temp    = dcba____ //tempを4ビット左にシフトした値をtempに代入

rev_i   = dcbahgfe //tempとrev_iをビット論理和し、rev_iに代入

temp    = _dcbahgf //rev_iを1ビット右にシフトした値をtempに代入

output  = __c___g_ //tempと0x22をビット論理積し、outputに代入

temp    = ___dcbah //tempを2ビット右にシフトした値をtempに代入

output |= ___d___h //tempと0x11をビット論理積し、outputと論理和を行い、outputに代入

temp    = cbahgfe_ //rev_iを1ビット左にシフトした値をtempに代入

output |= _b___f__ //tempと0x44をビット論理積し、outputと論理和を行い、outputに代入

temp    = ahgfe___ //tempを2ビット左にシフトした値をtempに代入

output |= a___e___ //tempと0x88をビット論理積し、outputと論理和を行い、outputに代入

結果      abcdefgh //outputの値

*計算コスト*

シフト回数(ローテーション命令なし) : 14

論理積の回数 : 4

論理和の回数 : 4

条件分岐の数 : 0

保持が必要なバイト数の合計 : 3

①とほぼ同じです。

違いは7~4bitと3~0bitのスワップ以降の手順です。

論理和の演算回数が①より一回多いですが、トータルの計算速度で見るとどちらが速いかわかりません。

ローテーション命令(キャリーなし、8bit回転)が無いようなマイコンやC言語だけで記述する場合に良さそうです。

・ローテーション命令あり(キャリーなし、8bit回転)

temp   = hgfedcba //inputをtempに代入

temp    = gfedcbah //inputを1ビット左にローテーションした値をtempに代入

output  = ___d___h //tempと0x11をビット論理積をした値をoutputに代入

temp    = edcbahgf //tempを2ビット左にローテーションした値をtempに代入

output |= __c___g_ //tempと0x22をビット論理積し、outputと論理和を行い、outputに代入

temp    = ahgfedcb //inputを1ビット右にローテーションした値をtempに代入

output |= a___e___ //tempと0x88をビット論理積し、outputと論理和を行い、outputに代入

temp    = cbahgfed //tempを2ビット右にローテーションした値をtempに代入

output |= _b___f__ //tempと0x44をビット論理積し、outputと論理和を行い、outputに代入

結果      abcdefgh //outputの値

*計算コスト*

ローテーション回数(キャリーなし、8bit回転) : 6

論理積の回数 : 4

論理和の回数 : 3

条件分岐の数 : 0

保持が必要なバイト数の合計 : 3

ローテーション命令(キャリーなし、8bit回転)がある場合(Z80など)に良さそうです。

使用するレジスタも少なくそれなりに高速です。

シフト命令のみの時より速そうですね。