ビット演算>ビットマップ 上下反転

下図のように、8×8ビットマップ画像を上下反転する関数 uint64 reverseVertical(uint64 bits) はどう書いたらいいだろうか?

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

↓ 上下反転

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

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

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

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

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

uint64 reverseVertical(uint64 bits)
{
    uint64 t = ((bits >> 32) ^ bits) & 0x00000000ffffffff;;
    t |= t << 32;
    bits ^= t;     // 上4行と下4行を交換
    t = ((bits >> 16) ^ bits) & 0x0000ffff0000ffff;
    t |= t << 16;
    bits ^= t;     // 2行ごとの交換
    t = ((bits >> 8) ^ bits) & 0x00ff00ff00ff00ff;
    t |= t << 8;
    bits ^= t;     // 1行ごとの交換
    return bits;
}

1行内のビット順序は変化しない。
分割統治法により、4,2,1行ごとに反転処理を行っている。
単純にループで処理すると6*4=24回の論理演算処理が必要だが、
分割統治法によりトータルの論理演算回数が6*3 = 18回に減少している。

ご理解いただけるであろうか?