bit 全探索 Java

bit全探索

フラグを立てて部分集合の全列挙をするときに使うそうです. 理解は未だあやふや.
bitのシフト演算の知識と bit演算&の式の理解が必要となります.

概要

部分集合の全列挙
以下のような全体集合があるとします

 { "dog" , "cat" , "bird" };

求めたいものは以下の部分集合,全部です.

{ }
{ "dog" }
{ "cat" }
{ "bird" }
{ "dog"  , "cat" }
{ "dog"  , "bird" }
{ "cat" , "bird"  }
{ "dog" , "cat" , "bird" }

要素数が3個数(dog ,cat , bird) なので, 全体で 2の3乗個の部分集合が存在します.
今回扱う場合は出力順はとわず, 全列挙できれば良いとします, 各要素に注目するとそれぞれ部分集合に含めるか含めいないかの2宅なのでbitをフラグとしてもちいてフラグが立っている場合のみ部分集合に含める操作をします .

bitフラグとの関係

実装

bitのフラグが, 000 , 001 , 010 , 011 , 100 , 101 , 110 , 111 の全てを網羅するように実装する.
重複はあってはなりません.
この 000 ~ 111 の8つの数字は 2進数表記だと思って10進数に変換するとこのようになります.

2進数と10進数

10進数で0 ~ 7を考えて2進数に変換することで 全て網羅することができます.

bitのフラグを10進数を使って全列挙できたので, 要素の抽出へ移ります.
bitが1のところのみ取り出すようにします .
ここでbit演算を使います.

shift演算

   >>

この演算子を用いることでえbitを一つずらすことができます.

shift演算

10進数で表すと , aは 101 (百一) から 50 (五十)に変化しています . ずれた後の左下の空欄部分は0と見なされます.

bit演算 &

   & 

&は, bit単位でみて 共に1の場所を1にする .

and演算

shift演算とand演算を用いることでbit全探索を実装することができます.

implement

for( int  bit = 0; bit < ( 1 << len ) ; bit ++;){
    // len は要素数
    // 処理
}

bit を 2のlen乗通り試す .
1 << len では1をlen回左にシフトしています. len = 3 の場合は , 00001 から左に3つシフトさせるので 01000 となります.
この値より小さい数 00000 , 00001 , 00010 , , , 00111までの8回繰り返されます.

処理部分

for( int  bit = 0; bit < ( 1 << len ) ; bit ++;){
    // len は要素数
    // 処理
    for( int i = 0; i < len; i++){
        if( (bit & ( 1 << i ) != 0 ){
        // 要素に対しての処理
        }
    }
}

for文を要素数(len)回数だけ回します.
if 文の中で 1 << i でbitが立っているかどうかの判定をしています.
i == 0 の時 0001
i == 1 の時 0010
i == 2 の時 0100
隣この2進数bit表記と bitとの &演算を返します. bitの指定した場所が1出ない場合は bit & ( 1 << i )の値が0になります. 逆に0出ない場合は, 0以外の数字隣 if の条件分岐が成り立つため 処理が行われます .

コード例

• BitSearch.java

class BitSearch {
    public static void main(String[] args) {
        String s[] = { "dog", "cat", "bird" };  //全体集合
        int len = s.length;
        for (int bit = 0; bit < (1 << len); bit++) {
            String str = "{";
            for (int i = 0; i < len; i++) {

                if ((bit & (1 << i)) != 0) {
                     // メインの処理部分
                    if (!str.equals("{")) {
                        str += " ,";
                    }
                    str += " " + s[i]; 
                }
            }
            str += " }";
            System.out.println(str);
        }
    }
}

• 出力

$ javac BitSearch.java
$ java BItSearch
{ }
{ dog }
{ cat }
{ dog , cat }
{ bird }
{ dog , bird }
{ cat , bird }
{ dog , cat , bird }

感想

あまり使うことないbit演算なのでこの機会にまとめておいた. フラグ管理などでよく使うらしい

問題例

atcoder.jp