Cortex-M3以上でN == 2^n判定とビット列反転

気分転換になんの気無しに彷徨ってて見つけた記事。
FFT: ビット列反転インデックス - Qiita
面白そうなのでやってみた。

Cortex-M3以上なら動くはず(未実装のコアで使おうとするとソフトウェア実装が呼ばれるのでかなり遅くなる)。

N == 2^nの判定

CLZ命令(Count Leading Zeros Cortex)で一番上のセットされたビットを探せる。
0x8000'0000を右シフトしてNと比較、あるいはNを左シフトして0x8000'0000と比較、で判断できる。

const bool a = N == (0x8000'0000 >> __CLZ(N));
const bool b = 0x8000'0000 == (N << __CLZ(N));

即値をシフトする分前者が有利?
アセンブリで書くならもうちょっといいやり方がありそう。

ビット列反転

__RBIT命令で32bit内の上下反転ができる。
__CLZ(N - 1)で右シフトすべき量が得られる。

const int K = __CLZ(N - 1);

for (uint32_t i = 0; i < N; i++)
{
    const uint32_t ri = __RBIT(i) >> K;
}

感想

ビット演算命令つよい

そういえば、CMSISのFFTライブラリでビットリバーサルしないモードってのがあって、何に使うんだろうと思ってたけど、こういうのを組み合わせて使えばいいわけか。LUT[i]でアドレスを変換するより、__RBIT(i) >> Kのほうが早そうな気もする? でもビットリバーサルしないモード使うなら定数で指定しそう。

おまじない

まちがってたらごめんね