1. はじめに

この記事は、香川大学創造工学部のサークル SLP の Advent Calendar 2020 の 23 日目の記事です。
https://adventar.org/calendars/5402

気が付いたら 12 月ももう終わりですね。
忍耐力と継続力が試される 1 年だったと思います。
何とか中間試験と課題の嵐を乗り切り、いよいよ冬休み、といったところですね。

さて、今年大学に入学して、初めて競技プログラミングに触れて、ビット演算というとても興味深いテーマを見つけたので、自分なりに勉強したことをまとめていきたいと思います！
勉強した内容のまとめなので自分のために書いている感じしかないですが、よろしくお願いします。
少しでも何かためになることがあればいいかなと思います。

2. ビット演算

まず初めに、ビット演算について軽く説明をします。
ビット演算では、文字通りビットを用いて演算するので、2 進数表記が基本となってきます。
C++ では、0b に続けて 0 と 1 のビット列を書くことで、 2 進数リテラルを用いて 2 進数表記で数字を書くことができます。

AND 演算

x	y	x AND y
0	0	0
0	1	0
1	0	0
1	1	1

のように定義される演算を AND 演算(論理積)といいます。

12 = 0b01100
24 = 0b11000

ですので、これらをそれぞれ AND 演算すると、

(12 & 24) = 0b01000

なので、

(12 & 24) = 8

となります。

and.cpp

#include <iostream>
using namespace std;

int main(){
    int a = 12; //0b01100
    int b = 24; //0b11000

    cout << a << " AND " << b << " = " << (a & b) << endl;
}

出力結果はこんなかんじ

12 AND 24 = 8

OR 演算

x	y	x OR y
0	0	0
0	1	1
1	0	1
1	1	1

のように定義される演算を OR 演算(論理和)といいます。

(12 | 24) = 0b11100

ですので、

(12 | 24) = 28

となります。

or.cpp

#include <iostream>
using namespace std;

int main(){
    int a = 12;
    int b = 24;

    cout << a << " OR " << b << " = " << (a | b) << endl; 
}

12 OR 24 = 28

XOR 演算

x	y	x XOR y
0	0	0
0	1	1
1	0	1
1	1	0

のように定義される演算を XOR 演算(排他的論理和)といいます。
x と y のビットが異なるときに 1 になり、等しいとき 0 になる演算です。

(12 ^ 24) = 0b10100

ですので、

(12 ^ 24) = 20

となります。

xor.cpp

#include <iostream>
using namespace std;

int main(){
    int a = 12;
    int b = 24;

    cout << a << " XOR " << b << " = " << (a ^ b) << endl;
}

12 XOR 24 = 20

NOT 演算

x	NOT x
0	1
1	0

のように定義される演算を NOT 演算 といいます。

左シフト演算

ビット列を左向きにずらす操作をする演算を左シフトといいます。
左シフトでは、ずらした後にはみ出したビット列は切り捨てられ、0 で埋められます。

24 = 0b11000

を 2 ビット左シフトすると 0b00000

になります。

右シフト演算

ビット列を右向きにずらす操作をする演算を右シフトといいます。
右シフトでも同じく、はみ出たビット列は切り捨てられ、0 で埋められます。

24 = 0b11000

を 3 ビット右シフトすると　0b00011

になります。

負の数の場合には、空いたビット列は 1 で埋められます。

3. ビット演算の使い道

主にビット演算には 2 つの使い道があり、1 つめは高速化、2 つめは集合の計算です。
実際に問題を解いていこうと思いますが、その前に bitset について触れておきたいと思います。

bitset

C++ でビット列を扱う際には bitsetを用います。
bitset とは、ビット配列を提供するクラステンプレートで、各要素が 0 か 1 にしかならない配列を表現することができます。

宣言・初期化

bitset<"ビット数"> "変数名"; // すべてのビット列が 0 の状態で初期化
bitser<"ビット数"> "変数名"("ビット列"); // 指定されたビット列で初期化

演算子

ビット演算	bitset の演算子	つかいかた
AND	&	変数 1 & 変数 2
OR	｜	変数 1 ｜変数 2
XOR	^	変数 1 ^ 変数 2
NOT	~	~ 変数
左シフト	<<	変数 << シフトするビット数
右シフト	>>	変数 >> シフトするビット数

bitset の関数

操作	かきかた
全てのビットを 1 にする	変数.set()
特定のビットを 1 にする	変数.set(1 にする位置)
特定のビットの値を変更する	変数.set(位置, 値)
全てのビットを 0 にする	変数.reset()
特定のビットを 0 にする	変数.reset(0 にする位置)
全てのビットを反転する	変数.flip()
特定のビットを反転する	変数.flip(反転する位置)
特定のビットが 1 になっているか調べる	変数.test(調べる位置)
全てのビットが 1 になっているか調べる	変数.all()
いずれかのビットが 1 になっているか調べる	変数.any()
1 のビットの個数を数える	変数.count()

ここまでが主な bitset のまとめです。

では、問題を解いてみましょう。

4. ビット全探索

例題

$A_1$, $A_2$, $A_3$...$A_n$ の $N$ 個の整数が与えられます。これらの整数からいくつか選び、その総和が $K$ となるような選び方が存在するかどうかを求めてください。

制約 $$1 ≤ N ≤ 20$$ $$1 ≤ K ≤ 100$$ $$1 ≤ A_i ≤ 100 (1 ≤ i ≤ N)$$

入力
$N, K$
$ A_1, A_2...A_N$

出力
　題意を満たすならば YES 、そうでないならば NO を出力してください。

この問題では、ビット演算の使い道のひとつである、集合の計算、いわゆるビット全探索というテクニックを用いることにより、組み合わせの全列挙を簡単に行うことができます。

ビット全探索は次のようにして行います。

for(int tmp = 0; tmp < (1 << "ビット数"); tmp++){
  bitset<"ビット数"> s(tmp);
  // (ビット列 s に対する処理)
}

bitset の長さの指定には変数を用いることができないということに注意が必要です。

for 文の中では、例えば今 4 ビットのビット列を考えるとすると、tmp は 0 から、1 を 4 だけ左シフトしたもの、つまり 2 進数表記で 10000 未満までループを行っている、ということになります。
ここからわかることは、1 << n は $2^n$ を表現している、ということです。

では、本当にそうなっているのかどうか、簡単に確かめます。
4 ビットのビット列の全列挙をしてみたいと思います。
次のようにすると行うことができます。

sample1.cpp

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

int main(){
    int n = 4;
    int count = 0;

    // 4 ビットのビット列を全列挙
    for(int tmp = 0; tmp < (1 << n); tmp++){
        bitset<4> s(tmp);

        // ビット列の出力
        cout << count << " = " << "{" << s << "}" << endl;
        count++;
    }

    return 0;
}

0 = {0000}
1 = {0001}
2 = {0010}
3 = {0011}
4 = {0100}
5 = {0101}
6 = {0110}
7 = {0111}
8 = {1000}
9 = {1001}
10 = {1010}
11 = {1011}
12 = {1100}
13 = {1101}
14 = {1110}
15 = {1111}

となり、0 から $2^4$ 未満までを出力する、ということが確認できました。

それでは、例題に戻りたいと思います。
上の sample1.cpp をベースに、次のようになります。

sample.cpp

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

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a.at(i);

    bool ans = false;

    // 選び方を全て試し、総和が k になるものをさがす
    for(int tmp = 0; tmp < (1 << 20); tmp++){
        bitset<20> s(tmp); // n は最大で 20 なので、20 ビットのビット列として扱う

        int sum = 0;
        for(int i = 0; i < n; i++){
            if(s.test(i)) sum += a.at(i);
        }

        if(sum == k) ans = true;
    }

    if(ans) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

5 11     
2 8 4 2 9

YES

5 3      
2 8 4 2 9

NO

5 25
2 8 4 2 9

YES

3 つのパターンで試してみました。

次に、AtCoder の中からビット全探索を用いて解くことができ、僕のレベルにちょうどいい問題があったので、それを解いていこうと思います。

AtCoder Beginner Contest 045 C 問題

問題文や詳しい入出力の指示に関しては、上のリンクをクリックして見てください。

数字を文字列 s として入力し、1文字1文字の間に和の記号 "+" を入れることができます。
例えば、334 だと 334, 3 + 34, 33 + 4, 3 + 3 + 4 という風になります。
こうしてできた 334, 3 + 34, 33 + 4, 3 + 3 + 4 をすべて足した合計を求めよ、という問題です。

文字の間に入る "+" という記号を入れることのできる箇所は全部で、s.length() - 1 個あるので、これらすべてを探索します。
ここで、ビット全探索を用いることにより、部分集合の全列挙を行いやすくなります。

解答は下のようになります。

abc045_c.cpp

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

int main(){
    string s;
    cin >> s;
    long long ans = 0, sum = 0;

    // "+" が入るすべての場合を探索
    for(int tmp = 0; tmp < (1 << s.length() - 1); tmp++){
        bitset<9> bit(tmp); // s の長さが 10 以下なので、"+" が入る場所は高々 9 箇所


        /* 一桁ずつ足していって、"+" が出てこなければ 10 倍する
        "+" が出てくればそれまでの合計値 sum を全体の合計値 ans に足して、sum をリセット */
        for(int i = 0; i < s.length() - 1; i++){
            sum *= 10;
            sum += s.at(i) - '0';
            if(bit.test(i)){
                ans += sum;
                sum = 0;
            }
        }
        sum *= 10;
        sum += s.back() - '0';
        ans += sum;
        sum = 0;
    }

    cout << ans << endl;
}

9999999999

12656242944

AtCoder Beginner Conest 167 C 問題

問題はこんな感じです。
学びたいアルゴリズムは全部で M 種類あり、C 円の参考書で理解度が $A_1, A_2...A_M$ だけ上昇します。
書店には N 冊の参考書が陳列されており、そのそれぞれに価格 $C_1, C_2... C_N$ が設定されています。
全てのアルゴリズムの能力を X 以上にするにはどの本を買えば最も安く済むかどうかを求めます。

同じ列の A の値を足し合わせて、それが X を超えているかどうか判断します。
またその際に、参考書の値段も足し合わせておき、参考書の合計の値段が一番低いものを出力します。

解答は以下のようになります。

abc167_c.cpp

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

int main(){
    int n, m, x;
    cin >> n >> m >> x;
    vector<int> c(n);
    vector<vector<int>> a(n, vector<int>(m));
    for(int i = 0; i < n; i++){
        cin >> c.at(i);
        for(int j = 0; j < m; j++){
            cin >> a.at(i).at(j);
        }
    }

    bool t = true;
    int cost = 0, ans = 999999999;
    // 参考書の合計費用はあらかじめ高く見積もっておく


    // どの参考書を購入するか、という組み合わせの全列挙
    for(int tmp = 0; tmp < (1 << n); tmp++){
        bitset<12> s(tmp); // n の最大値が 12 であるため、12 ビットのビット列で考える

        cost = 0;
        t = true;
        vector<int> skill(m);
        // 参考書で得られるアルゴリズムの種類別の能力値の配列
        // ビット全探索のループが 1 つ終わるごとに初期化する

        for(int i = 0; i < n; i++){
            if(s.test(i)){
                cost += c.at(i); // かかる費用
                for(int j = 0; j < m; j++){
                    skill.at(j) += a.at(i).at(j);
                }
            }
        }

        // 得られる能力がそれぞれ x を超えているかどうかの判定
        for(int i = 0; i < m; i++){
            if(skill.at(i) < x) t = false;
        }
        if(t) ans = min(ans, cost);
    }

    if(ans == 999999999) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
}

-1

8 5 22
100 3 7 5 3 1
164 4 5 2 7 8
334 7 2 7 2 9
234 4 7 2 8 2
541 5 4 3 3 6
235 4 8 6 9 7
394 3 6 1 6 2
872 8 4 3 7 2

5. おわりに

アドベントカレンダーを初めて書いてみましたが、これだけではなく、定期的に知識をアウトプットしていくとより確固たるものになるんだろうな、という実感が何となくですが湧きました。
来年は何か創作できればなと思います！

それでは、よい年末をお過ごしください。

[参考文献]

ビット全探索についてとてもわかりやすくまとまっています
https://drken1215.hatenablog.com/entry/2019/12/14/171657

ビット全探索というよりも、ビットの考え方について詳しく学べます。
https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361

基本的にこの記事をベースにさせてもらいました
https://atcoder.jp/contests/apg4b/tasks/APG4b_ac

ビット演算の勉強

目次

1. はじめに

2. ビット演算

AND 演算

OR 演算

XOR 演算

NOT 演算

左シフト演算

右シフト演算

3. ビット演算の使い道

bitset

4. ビット全探索

例題

AtCoder Beginner Contest 045 C 問題

AtCoder Beginner Conest 167 C 問題

5. おわりに