Bit reverse
動作を表す疑似コード
code:bit_reverse
word_size: size of word
src: word_size bits unsigned integer
for i in 0..word_size {
desti = srcword_size-1-i
}
return dest
ビット列の前後を反転させる。MSBはLSBに、LSBはMSBになる。
CPU命令
arm(AArch32, AArch64)ならRBIT
PTXならbrev
x86にはバイト単位のreverseしかなさそう
ソフトウェア実装
2^k bit単位での入れ替えを順次行う
code:bit_reverse.cpp
uint64_t bit_reverse(uint64_t x) {
x = (x >> 32) | (x << 32);
x = ((x >> 16) & 0x0000FFFF0000FFFF) | ((x << 16) & 0xFFFF0000FFFF0000);
x = ((x >> 8) & 0x00FF00FF00FF00FF) | ((x << 8) & 0xFF00FF00FF00FF00);
x = ((x >> 4) & 0x0F0F0F0F0F0F0F0F) | ((x << 4) & 0xF0F0F0F0F0F0F0F0);
x = ((x >> 2) & 0x3333333333333333) | ((x << 2) & 0xCCCCCCCCCCCCCCCC);
x = ((x >> 1) & 0x5555555555555555) | ((x << 1) & 0xAAAAAAAAAAAAAAAA);
return x;
}
もしバイト単位のreverseがあるなら、途中まではそれで置き換えることができる
ハードウェア実装
配線するだけ、とはいえ配線長が長くなると大変…?