C++ ビット演算・ビット全探索

ビットは0か1の2通りを表せるやつです。

C++でビット列を作る

下記で作れます。

bitset<8> b("101");
bitset<8> b2(5);

上記は、b, b2共に、00000101 です。引数に文字列を渡すと、そのままビット列として扱います。整数を渡すと、10進数から2進数に変換します。

ビット演算子

ビット演算子は、AND, OR, XOR, NOTがあります。

サンプルコード

int main()
{
  bitset<8> b1("00001100");
  bitset<8> b2("00000101");

  cout << (b1 & b2) << endl; // AND
  cout << (b1 | b2) << endl; // OR
  cout << (b1 ^ b2) << endl; // XOR
  cout << ~b1 << endl;       // NOT
}

結果

00000100
00001101
00001001
11110011

AND

• どちらも1のところを1にします。

OR

• どちらかが1のところを1にします。

XOR

• どちらかが1で、且つ、どちらも1ではないところを1にします。

NOT

• 反転させます。

シフト

• >> は、ビット列の各ビットを右にずらします。
• << は、ビット列の各ビットを左にずらします。

サンプルコード

int main()
{
  bitset<8> b1("00001000");
  cout << b1 << endl;
  cout << b1.to_ulong() << endl;
  cout << (b1 << 1) << endl;
  cout << (b1 << 1).to_ulong() << endl;
  cout << (b1 >> 1) << endl;
  cout << (b1 >> 1).to_ulong() << endl;
}

結果

00001000
8
00010000
16
00000100
4

bit全探索

サンプルコード

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

int main()
{
  vector<int> v = {1, 2, 3};
  for (int bit = 0; bit < (1 << v.size()); ++bit)
  {
    for (int i = 0; i < v.size(); ++i)
    {
      if (bit & (1 << i)) cout << v.at(i) << " ";
    }
    cout << endl;
  }
}

結果

1
2
1 2
3
1 3
2 3
1 2 3