ビットで組み合わせ全列挙

bit演算を使って部分集合を実装

競技プログラミングをやっていると、集合 のべき集合を求めよ～ とか、数列 の部分列の総和を求めよ～とかでできます。

bit演算で簡単に実装できることを学びました。

具体例として、集合 として、 が与えられたとします。
集合Aの部分集合は なので、
べき集合は になります。
これをJavaで実装すると以下のようになります。

import java.util.ArrayList;
import java.util.List;

public class Sample {

    public static void main(String[] args) throws IOException {

        String[] c = {"a", "b", "c"};
        List<String> list = new ArrayList<>();

        for (int i = 0; i < 1 << c.length; i++) {
            StringBuffer sb = new StringBuffer();
            for (int j = 0; j < c.length; j++) {
                if ((i >> j & 1) == 1) {
                    sb.append(c[j]);
                }
            }
            list.add(sb.toString());
        }

        for (int i = 0; i < list.size(); i++) {
            System.out.println(i + ":" + list.get(i));
        }

    }

}

0:
1:a
2:b
3:ab
4:c
5:ac
6:bc
7:abc

確かにlistには集合Aの部分集合が含まれていることがわかります。

ビット演算子、シフト演算子

ビット演算子は以下のように使用できます。
たとえば << であれば、 a << 3 とするとaを左へ3ビットシフトします。
同様に >> であれば、 a >> 3 とするとaを右へ3ビットシフトします。
また、 & は 2つのオペランドのビット積を取ります。
たとえば int整数値の3(2進数で表すと0011)とint整数値の6(2進数で表すと0110)のビット積を取ると
int整数値の2(2進数で0010)になります。

上記の実装では、集合の要素が3であり、1 << 3 によって、ループする回数は8になります。
これは2進数で表すと
000
001
010
011
100
110
101
111
となります。
集合のある要素が含まれる場合を1、含まれない場合を0とすると、
の部分集合を全て表せています。
補足ですが、元の集合の要素の個数が 個のとき、べき集合の要素は 個存在します。
上記実装の if ((i >> j & 1) == 1) { の部分では3桁のビットそれぞれ右へのシフト演算子によってシフトした結果と1のビット積をとることによって 各要素が含まれる場合の処理を実装できています。