C#｜bit全探索

bit全探索の備忘録です。

bit全探索とは

N個のものからいくつか選び取るパターンを全列挙するための手法です。
N個のものからいくつか選び取るパターンは2^N通りあるので、3個のものからいくつか選びとるパターンは、2³通り=8通りとなります。
※1個も選ばないパターンも含みます。

bit列で考える

例えば、りんご(R)・みかん(M)・ばなな(B) の3個の果物があるとします。
この3個の果物をいくつか選び取るパターンを見ていきます。
それぞれ選ばない場合は0、選ぶ場合は1のしるしをつけます。

R | M | B
---------
0   0   0
0   0   1
0   1   0
0   1   1
1   0   0
1   0   1
1   1   0
1   1   1

このように、8通りのパターンを作ることができます。 よく見ると、2進数表記のbit列になっています。
これに10進数表記を追記します。

RMB
---
000  -> 0
001  -> 1
010  -> 2
011  -> 3
100  -> 4
101  -> 5
110  -> 6
111  -> 7

この8通りのbit列それぞれのx桁目が0なのか1なのかが分かれば、8通りのパターンの内訳が分かります。

10進数の6を見ると、1 1 0となっています。この2桁目が 1 であることを知るためには、右に2bitシフトして、0桁目のbitが0なのか1なのかを確認します。

110
011 // まず右に1bitシフト
001 // 続いて右にもう1bitシフト

10進数の6を右に2bitシフトしたbit列を求める場合、C#ではこのように書くことができます。

6 >> 2

// => 001

あとは 001 の0桁目のbitが 1 であることが分かればOKです。
0桁目のbitが0なのか1なのかを確認するためには、AND演算を使います。
AND演算をすると、2つのbit列の各桁ごとのbitを見て、どちらも1の場合のみ1を返し、どちらかが0またはどちらも0の場合は0を返します。
これをうまく使って s & 1 とすれば、sの0桁目のbitが0の場合は0を、1の場合は1を返すので、0桁目のbitを確認することができます。

(6 >> 2) & 1

// => 1

C#でbit全探索

では、先ほどの8通りのbit列それぞれのx桁目が0なのか1なのかを調べて、8通りのパターンの内訳を明らかにしていきます。

int N = 3; // N個のもの
int P = (int)Math.Pow(2, N); // P通りのパターン
var R = new int[P, N]; // 結果を格納する配列

// P通りのbit列を一つずつ確認する
for (int i = 0; i < P; i++)
{
    // 右からx桁目が0なのか1なのかを調べる
    for (int x = 0; x < N; x++)
    {
        var a = (i >> x) & 1;
        R[i, x] = a;
    }
}

結果を格納したRを出力してみます。

for (int i = 0; i < P; i++)
{
    string s = "";

    for (int j = 0; j < N; j++)
    {
        s += R[i, j].ToString();
    }

    Console.WriteLine(s);
}

000
100
010
110
001
101
011
111

ちゃんと8通りのパターンが作成されました。