bit全探索【Java,Python】

理解するのに苦労したので、忘れないようにメモ。

使い所

選択する or 選択しないの2択を組み合わせ全探索するとき。

参考サイト

qiita.com

algo-method.com

Java

「1 << N」 は２のN乗。

「S & (1 << i))」は整数Sを2進数とみなして、下からi桁目が1か判定。

簡単に言うと、８通り全探索したいなら、0～8を順番に2進数に変換して、１になったとこだけ選択する。

import java.io.IOException;
import java.util.Scanner;

//Q2. 部分和問題　https://algo-method.com/tasks/1083
public class BitEnzanBubunwa {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int v = sc.nextInt();
        int[] a = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();

        }
        /* N個の数字の中から、１つ以上選ぶ組合せを全探索したい。
        * 全探索のパターン数は下記。
        * 例：N=3 (1 << 3) = 2の3乗 = 8; ３個の数字の選択パターンは全部で８通り。
        * 
        * 問題に合わせて読み替えると
        * N個の整数が与えられたので、全探索するには何通り調べればよいか知りたい。
        * (1 << N)がパターン数 = ２のN乗
        * 
        * 次に（1 << N)パターンで全探索する方法を考える。
        * ３つの数字を選択するパターンは下記の通り。１が選択。０が選択しない。
        * 
        * {2, 1, 0}←選択される数字の集合
        *  0  0  0 
        *  0  0  1
        *  0  1  0
        *  0  1  1
        *  1  0  0
        *  1  0  1
        *  1  1  0
        *  1  1  1
        *  
        *  この８通り。これをビット演算で実現したい。
        *  これは下記のAND演算で実現する。
        *  index & (1 << 配列の添字番号) != 0
        *  上記の意味→　「indexの2進数」AND「 (1 << 配列の添字番号)の2進数」で0以外
        *  例えば index=7で N=1なら１０進数で「７」と「２」。
        *  ２進数「0111」AND「0010」= 「0010」=10進数の「２」
        *  
        *  例
        *  index=1 & (1 << 配列の添字番号＝0) != 0が成立するので、配列(0)を選択
        *  index=1 & (1 << 配列の添字番号＝1) != 0が成立しないので、配列（１）は選択しない
        *  index=1 & (1 << 配列の添字番号＝2) != 0が成立しないので、配列（２）は選択しない
        *  ・
        *  index=2 & (1 << 配列の添字番号＝0) != 0が成立しないので、配列（0）は選択しない
        *  index=2 & (1 << 配列の添字番号＝1) != 0が成立するので、配列（1）は選択
        *  index=2 & (1 << 配列の添字番号＝2) != 0が成立しないので、配列（2）は選択しない
        *  ・
        *  ・
        *  ・
        *  index=7 & (1 << 配列の添字番号＝0) != 0が成立するので、配列(0)を選択
        *  index=7 & (1 << 配列の添字番号＝1) != 0が成立するので、配列(1)を選択 
        *  index=7 & (1 << 配列の添字番号＝2) != 0が成立するので、配列(2)を選択 
        *  こんな感じで全探索する。
        *  
        *  簡単に言うと、８通り全探索したいなら
        *  0～8を順番に2進数に変換して、１になったとこだけ選択する。
        *  
        *  下記コードに読み替えると
        *  for文1重目の　S = index
        *  for文2重目の　i = 配列の添字番号
        *  
        */


        for (int S = 0; S < (1 << n); S++) {//探索数＝２のN乗
            int total = 0;
            
            for (int i = 0; i < n; i++) {
                if((S & (1 << i)) != 0) {// index & (1 << 配列の添字番号) != 0が成立するなら配列(n)を選択
                    total += a[i];
                }
            }

            if(total == v) {
                System.out.println("Yes");
                return;
            }
        }
        
        System.out.println("No");


    }
}

Python

簡単に言うと、８通り全探索したいなら、0～8を順番に2進数に変換して、１になったとこだけ選択する。

import itertools
N = 3
A=[1,2,3]

# 数列Aをビット全探索
def judge(bit):
    total = 0
    for i in range(N):
        if bit[i]:# if文の判定では、0はFalse扱い、他の整数はTrue扱い
            print(A[i], end=" ")
    print()

# タプルの「0 or 1」でビット列を表現
# N＝3なら3ビット
for bit in itertools.product((0,1), repeat=N):
    print(bit)
    judge(bit)

#-------------------------------------------------------------------------------------------
# bit演算子を使うバージョン
N = 3
A=[1,2,3]

# 数列Aをビット全探索
def judge2(bit):
    for i in range(N):
        if(bit & (1 << i)):#整数bitを2進法とみなしたときの、下からi桁目が1か判定
            print(A[i], end=" ")
    print()

for bit in range(1 << N):#1~2のN乗
    print(bin(bit))
    judge2(bit)