【C#】bit全探索を行う

はじめに

今回はbit全探索を実装していこうと思います。

bit全探索とはN 個のものから、選ぶ・選ばない(true,false)を全列挙して調べ上げる手法のことです。

例えば３個の番号がついたボールがあり、選んだときは1(true)，選ばなかったときを0(false)とすると、以下の8通りがあります。

0,0,0
1,0,0
0,1,0
1,1,0
0,0,1
1,0,1
0,1,1
1,1,1

この組み合わせの個数はで表され、なので8通りというわけです。

コード

実際に実装してみたコードはこちら。
(ちなみにbit全探索の英語が「BitFullSerch」であってるかかなり不安です・・・)

public static IEnumerable<bool[]> BitFullSearch(int n)
{
    if (n <= 0)
    {
        yield return new bool[] { };
        yield break;
    }

    for (int i = 0; i < Math.Pow(2, n); i++)
    {
        var array = new bool[n];
        for (int j = 0; j < n; j++)
        {
            var targetBit = (i >> j) & 1;
            if (targetBit == 1) array[j] = true;
        }

        yield return array;
    }
}

使う方法はこんな感じ。

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        int n = 3;
        foreach(var target in BitFullSearch(n))
        {
            Console.WriteLine(string.Join(",", target));
        }
    }

False,False,False
True,False,False
False,True,False
True,True,False
False,False,True
True,False,True
False,True,True
True,True,True

キモになるところ

bit全探索で一番重要なのはこの一行だと思います。

var targetBit = (i >> j) & 1;

この>>は右シフト演算子というもので、数字を２進数で表したときのビットを右にずらし、右ビットを破棄・左ビットに0を加えます。

例えば5 >> 1のイメージはこんな感じ。

この２進数にしたときの1・0をそれぞれtrue・falseに見立ててフラグ管理を行っています。

これはC#だと列挙型とよく一緒に使われる手法ですね。
www.hanachiru-blog.com

加えて& 1とすることで一番右のbitがなんであるかが分かります。

これらが分かればあとはおそらくさほど苦労せずにわかるはずです。

さいごに

実際に実装してみるとやっぱりイテレーターは偉大だなーと思ったりしました。

割と簡潔にまとめることができた気がするので、満足です。

ではまた。