カテゴリー別アーカイブ: ビット演算

数独データ構造

数独用データ構造の自分用メモ

単純には、char cell[81]; とし、各セルの値を 0~9 で保持すればよい。
が、このようなデータ構造では確定しているセルを探す処理が非効率になる。

一案としては、数値を 0b000000001, 0b000000010, … 0b100000000 で 1~9 を表すことにし、
short cell[81]; でセルの数字を、short candidates[81]; で候補数字をビットパターンで表す方法がある。
こうしておけばビット演算で、確定しているセルを探す処理が効率的になる。

もう一つの方法としては、1つの数字が候補として生きているかどうかを1つのビットボードで表す方法がある。
1つのビットボードを ushort * 9 で表すとすれば、全部の候補は ushort * 9 * 9 なので 182バイトとなる。

ビットフラグが9個あり、1個だけビットが立っている部分を検出 その2

2つの加算は

s1 = b0 ^ b1;
s0 = ~(b0 | b1);

でできる。論理演算の回数は3回だ。
したがって、8個分の加算は 8*3 = 24回
で、加算したものどうし(s01, s11, s02, s12)の加算は

s1 = (s01 & ~s12) | (~s11 & s02);
s0 = s01 & s02;

で可能だ。論理演算の回数は6回だ。
これを3回繰り返せば、8個分の加算が出来る。
合計は 24 + 6*3 = 32回
最後に s1 = (s1 & ~x2) | (s0 & x2) で残ったビットを足せばいいので、全部で論理演算回数は36回となる。

ビットフラグが9個あり、1個だけビットが立っている部分を検出

x0, x1, … x8 にビットフラグが入っていて、フラグが1箇所だけ立っているビットを検出するコード

各ビットの1の個数を数えればいいので、s0 は立っているビットの数が0,s1 は立っているビットの数が1 となるように計算する。

s1 = x0 ^ x1;
s0 = ~x0 & ~x1;

論理演算回数:4

x0 + x1 を計算する。あとは x2, x3, … x8 を足し込んでいけばよい。

s1 = (s1 & ~x2) | (s0 & x2)
s0 = s0 & ~x2;

論理演算回数:5

なので論理演算回数の合計は 4 + 5 * 7 = 39回となる。

ここ に載っているの方法だと32回なので、ちょっと冗長だぞ。

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

下図のように、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だ。
ちょっとむずかしいかもしれないが、ご理解いただけたであろうか?

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

下図のように、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回に減少している。

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

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

下図のように、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. 左右ではなく上下反転するコードを書きなさい(解答例は次稿)

ビット演算>ビットマップ ボールド化

ボールドとは太字のことだ。
下図の様に、ドットがある部分を二重化することで、ボールドとなる。

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

↓ ホールド化

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

uint64 bits に8×8ビットマップデータが入っているとき、それをボールド化するにはどうしたらいいだろうか?

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

void toBold(bool pixel[8][8])
{
    for(int y = 0; y < 8; ++y) {
        for(int x = 8; --x > 0; ) {
            pixel[y][x-1] |= pixel[y][x];
        }
    }
}

2重ループで、論理演算を56回も行う必要がある。

これに対して、ビットマップであれば、以下の1行で済む。

uint64 toBold(uint64 bits)
{
    return ((bits>>1) & 0x7f7f7f7f7f7f7f7f) | bits;
}

基本的には ビットパターンを右にひとつシフトしたものと、もとのパターンの論理和(or)を計算するとよい。
ただし、右端から左端への影響を無くすために、0x7f7f7f7f7f7f7f7f との論理積(and)をとっているというわけだ。
配列を使った場合は56回も必要だった論理演算が、わずか3回で済んでいる。
ビット演算により、ボールド化処理がとんでもなく高速化されるのをご理解いただけたであろうか?

ビット演算>ビットマップ画像表示

今度は逆に、uint64 の 8×8 サイズビットマップ画像が与えられた時に、それを以下のように * . で表示する関数を書く。

........
.*......
.*......
.*......
.*****..
.*....*.
.*....*.
.*****..
void print(uint64 bits)
{
    uint64 mask = (uint64)1 << 63;
    for (int i = 0; i < 8; ++i) {
        for (int k = 0; k < 8; ++k, mask>>=1) {
            if( (bits & mask) != 0 )
                std::cout << "*";
            else
                std::cout << ".";
        }
        std::cout << "\n";
    }
}

演習問題:

  1. 上記コードをビルドし、”b” を表示してみなさい。

ビット演算>ビットマップ画像構築

まずは、下図のようなテキストが与えられたときに、それを数値に変換する関数を書こう。

"00000000"
"01000000"
"01000000"
"01000000"
"01111100"
"01000010"
"01000010"
"01111100"

画像サイズは 8×8 固定とする。なので、数値は64ビットとなるので、型は unsigned __int64 とする。
これは表記が長いので、typedef unsigned __int64 uint64; と型定義しておく。

uint64 binToUInt64(const char *ptr)
{
    uint64 val = 0;
    while( *ptr != '\0' ) {
        switch( *ptr++ ) {
            case '0':
                val *= 2;
                break;
            case '1':
                val = val * 2 + 1;
                break;
        }
    }
    return val;
}

 演習問題:

  1. 上記コードをビルド・実行し、正しく数値に変換されることを確認しなさい
  2. “a” の文字の8×8ピクセル画像を作り、それを数値に変換しなさい。

ビット演算>ビットマップ画像

最近では、フルカラーが普通なので1ピクセルを24bitまたは32bitで表すことが多くなったが、大昔は1ピクセルは1ビットだったので、8ピクセルをまとめて1バイトとすることがあった。
これをビットマップ画像とも呼ぶ

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

例えば、上記は 8×8 で表した “b” だが、これをビットマップにすると、0x004040407c42427c という64ビットの値となる。
ご理解いただけるであろうか?
※ *が1、. が0として2進数→16進数変換を行っている。もしご理解いたけないようであれば こちら で勉強してきて欲しい

というわけで、今回から1ビット/1ピクセルの8×8サイズのビットマップ画像の処理について書いて行こう。