ビット演算>ビットマップ 転置

下図のように、8×8ビットマップ画像を転置(行・列入れ替え)する関数 uint64 taransose(uint64 bits) はどう書いたらいいだろうか?

........
.*......
.*......
.*......
.*****..
.*....*.
.*....*.
.*****..

↓ 転置

........
.*******
....*..*
....*..*
....*..*
....*..*
.....**.
........

もし、8×8画像をビットマップを使わず bool pixel[8][8]; で表現していた場合、転置処理は以下のように書ける。

void reverseHorizontal(bool pixel[8][8])
{
    for(int y = 0; y < 7; ++y) {
         for(int x = y + 1; x < 8; ++x) {
            std::swap(pixel[y][x], [x][y]);
        }
    }
}

2重ループで、swap演算を28回行う必要がある。

これをビット演算で行うと、以下のように記述できる。

uint64 transpose(uint64 bits)
{
    //  右上4x4と左下4x4を転置
    uint64 t = ((bits >> 28) ^ bits) & 0x00000000f0f0f0f0;
    t |= t << 28;
    bits ^= t;
    //  4x4 の中の、右上2x2と左下2x2を転置
    t = ((bits >> 14) ^ bits) & 0x0000cccc0000cccc;;
    t |= t << 14;
    bits ^= t;
    //  2x2 の中の、右上と左下を転置
    t = ((bits >> 7) ^ bits) & 0x00aa00aa00aa00aa;;
    t |= t << 7;
    bits ^= t;
    return bits;
}

これも、分割統治法を使い、4x4, 2x2, 1x1 サイズの矩形を右上、左下で入れ替えるとOKだ。
ちょっとむずかしいかもしれないが、ご理解いただけたであろうか?