ビット

「0」か「1」の2通りの状態を表現することができるデータの単位をビットといいます。

ビットをいくつか並べたものをビット列といいます。 例えば「0011」は4ビットのビット列で、「10101010」は8ビットのビット列です。

ビット演算

ビット列に関する演算をビット演算といいます。

以下の6つのビット演算を紹介します。

• AND演算
• OR演算
• XOR演算
• NOT演算
• 左シフト演算
• 右シフト演算

AND演算

下の表で定義される演算をAND演算（または論理積）といいます。 このAND演算をビット毎に適用する演算をビット毎のAND演算（bitwise AND）といいます。

AND演算ではx, yのビットが共に1の場合のみ結果が1になります。

具体例

0111 AND 0100 = 0100

縦に並べると次のようになります。

    0111
AND 0100
--------
  = 0100

OR演算

下の表で定義される演算をOR演算（または論理和）といいます。 ビット毎にOR演算を適用する演算をビット毎のOR演算（bitwise OR）といいます。

OR演算ではx, yのビットの少なくとも一方が1の場合に結果が1となります。 逆に言うと、共に0の場合のみ結果が0となります。

具体例

0111 OR 0100 = 0111

縦に並べると次のようになります。

    0111
 OR 0100
--------
  = 0111

XOR演算

下の表で定義される演算をXOR演算（または排他的論理和）といいます。 ビット毎にXOR演算を適用する演算をビット毎のXOR演算（bitwise XOR）といいます。

XOR演算ではx, yのビットの一方が1の場合に限り結果が1となります。 x, yのビットが等しい場合に0になると見ることもできます。

具体例

0111 XOR 0100 = 0011

縦に並べると次のようになります。

    0111
XOR 0100
--------
  = 0011

NOT演算

下の表で定義される演算をNOT演算といいます。 ビット毎にNOT演算を適用する演算をビット毎のNOT演算（bitwise NOT）といいます。

NOT演算は単にビットを反転する演算で、0のビットは1に、1のビットは0になります。

具体例

NOT 0111 = 1000

縦に並べると次のようになります。

NOT 0111
--------
  = 1000

左シフト演算

ビット列を左向きにずらす操作を論理左シフト演算や単に左シフトといいます。

論理左シフト演算ではずらした後にはみ出た部分のビットは捨てられ、足りない部分のビットは0で埋められます。

具体例

0111 を2ビット左シフトすると 1100

縦に並べると次のようになります。

2ビット左シフト
    |0111|
  01|11  |
----------
  = |1100|

はみ出た「01」の部分は切り捨てられ、右端の2ビット分は0で埋められます。

右シフト演算

ビット列を右向きにずらす演算を論理右シフト演算や単に右シフトといいます。

論理左シフト演算と同様に、ずらした後にはみ出た部分のビットは捨てられ、足りない部分のビットは0で埋められます。

具体例

0111 を2ビット右シフトすると 0001

縦に並べると次のようになります。

2ビット右シフト
    |0111|
    |  01|11
----------
  = |0001|

はみ出た「11」の部分は切り捨てられ、左端の2ビット分は0で埋められます。

ビット演算の使い道

ビット演算は集合の演算を行ったり、高速な演算が必要な場合に用いられます。

集合の操作

ビット列を用いると物の集まり(以下、集合と呼びます)を表現することができます。 ある要素を含むなら対応するビットを1にし、含まないなら対応するビットを0にすることで表現することができます。

具体例

例えば、1〜10の数が書かれたカードのうち、いくつかを手札として持っているとき、この手札を10ビットのビット列を用いて表現できます。 ここでは「カードに書かれた数に対応する位置のビットを1にする」というルールで手札をビット列に対応付けることにします。 例えば{2, 3, 7}という手札は「0110001000」というビット列に対応します。 2が書かれたカードは含まれるので、(左から)2ビット目が1になっています。 5が書かれたカードは含まれないので、5ビット目は0になっています。

このようにビット列で表現しておくと、 例えば「2人の手札に共通して含まれるカードを求めたい」ときに、 2人の手札のビット列に対してビット毎のAND演算を行うことで 「2人の手札に共通して含まれるカードの集合」に対応するビット列を一度に得ることができます。

集合の操作とビット演算の対応の例

もちろん、配列を用いて同様の集合演算を行うことは出来ます。 しかし、上の表に挙げたような単純な集合の操作であれば、 ビット演算を用いることでプログラムがシンプルになったり高速になったりするメリットがあります。

2つの集合から共通する要素を取り出す例

A = {1, 2, 3, 5, 7}とB = {1, 3, 5, 7, 9}という2つの集合に共通する要素は{1, 3, 5, 7}です。 Aに対応するビット列は「1110101000」で、Bに対応するビット列は「1010101010」です。 これらにビット毎のAND演算を適用すると、「1010101000」となり、これは集合{1, 3, 5, 7}を意味しており、共通する要素を取り出せていることが分かります。

高速化

ビット演算では複数のビットについての計算をまとめて行えるので、 この性質をうまく活かすとプログラムを高速化できることがあります。

STLのbitset

C++でビット列を扱うにはbitsetを用います。

宣言・初期化

bitset<ビット数> 変数名;  // すべてのビットが0の状態で初期化される
bitset<ビット数> 変数名("ビット列(長さはビット数に合わせる)");  // 指定したビット列で初期化される

「ビット数」の部分は定数でなければならず、変数を使うことはできないことに注意してください。

例

bitset<4> b("1010");

ビット演算

bitsetに対するビット演算はC++の演算子として定義されています。

対応は次の表の通りです。

これらのビット演算の末尾に=を付けることで複合代入演算子として用いることができます。

サンプルプログラム

#include <bits/stdc++.h>
using namespace std;

int main() {
  bitset<8> a("00011011");
  bitset<8> b("00110101");

  auto c = a & b;
  cout << "1: " << c << endl;         // 1: 00010001
  cout << "2: " << (c << 1) << endl;  // 2: 00100010
  cout << "3: " << (c << 2) << endl;  // 3: 01000100
  cout << "4: " << (c << 3) << endl;  // 4: 10001000
  cout << "5: " << (c << 4) << endl;  // 5: 00010000

  c <<= 4;
  c ^= bitset<8>("11010000"); // XOR演算の複合代入演算子
  cout << "6: " << c << endl; // 6: 11000000
}

実行結果

1: 00010001
2: 00100010
3: 01000100
4: 10001000
5: 00010000
6: 11000000

bitsetの操作

bitsetにはビット列を扱うときに便利な関数が用意されています。 以下に主要なものを挙げます。

位置の指定についてですが、ビット列の右から左にかけて0, 1, 2, ...と対応します。 配列の位置の指定とは逆になっていることに注意してください。

サンプルプログラム

#include <bits/stdc++.h>
using namespace std;
int main() {
  bitset<4> S;
  S.set(0, 1);  // 0番目のビットを1にする
  cout << S << endl;

  if (S.test(3)) {
    cout << "4th bit is 1" << endl;
  } else {
    cout << "4th bit is 0" << endl;
  }
}

実行結果

0001
4th bit is 0

その他の関数については「細かい話」で紹介します。

整数とビット列の対応

実はこれまで扱ってきたintやint64_tなどの整数型は、 コンピュータの内部ではビット列で表現されています。

さらに言えば、通常のコンピュータで扱えるものは全てビット列です。

コンピュータはビット列の01のパターンに対して数値を割り当てることで数値を扱っています。 例えば「00000111」は7に、「00100100」は36に対応しています。

このようなビット列と数値の対応は、二進法というルールに基づいています。

以下、簡単のために符号なし整数を表現する場合について説明します。

多くのコンピュータでは負の数を2の補数表現という形式で表現します。 ビット演算の話から少しそれるので扱いませんが、興味のある人は調べてみてください。

二進法

二進法は整数を「1, 2, 4, 8, 16, 32, 64, ... (2の累乗)」の和で表す表し方で、足すか足さないかを0, 1に対応させます。

また、二進法で表記することを二進数表記といいます。 これに対して普段私達が使っている0〜9の数字の並びで表現したものを十進数といいます。

例えば、十進数の「7」は、7 = 4 + 2 + 1 なので、二進数表記は「111」となります。先頭に続く0は省略することが多いです。

以下にいくつか例を挙げます。ビット列の右端から順に 1, 2, 4, 8, ... と対応していることに注意してください。

0〜15の二進数表記は以下の通りです。二進数に不慣れな人は確認してみてください。

整数でのビット演算

C++には、整数をビット列として扱うための演算子が用意されています。 整数でのビット演算の演算子はbitsetのものと同じです。

ただし、整数型に応じてビット列の長さが固定されているので、bitsetほど柔軟には使えません。 例えば、uint32_tは32ビットのビット列として扱うことができ、uint8_tは8ビットのビット列として扱うことができます。 さらに、C++の標準で扱える最大の整数型はuint64_tであり、これは64ビットのビット列なので、 整数をビット列として扱えるのは64ビット以下の場合に限定されることになります。

また、coutで出力しようとした場合に10進数の整数として出力されてしまうため分かりにくいという欠点があります。

基本的にはbitsetを使うのが便利ですが、 「ありうる集合すべてを列挙する」ような処理を行う場合には整数をビット列として扱う方が簡潔に書けることがあります。 詳しくは「細かい話」の「ビット全探索」で説明します。

注意点

演算子の優先順位

ビット演算に用いる演算子は優先順位が低いものが多いので、明示的に()でくくる必要がある場合があります。

サンプルプログラム

#include <bits/stdc++.h>
using namespace std;

int main() {
  int x = 5;  // 0101
  int y = 10; // 1010
  // if (x & y > 0) { // &演算子よりも>演算子の優先度の方が高いので x & (y > 0) と解釈される
  if ((x & y) > 0) {
    cout << "yes" << endl;
  } else {
    cout << "no" << endl;
  }
}

実行結果

no

主要な演算子の優先順位を以下に示します。上ほど優先度が高いです。

優先順位を全て暗記するのは大変なので、ミスを防ぐためにもビット演算を行う際には常に()でくくるようにしましょう。

細かい話

bitsetの関数

以下の表にbitsetのビット列に対する操作をまとめます。

ビット全探索

「ビット全探索」と呼ばれるテクニックを紹介します。

ビット全探索によって、組合せの全列挙をシンプルに実装することができます。

ビット全探索とは「すべてのビット列の組合せ」に対して何らかの処理を行うことをいいます。

例えば、長さ2のビット列ならば、すべてのビット列の組合せは「00」「01」「10」「11」の4通りです。

各ビットについて0か1の2通りなので長さNのビット列は2^N通り存在します。

次のサンプルプログラムでは、すべての「長さ3のビット列」を列挙しています。

サンプルプログラム

#include <bits/stdc++.h>
using namespace std;

int main() {
  // 3ビットのビット列をすべて列挙する
  for (int tmp = 0; tmp < (1 << 3); tmp++) {
    bitset<3> s(tmp);
    // ビット列を出力
    cout << s << endl;
  }
}

実行結果

000
001
010
011
100
101
110
111

6行目はtmpという変数を0から始めて8になるまでのfor文です。 1 << 3は、2の3乗を得るための式です。 1を3ビット左シフトすると、ビット列は「1000」となり、これを2進数として解釈すると2の3乗=8になります。

2のk乗の値を得るために、1 << kという書き方をすることがよくあります。シンプルな形なので覚えておきましょう。

7行目では、tmpをビット列として解釈してbitset<3>型のsを初期化しています。

9行目ではsのビット列を出力しています。

0から7のビット列は次のようになっています。

これらの中に長さ3のビット列が全て現れているということが分かります。

より一般には、0から2^N-1の範囲でループすることで、 長さNのビット列をすべて列挙することができます。

ビット全探索の雛形

次の形でビット全探索を行うことができます。

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

bitsetの長さの指定に変数は使えないことに注意してください。

また、このアルゴリズムはビット列の長さをNとして、少なくとも2^N回以上のループになるので計算量に注意しましょう。

例題

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

制約

• 1 \leq N \leq 20
• 1 \leq K \leq 100
• 1 \leq A_i \leq 100 (1 \leq i \leq N)

入力

N K
A_1 A_2 \ldots A_N

出力

総和がKとなるような整数の組合せが存在するなら1行にYESを、そうでなければNOを出力してください。

入力例1

5 11
2 8 4 2 9

出力例1

YES

2 + 9 = 11となるように、2, 9を選べばよいです。

入力例2

5 3
2 8 4 2 9

出力例2

NO

入力例3

5 25
2 8 4 2 9

出力例3

YES

解答例

#include <bits/stdc++.h>
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);  // 最大20個なので20ビットのビット列として扱う

    // ビット列の1のビットに対応する整数を選んだとみなして総和を求める
    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;
  }
}

bitsetと整数の相互変換

整数からbitsetへの変換

bitsetのコンストラクタに整数を渡すことで整数をビット列としてみなしてbitsetに変換することができます。

bitset<ビット数> 変数名(整数);

bitsetから整数への変換

mapのKeyとして使う場合や四則演算を行う場合に、bitsetを整数に変換したいことがあります。このような場合には、bitsetのto_ullong関数を用います。

bitsetの変数.to_ullong()

bitsetのビット数が64ビットを超えている場合は、整数に変換できずに実行時エラーになります。

2進数リテラル

2進数リテラルを用いることで、2進数表記で整数を書くことができます。

2進数リテラルは0b0101や0b11111111のように、0bに続けて01のビット列を書きます。

#include <bits/stdc++.h>
using namespace std;

int main() {
  uint32_t x = 0b100;
  cout << x << endl;  // 4

  cout << (x | 0b010) << endl;  // 計算結果は 0b110 = 6
}

実行結果

4
6

ビット演算の計算量

整数をビット列として用いる場合

全てO(1)です。

bitsetを用いる場合

基本的にはbitsetの操作の計算量はビット数をNとしてO(N)です。

しかし、内部的には整数のビット演算を用いて複数のビットをまとめて処理するように実装されていることが多いため、 64ビット以内であれば基本的にO(1)になります。 64ビットを超える場合でも、計算量から見積もられる実行時間より高速に動作することが多いです。

負の整数の右シフト

論理右シフトでは、空いたビットは0で埋められるということを説明しましたが、 負の数を右シフトした場合には、空いたビットは基本的に1で埋められます。 この動作を算術右シフトといいます。

演習問題

リンク先の問題を解いてください。

EX25.集合の操作

ABC/ARCの問題

ここまでの知識で解ける問題をAtCoder Beginner Contest / AtCoder Regular Contestの過去問題から紹介します。 練習問題だけでは物足りない人は是非挑戦してみてください。

「2.05.再帰関数」でも取り上げた問題ですが、ビット全探索を用いて解くこともできます。

• ARC061 C - たくさんの数式 / Many Formulas
• ABC079 C - Train Ticket
• ABC104 C - All Green
• ARC029 A - 高橋君とお肉
• ABC002 D - 派閥

前のページ | 次のページ