カテゴリー別アーカイブ: C言語

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

下図のように、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サイズのビットマップ画像の処理について書いて行こう。

ビット演算>ビットカウント

条件分岐使わないmax祭りが収まったみたいなので、通常進行に戻って、ビット演算の記事を淡々と書いていこう。
で、今回はビットカウントですよ。

ビットカウントは、与えられた整数を2進数表記した時の1の数を返すものだ。

bitCount(0) = 0
bitCount(1) = bitCount(2) = bitCount(4) = … bitCount(0x80000000) = 1
bitCount(0b1010) = 2
bitCount(0b1111) = 4

という感じだ。

さて、読者はこの int bitCount(unsigned int bits) を何通りの方法で記述できるだろうか?
なお、unsigned int は長いので、以下では typedef unsigned int uint; が定義済みとしてコードを記述する。

ループとマスクを使う方法

int bitCount(uint bits) {
    int cnt = 0;
    for(uint mask = 1; mask != 0; mask<<=1) {
        if( (bits & mask) != 0 )
            ++cnt;
    }
    return cnt;
}

上記コードは、ずっと前に紹介済みだ。
ビット判定をするマスクを 1 から 0x80000000 まで左シフトしながら回し、論理積演算によりビットが1であればカウンターを+1している。
基本の基本なので理解していない人はもう一度基礎を勉強しなおそう。

 if 文無しで、ループを使う方法

int bitCount(uint bits) {
    int cnt = 0;
    for(; bits != 0; bits>>=1) {
        cnt += bits & 1;
    }
    return cnt;
}

今度のコードは前節のものに似ていて、ビット数分ループをするのは同じだが、論理積を行うマスクは 1 固定にし、その代わり引数の方を右シフトしている。論理積の結果は 0 or 1 なので、それをそのままカウンターに足し込んでいるので、if 文を使っていない。

前節の方法は bits が符号付きでも大丈夫だが、この方法は unsigned でないとダメなので、そこんとこは注意して欲しい。

ひとつずつビットを落としていく方法

int bitCount(uint bits) {
    int cnt = 0;
    while( bits != 0 ) {
        ++cnt;
        bits &= bits - 1;       // 一番右の1を0にする
    }
    return cnt;
}

おもしろいことに、bits & bits – 1 を計算すると、2進数表記で一番右の1が0になる(0bxx..x100..0 → 0xbxx..x000..0)。例:0xff → 0xfe, 0x58 → 0x50
1を引くと 0bxx..x100..0 → 0xbxx..x011..1 となり、一番右の1から右のビットが反転する。
X & X = x, x & ~X = 0 という性質があるために、一番右の1が0になるとういわけだ。
ご理解いただけたであろうか?

分割統治法を使った O(Log2 N) な方法

int bitCount(uint bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);    //  2bitごとに計算
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);    //  4bitごとに計算
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);    //  8bitごとに計算
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);    //  16ビットごとに計算   
    return (bits & 0x0000ffff) + (bits >> 16);    //  32ビット分を計算   
}

今度は、いかにもビット演算を使った、という方法。

この方法はビット順序反転のところでも出てきたテクニックとある意味いっしょだ。
処理を2ビットごと、4ビットごと、8ビットごと、16ビットごと、というように処理ビット数を倍々にしていく。
ループで処理を行うとビット数に比例した処理回数が必要だが、この方法なら Log2 N に抑えることが出来る。
分割統治法とも呼ばれる。

 8ビット毎にテーブルを引く方法

int bitCount(uint bits) {
    static int table[256] = {0};
    if( table[1] == 0 ) {
        for (int i = 0; i < 256; ++i) {
             table[i] = bitCount(i);
         }
     }
     return table[bits&0xff] +
                table[(bits>>8)&0xff] +
                table[(bits>>16)&0xff] +
                table[(bits>>24)&0xff];
}

最後に8ビットごとにビットカウントのテーブルを作り、それを引くという方法も書いておく。
テーブルはあらかじめ作っておいてもいいのだが、それが面倒なので、static な配列とし、最初に呼ばれた時に他の関数を利用して初期化するようにした。

 演習問題:

  1. 本稿で紹介したコードが正しく動作することを確認しなさい。
  2. 本稿で紹介した以外の方法を考えなさい。

if文(条件分岐)を使わず、max(a, b) を計算 別解(2)

前項がはてなブックマークされ、大量のアクセスが殺到してます。ありあとうございます。

xor と 比較演算子を使用する方法

で、新たな別解を @n_soda 氏に教えてもらった。
参照:Compute the minimum (min) or maximum (max) of two integers without branching

int max(int a, int b) {
    return a ^ ((a ^ b) & -(a < b));
}

a < b は 1 or 0 なので、符号反転し、0xffffffff or 0 となる。
後は xor の性質を使い、最大値を求めている。

a < b ならば a^((a^b)&0xffffffff) = a^(a^b) = b
a >= b ならば a^((a^b)&0) = a^0 = a

となる。
この方法ならば、オーバーフローの心配もなく、どんな値でも max を求めることが出来る。
素晴らしい。

気になるのは、a < b の部分は条件分岐を使わないのか?という点だ。

VS2013 で Release モードでビルドし、アセンブラコードを見て見ると、以下のようになっていた。

mov ecx,dword ptr [esp+4]   ; ecx := a
xor edx,edx                             ; edx := 0
mov eax,dword ptr [esp+8]   ; eax := b
cmp ecx,eax                           ; a – b を計算し、フラグを立てる
setl dl                                     ; a < b なら edx = 1, a >=b なら edx = 0

なんと、a < b も分岐命令を使わないのだ。setl というのもおいらは知らない命令だったが、条件が成立していたら1を設定するものらしい。3行前であらかじめ edx を 0に設定しているのがミソだ。

つまり、最近のCPU・コンパイラであれば 比較演算子を使っても条件分岐を行わないということみたいじゃ。

比較演算子とテーブルを使用する解

a < b を使っていいのなら、以下の様にテーブルを使う解も当然ありだ。

int max(int a, int b) {
    const int t[] = { a, b };
    return t[a<b];
}

 

if文(条件分岐)を使わず、max(a, b) を計算 別解

前稿をアップしたら、思いの外反響が大きく、facebook、ニコニコ生放送で興味深いレスポンスをいただいたので、ここで紹介する。

a>b を使った解答

C の関係演算子は成立すると1を、不成立だと0を返すので、以下のように記述できる。

return (a>b)*a + (a<=b)*b;

すばらしい。
この解法は清水悠氏らに教えていただいた。

&& を使った解答

C の exp1 && exp2 文は、exp1 が真の時のみ exp2 が評価される。この性質を使うと、以下のように書ける。

return a < b && (a = b), a;

この解答は条件分岐命令を生成するので不可だと考えたのだが、最新のコンパイラ(VS2013, gcc の最新のやつ)でコンパイルすると、なんと cmovecc 命令が生成されるのだ。
cmovecc 命令は、条件が成立している場合のみ move 命令を実行するというもので、分岐をすることが無いので、パイプラインがリセットされることが無いという優れものの命令だ。
実はおいらは x86 にこんな命令が追加されていることを知らなかった。
この解法、cmovessのことも清水悠氏に教えていただいた。大変勉強になりました。thx

 abs(a-b) を使った解答

(a+b)+(a-b) = 2a, (a+b)+(b-a) = 2b なので、以下のようにも書ける

return ((a+b)+abs(a-b)) / 2;

ただし、この書き方はオーバーフローする場合(例えば、0x80000000 が指定された場合)に正しい答えを返さないという問題がある。

この解法は きしだ氏 に教えていただきました。

レスポンスを下さった方々、ありがとうございました。

追記(2014/12/04):さらに別解を教えていただきました。こちらを参照。