競技プログラミングで使いたいと思いつつずっと未履修だったbitsetの使い方を勉強しました。
基本操作
以下ではすべて以下が書かれているものとします。
#include <bitset> #include <iostream> using namespace std;
初期化は、文字列を与えるか、整数を与えるかで行えます。
int main(void) { bitset<8> bs1("10001111"); cout << bs1 << endl; // 10001111 bitset<8> bs2(127); cout << bs2 << endl; // 01111111 return 0; }
n桁目を1にするにはset, n桁目を0にするにはresetを使うのがシンプルです。
int main(void) { bitset<8> bs("10001111"); cout << bs << endl; // 10001111 bs.set(4); // 4番目の桁を1に変更 cout << bs << endl; // 10011111 bs.reset(2); // 2番目の桁を0に変更 cout << bs << endl; // 10011011 return 0; }
n番目の桁を1にするか0にするかを変数で制御したい場合は、引数が2個バージョンのset()を使います。
int main(void) { bitset<8> bs("10001111"); cout << bs << endl; // 10001111 bs.set(4, 1); // 4番目の桁を1に変更 cout << bs << endl; // 10011111 bs.set(2, 0); // 2番目の桁を0に変更 cout << bs << endl; // 10011011 return 0; }
引数なしでset(), reset()を呼ぶと、ビットが1または0で埋められます。
int main(void) { bitset<8> bs("10001111"); cout << bs << endl;; // 10001111 bs.set(); cout << bs << endl; // 11111111 bs.reset(); cout << bs << endl; // 00000000 return 0; }
n番目の桁が0か1かを確かめるには、添字かtest()を使います。
int main(void) { bitset<8> bs("10001111"); cout << bs << endl; // 1,1,1,1,0,0,0,1, と表示される for(size_t i = 0; i < bs.size(); ++i) { cout << bs[i] << ","; } cout << endl; // 同上 for(size_t i = 0; i < bs.size(); ++i) { cout << bs.test(i) << ","; } return 0; }
当然、ビット演算も可能です。
int main(void) { bitset<8> bs1("10001111"); bitset<8> bs2("01010101"); cout << (bs1 & bs2) << endl; // 00000101 cout << (bs1 | bs2) << endl; // 11011111 cout << (bs1 ^ bs2) << endl; // 11011010 return 0; }
count()で1が立ったビットの数を数えられるのはかなり便利です。
int main(void) { bitset<8> bs(127); cout << bs.count() << endl; // 7 return 0; }
その他、使う可能性が高そうな便利機能です。
int main(void) { bitset<8> bs("10001111"); cout << bs << endl; // 10001111 // 0と1を反転 bs.flip(); cout << bs << endl; // 01110000 // 左に2個シフト bs <<= 2; cout << bs << endl; // 11000000 // 右に2個シフト bs >>= 2; cout << bs << endl; // 00110000 // 整数に変換 unsigned long n = bs.to_ulong(); cout << n << endl; // 48 // 文字列に変換 string str = bs.to_string(); cout << str << endl; // 00110000 // 文字列に変換する際、0, 1それぞれを任意の記号にすることも可能 string str2 = bs.to_string('a', 'z'); cout << str2 << endl; // aazzaaaa return 0; }
応用例
ビット全探索
2の5乗をビット探索するときは以下のように書きます。
int main(void) { for(int i = 0; i < (1 << 5); ++i) { bitset<5> s(i); cout << s << endl; } return 0; }
出力は以下です。
00000 00001 00010 00011 ... 11110 11111
