メモ：ビットリバースの効率的な実装

ビットの順番を入れ替えたくなった時に、いい感じの計算方法がすぐには見つからなかったので、どこかのサイトで見つけたやつをここにメモしておく。FFTとかで使えるゾ。

実装のノリはFFTのバタフライ演算から実際の計算を取り除いたみたいな感じかしら。

uint32_t bit_reverse(uint32_t b) {
   b = (b & 0xffff0000) >> 16 | (b & 0x0000ffff) << 16;
   b = (b & 0xff00ff00) >> 8 | (b & 0x00ff00ff) << 8;
   b = (b & 0xf0f0f0f0) >> 4 | (b & 0x0f0f0f0f) << 4;
   b = (b & 0xcccccccc) >> 2 | (b & 0x33333333) << 2;
   b = (b & 0xaaaaaaaa) >> 1 | (b & 0x55555555) << 1;
   return b;
}

uint8_t bit_reverse(uint8_t b) {
   b = (b & 0b11110000) >> 4 | (b & 0b00001111) << 4;
   b = (b & 0b11001100) >> 2 | (b & 0b00110011) << 2;
   b = (b & 0b10101010) >> 1 | (b & 0b01010101) << 1;
   return b;
}

特定のbit幅Wとかで反転したい時は以下みたいな感じで使う。

uint32_t i_reversed = bit_reverse(i << (32 - W));