bit列を奇数列と偶数列にO(log n)で分離する

別に難しくはないし既にありそうだけど、見つからないので一応記事に残しておく。

操作の概要

こんな感じにbit列の奇数番目の列と偶数番目の列を左右に分離する操作を考える。
これは自明にO(n)で処理ができる。各bitを再配置するのに3回程bit演算が必要になるので、 全体で3 x 32 = 96回程度bit演算をすることになる。
Polar符号の文脈ではこの操作のことをReverse Shuffleと呼ぶらしい（よく知らない）。

実装

uint32_t even_odd_separate32(uint32_t x) {
    uint32_t odd  = x & 0b10101010101010101010101010101010;
    uint32_t even = x & 0b01010101010101010101010101010101;
    odd = (odd | (odd << 1)) & 0b11001100110011001100110011001100;
    odd = (odd | (odd << 2)) & 0b11110000111100001111000011110000;
    odd = (odd | (odd << 4)) & 0b11111111000000001111111100000000;
    odd = (odd | (odd << 8)) & 0b11111111111111110000000000000000;
    even = (even | (even >> 1)) & 0b00110011001100110011001100110011;
    even = (even | (even >> 2)) & 0b00001111000011110000111100001111;
    even = (even | (even >> 4)) & 0b00000000111111110000000011111111;
    even = (even | (even >> 8)) & 0b00000000000000001111111111111111;
    return odd | even;
}

仕組みは、bit列を偶奇に分けた後、少しずつスライドする幅を増やしながら隙間を詰めていっているだけなのですぐわかると思う。2進数リテラルを利用しているので、C++14以降でしかコンパイルできないけど、この方が理解しやすいと思うのでこのまま残しておく。

この実装だと、2 + 3 x 8 + 1 = 27回のbit演算で済んでいる。