前書き
筆者は、競技プログラミング低レートなので、ご指摘などあればぜひよろしくお願いいたします！また、筆者のレベルが上がり次第この記事も更新していくつもりです。
bitとは
普段生活では10進数で物事を考えますが、PCの世界では基本0と1の二進数で計算されている(10進数:4 -> 2進数:11)ため、二進数でコードを書いた方がスッキリすることが多い(可読性は落ちるかもです)。特に全状態について処理しなければならない時、bit全探索は便利です。
bit操作とは
atcoderでbit操作を要求される場面は、ABCのE問題くらいまでは基本的な操作(and(&),or(|),xor(-),not(~),算術シフト(<<,>>))とbit全探索くらいなので、簡単にまとめます。
基本操作
and(&)
演算子(&)の左辺と右辺のビットを比較して、同じ位置のビットが両方1なら1にします。
int a = 2; //10
int b = 3; //11
int c = a & b; //(10 & 11) = 10
System.out.print(c); //2
or(|)
演算子(|)の左辺と右辺のビットを比較して、同じ位置のビットについて片方1なら1にします。
int a = 2; //10
int b = 3; //11
int c = a | b; //(10 | 11) = 11
System.out.print(c); //3
xor(^)
演算子(^)の左辺と右辺のビットを比較して、同じ位置のビットについて片方だけ1なら1にします。
int a = 2; //10
int b = 3; //11
int c = a ^ b; //(10 ^ 11) = 01
System.out.print(c); //1
not(~)
演算子(~)の右辺のビットを全部反転させます。
int a = 2; //010
int c = ~a; //(10 ^ 11) = 101
System.out.print(c); //-3
notで表される2進数の数え方には注意が必要です。まず10進数を2進数に変換する時ですが、例えば10進数で8の時、2進数では1000です。しかし、これは正確に書くと01000になります。左端の数字は符号ビットといって、これが1だと負の数を表します。負の数の二進数の数え方はhttp://www.infonet.co.jp/ueyama/ip/binary/signedbin.htmlなどを参考にしてください。
シフト(<<,>>)
演算子の左辺について左(右)に右辺だけずらします。
int a = 2; //10
int b = a << 1; //(100) = 4
int c = a >> 1; //(01) = 1
System.out.print(b); //4
System.out.print(c); //1
bit全探索
全状態を表して、各状態について処理をしたい時bitを使えば簡単にできる時があります。例えば人が5人いて、その中から何人か選んだ時、その中に２０才以上の人が2人以上が含まれるのは?みたいな時、
解法
bit全探索を行い、立っているbitの数が2以上でかつそのbitの位置の人が20以上ならカウントする。
イメージ
bitは 00000 -> 00001 -> 00010 -> 00011 -> 00100
と遷移していく。例えば00010は1番目の人のみのグループを表しており、00101は0番目と2番目の人のグループを表している。
コード
static void solve(){
int[] age = {12,14,20,4,24};
int ans = 0;
for(int bit = 0;bit < (1<<5);bit++){ //bit全探索=全状態について処理
if(countbit(bit,5,age) >= 2){
ans++;
}
}
System.out.println(ans); //8
}
//立っているbitの数を数え、そのbitの位置の人が20才以上か見る。
static int countbit(int bit,int n,int[] age){
int count = 0;
int x = 1;
for(int i = 0;i < n;i++){
if((x & bit) != 0 && age[i] >= 20){
count++;
}
x <<= 1;
}
return count;
}