ビット演算>ビットマップ 左右反転

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

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

↓ 左右反転

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

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

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

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

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

uint64 reverseHorizontal(uint64 bits)
{
    uint64 t = ((bits >> 4) ^ bits) & 0x0f0f0f0f0f0f0f0f;
    t |= t << 4;     bits ^= t;     // 4ビットごとの交換     t = ((bits >> 2) ^ bits) & 0x3333333333333333;
    t |= t << 2;     bits ^= t;     // 2ビットごとの交換     t = ((bits >> 1) ^ bits) & 0x5555555555555555;
    t |= t << 1;
    bits ^= t;     // 1ビットごとの交換
    return bits;
}

8ビットごとにビット順序を逆にしているのだが、8バイトを並行に処理している。
また、分割統治法により、4,2,1ビットごとに反転処理を行っている。
トータルの論理演算回数は6*3 = 18回だ。

ご理解いただけるであろうか?
反転処理は xor(排他的論理和)を用いたビットの交換 で説明したテクニックを使っている。
よくわからなかった人は復習してきて欲しい。

演習問題:

  1. 上記コードをビルド・実行し、正しく反転されていることを確認しなさい
  2. “d” を左右反転し表示するコードを書きなさい
  3. 左右ではなく上下反転するコードを書きなさい(解答例は次稿)