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

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

条件分岐使わない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):さらに別解を教えていただきました。こちらを参照。

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

通常、int max(int a, int b) は以下のように実装される(非テンプレートの場合)。

int max(int a, int b)
{
    return a > b ? a : b;
}
int max(int a, int b)
{
    if( a > b )
        return a;
    else
        return b;
}

これを if文, ?: を使わずに書くにはどうしたらいいだろうか?

実はビット演算を使うとそれが出来てしまうのだ。

答えは以下のとおり(int は 32bit 符号付き整数と仮定)。

int max(int a, int b)
{
    int t = (a - b) >> 31;  // a>=b ならば0, a<b ならば 0xffffffff
    return (a & ~t) | (b & t);
}

符号付き整数を右シフトすると、最上位の符号ビットが維持されたままになる性質を利用している。
ご理解いただけたであろうか?

if文を使わずこんなことをしていったい何の意味があるのかと懐疑的な読者もいることだろう。
実は最近のCPUはパイプライン+分岐予測を行っているので、条件分岐があり、分岐予測に失敗すると、パイプラインをクリアする必要があり、処理が遅くなることがあるのだ。
条件分岐を使わず論理演算だけで済ますと、そういうことがなく処理が高速になることがある。

また、ある種の並列マシンでは、データは並列CPUでアクセスできるのだが、プログラムカウンタが共通、という仕様のものがあるのだそうだ。そういうマシンでは各データごとで異なる条件分岐を行うことができないので、このようなテクニックを使わざるをえないのだそうじゃ。

追記(2014/12/03):

別解も書きましたよ

ニコ生でM氏に、オーバーフローする場合があるというご指摘をいただいだ。
たしかに、a, b の差が0x7fffffff を越えていると、結果が正しくならないようだ。

 

 

ビット演算>ビット順序反転 xor 版

前稿では、ループを and or を用いてビット順序を反転するコードを示した。
本稿では、xor を用いたビット交換を繰り返し行うことでビット順序を反転するコードを紹介する。

まずは2ビットの場合を考えよう。
この場合は、ビット交換テクニックにより交換すればよい。

int x = 2ビットの値;
int t = ((x >> 1) ^ x) & 1;
t |= t << 1;
x ^= t;

これは以前説明した通りだ。
では、次に4ビットの場合はどうするか?

実は上位2ビットと下位2ビットを交換し、ついで隣り合う1ビット同士を交換すると、ビット順序が反転するのだ。

と言われても、はあ?と思う方がほとんどだと思うので、例を示そう。
各ビットの値を a, b, c, d とすると、初期状態は abcd だ。
上位2ビット(ab)と下位2ビット(cd)を交換すると cdab となる。
ついで、隣り合う1ビット同時を交換すると、dcba となる。

どうだい、ちゃんとビット順序が反転しただろ。

これをコードで書くと以下のようになる。

int x = 4ビットの値;
// 上位2ビットと下位2ビットの交換
int t = ((x >> 2) ^ x) & 3;
t |= t << 2; x ^= t; // 隣り合う1ビットの交換 t = ((x >> 1) ^ x) & 1;
t |= t << 1;
x ^= t;

同様にして、32ビットの順序を反転したい場合は、まず上位16ビットと下位16ビットを交換し、ついで8ビットごとに交換、4ビットごとに交換、2ビットごとに交換、1ビットごとに交換、とすればよいのだ。
1回の交換では論理演算を6回行うので、合計30回の論理演算しか行わない。
ループの場合は平均して80回の倫理演算だった。単純に言えば2倍以上高速ということだ。

int x = 32ビットの値;
// 上位16ビットと下位16ビットの交換
int t = ((x >> 16) ^ x) & 0xffff;
t |= t << 16; x ^= t; // 8ビットごとの交換 t = ((x >> 8) ^ x) & 0x00ff00ff;
t |= t << 8; x ^= t; // 4ビットごとの交換 t = ((x >> 4) ^ x) & 0x0f0f0f0f;
t |= t << 4; x ^= t; // 2ビットごとの交換 int t = ((x >> 2) ^ x) & 0x33333333;
t |= t << 2; x ^= t; // 隣り合う1ビットの交換 t = ((x >> 1) ^ x) & 0x55555555;
t |= t << 1;
x ^= t;

演習問題:

  1. 上記コードをビルドし、ビット順序が正しく反転されることを確認しなさい。
  2. 本稿のテクニックを使って、64ビット整数のビット順序を反転するコードを書きなさい。
  3. 上記コードがループでビット順序反転を行う場合に比べてどの程度高速かを計測しなさい。

ビット演算>ビット順序反転

int x; に何らかの値が入っているとき、最上位ビットから最下位ビットまでの順序を反転(0x01234567 → 0xe6a2c480)するにはどう書いたらいいだろうか?

ループと論理積を使えば、以下のように書くことができる。

int x = 何らかの値;
int t = 0;
for(unsigned int mask = 0x80000000; mask != 0; mask>>=1) {
    t <<= 1;    //  結果を1ビット左シフト
    if( (x & mask) != 0 )   //  x の当該ビットが立っていれば
        t |= 1;    //  結果のビットを立てる
}
x = t;    //  結果を x に格納

ループは int のビット数分なので、32回。1回のループでは論理演算が2回または3回だ。
平均2.5回だとすると、合計80回の論理演算ということになる。

このコードで何も問題なさそうだが、実は前稿で紹介したビット交換テクニックを使うと演算回数を大幅に減らせるのだ。
実際にどうやるかは次稿で。

ビット演算>xor(排他的論理和)を用いたビットの交換(2)

前稿 では、異なる変数の同じ位置のビットを交換したが、ひとつの変数内のビットを交換することも出来るぞ。
下記は、変数 x の下位4ビット(bit0~bit3)とその上4ビット(bit4~bit7)を交換するコードだ。

x = 何らかの値;
int t = (x ^ (x >> 4)) & 0xf;    //  x の下位4ビットとその上4ビットの xor を計算
t |= t << 4;    //  xor 値を bit4~bit7 にもコピー
x ^= t;    // xor を取ることでビットを交換

論理演算の回数はわずか6回だ。
どうだい、こんな簡潔なコードでビットの交換ができるなんて感激しないか?

 演習問題:

  1. 上記コードをビルド・デバッガで実行し、ビットが交換されていることを確認しなさい。
  2. 論理積と論理和を使って上記と同じコードを書いてみなさい。
  3. 変数x の bit4~bit7 と bit12~bit15 を交換(x = 0x1234; ならば x = 0x3214 となる)するコードを書きなさい。

ビット演算>xor(排他的論理和)を用いたビットの交換

前稿 で、and, or を用いたビット交換方法を示したが、xor を用いると、より簡潔に書けるぞ。

int x = 何らかの値;
int y = 何らかの値;
const int t = (x ^ y) & 0xf;   //  x と y の下位8ビットの xor
x ^= t;    //  下位8ビットが x^(x^y) = y になる
y ^= t;    //  下位8ビットが y^(x^y) = x になる

どうだろう?ご理解いただけるであろうか?
前稿の方法と比べて、非常に簡潔になったでしょ。

交換したい部分の xor(排他的論理和)をとり、それを元の変数に xor することで、ビットを交換できるということだ。

筆者がはじめてこのテクニックを見たときはかなりびっくりした。言われてみればあたりまえなのだが、ビットを交換するときに方法が思いつかず、前稿の方法を使っていたからだ。

演習問題:

  1. 上記コードをビルド・デバッガで実行し、正しく交換されることを確認しなさい。

ビット演算>and(論理積), or(論理和)を用いたビットの交換

int x, int y に何らかの値が入っている時、下位8ビットの値を交換するコードは以下のように記述することが出来る。

int x = 何らかの値;
int y = 何らかの値;
const int mask = 0xf;    // 交換する部分のマスク
int tx = x & mask;    // x の下位8ビットを取り出す → tx に保存
int ty = y & mask;    // y の下位8ビットを取り出す → ty に保存
x &= ~mask;    // x の下位8ビットを0に
x |= ty;    // x の下位8ビットを y の下位8ビットの値にする
y &= ~mask;    // y の下位8ビットを0に
y |= tx;    // y の下位8ビットを x の下位8ビットの値にする

これまでに説明した、論理積・論理和のテクニックを使用している。ご理解いただけるであろうか?
よくわからない人はこれまでの解説を是非読み返して欲しい。

演習問題:

  1. 上記コードをビルドし、デバッガで動きを確認しなさい。

ビット演算>xor(排他的論理和)を使った値の交換

ここまでは基礎編だったが、ここからは中級編だ。少し難しくなるかもしれない。
が、マスターすれば便利な機能なので、ぜひマスターしてワンランク上のビット演算氏になってもらいたい。

排他的論理和 のところで一応説明したのだが、もう一度書いておくと、排他的論理和には以下の様な性質がある。

  • x ^ 0 = 0 ^ x = x   // 0 との排他的論理和は値を変えない
  • x ^ x = 0    // 同じものを xor すると結果は 0
  • (x ^ y) ^ z = x ^ (y ^ z)   // 結合法則
  • x ^ y = y ^ x    // 交換法則

なので、 (x ^ y) ^ x = (y ^ x) ^ x = y ^ (x ^ x) = y ^ 0 = y となる。

この性質を使うと、下記のコードで2つの変数を入れ替えることが出来る。

int x = 何らかの値;
int y = 何らかの値;
x ^= y;
y ^= x;
x ^= y;

狐に摘まれた方も少なくないと思うが、上記のコードで x, y に入っている値はしっかり入れ替わる。

x,y の初期値を x0, y0 として説明する。
最初に x ^= y; を実行すると、x には x0 ^ y0 が入る。
次に y ^= x; を実行すると、y0 ^ (x0 ^ y0) = x0 なので、y には x の初期値 x0 が入る。
次に x ^= y; を実行すると、x には (x0 ^ y0)、y には x0 が入っているので、(x0 ^ y0) ^ x0 = y0 となり、x には無事 y0 が入り、x と y の値が交換されることになる。

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

演習問題:

  1. 変数の値を入れ替えるコードをビルド・デバッガで実行し、本当に中身が入れ替わることを確認しなさい。