Help us understand the problem. What is going on with this article?

bit全探索について簡単にまとめる

競プロとかで毎回bit全探索を調べ直しているのでまとめる。

bit全探索とは

bit全探索とは、bit演算を使って全探索をする方法。bit全探索を使えば、部分集合を全パターン列挙することができる。
例えばAtCoderの「C - たくさんの数式 / Many Formulas」のような問題で、各文字列中のどこに+を入れるかというパターンを簡単に全探索できる。

bit全探索の例

例のコードは以下のようになる。(参考:ビット演算 (bit 演算) の使い方を総特集! - Qiita

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 3;

    // {0, 1, ..., n-1} の部分集合の全探索
    for (int bit = 0; bit < (1<<n); ++bit) {
        vector<int> S;
        for (int i = 0; i < n; ++i) {
            if (bit & (1<<i)) { // 列挙に i が含まれるか
                S.push_back(i);
            }
        }

        cout << bit << ": {";
        for (int i = 0; i < (int)S.size(); ++i) {
            cout << S[i] << " ";
        }
        cout << "}" << endl;
    }
}

標準出力は以下のようになる。

0: {}
1: {0 }
2: {1 }
3: {0 1 }
4: {2 }
5: {0 2 }
6: {1 2 }
7: {0 1 2 }

bit全探索のコード解説

一つずつ上記のコードを解説していく。まずは最初のfor文を見てみる。

// {0, 1, ..., n-1} の部分集合の全探索
for (int bit = 0; bit < (1<<n); ++bit) {
  //
}

見慣れないのはおそらく(1<<n)の部分だと思う。(1<<n)2^nと覚えよう。2^nは全パターン数と一致する。

<<という演算子はビット演算子で、ビット(2進数)を左へシフトする。int型は透過的に整数として扱えるが、実際に内部ではbitで管理されている。例えば3を8bitで保持するのであれば、0b00000011になる(2進数は先頭に0bをつける)。

そして1 (0b00000001)を左へ3ビットシフトする場合は1<<3と書き、結果は8(0b00001000)となる。

AND演算

次にこの部分を見る。

if (bit & (1<<i)) { // 列挙に i が含まれるか

まずは(1<<i)この部分。これは先ほど説明した通り、iが3なので2^3で8となる。
&の部分はAND演算、つまり「両方のビットが 1 のときのみ結果が 1 になるビット演算」である。

出力が7: {0 1 2 }となる場合は、bitが7 (0b00000111)である。というのも、どのビット位置(0~2番目)にもビットが立っているため、iが0~2どれであってもAND演算子ではtrueになり、全パターンである0 1 2を列挙することになる。
逆に4: {2 }の場合は4 (0b00000100)は右から3番目にしかビットが立ってないため、0~2の内、3番目である2しか列挙しないことになる。

このようにbitの特性を活かして全探索することができる。

bit全探索まとめ

  • (1<<n)2^nと覚える
  • (bit & (1<<i))はAND演算子であり、bitの特性を活かして列挙することができる

実際に手を動かして試すのが一番分かりやすい。

hareku
AWS / Go / Laravel / Vue.js / React
https://mycode.rip/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした