ビット全探索で学ぶビット演算子
プログラミング関連の書籍にありそうなタイトルですが、以下の記事の続編になります。
上記の記事では、ビット全探索を使って問題を解きました。しかし私自身、ビット全探索、もといビット演算子についてよく理解していません。そこで、ビット全探索を題材にしてビット演算子について学ぼうというのが今回の記事のテーマです。
さて、Javaでビット全探索を書くときの基本形は以下のようになっています。
for (int i=0; i<Math.pow(2,N); i++) { for (int j=0; j<N; j++) { if ((1&i>>j) == 1) { //ビットが立っているときの処理 } } }
要素数Nの集合の部分集合を全列挙するビット全探索です。外側のループでは、集合の部分集合に対応する二進数（00011,01110,11110など）を生成し、内側のループでは、生成された二進数のうち、ビットが立っている部分にのみ処理を加えます。例をあげるなら、int型配列 {1,3,5,7,9} をビット全探索にかけたとき、ループカウンタである i（二進数）が 01100 ならば、配列の1番目と2番目の要素、すなわち {3,5} の部分集合が列挙されるということになります。
i が 0 のときは空集合で、その i を Math.pow(2,N)-1 まで回しながら二進数を生成します。外側のループの動きはわかりやすいのですが、問題は内側のループです。とくに if ((1&i>>j) == 1) の部分が全くわかりません。いったい何をやっているんでしょう。
Javaにはビット演算子というものが用意されています。ビット演算子は全部で7種類あり、
・& ビットAND
・| ビットOR
・^ ビットXOR
・~ ビット反転(ビットNOT)
・<< 左へビットシフト
・>> 右へビットシフト(符号有り)
・>>> 右へビットシフト(符号無し)
このうち、ビット全探索で使われているのは1番目の「&」と6番目の「>>」で、このうち「>>」はシフト演算子と呼ばれています。シフト演算子は、値のビットを左または右にシフトするためのもので、いろいろ使い道があるみたいなんですが、今回はビット全探索における使われ方のみに焦点を絞ります。
問題の記述部分を順に見ていきます。
1 & i >> j
& と >> ですが、>> のほうが演算子の優先順位が高いので >> が先に演算されます。
i >> j
この部分では、i を j だけ右にビットシフトするという演算がおこなわれています。
・10101 >> 1（01010）
・11111 >> 3（00011）
・00100 >> 2（00001）
とこのように、ビットが指定した分だけ右にずれて、左側の部分は 0 で埋められます。ビット全探索では N 桁の二進数に対して 0 ~ N-1 まで右にビットシフトしていますが、このときの動作を4桁の二進数1010を例にとって確かめてみます。
・1010 >> 0（1010）
・1010 >> 1（0101）
・1010 >> 2（0010）
・1010 >> 3（0001）
ここで前半部分の 1 & i に注目します。ビット演算子ANDは、ビットが両方とも立っていれば 1 を出力する演算です。上記の二進数1010を右にビットシフトしたものと組み合わせて表にしてみましょう。
・0001 & 1010（0000 = 0）
・0001 & 0101（0001 = 1）
・0001 & 0010（0000 = 0）
・0001 & 0001（0001 = 1）
1と演算しているので、出力はかならず 0 か 1 のどちらかになります。これを見ると、i の一番右側のビットが立っているかどうか、という処理がおこなわれていることがわかります。
なるほど、これで問題の部分の動作がはっきりしました。つまり、
( 1 & i >> j ) == 1
という条件式は、「i を j だけ右にビットシフトしたとき、i の右端のビットが立っているか」という意味なんですね。イメージとしては、生成した二進数を右端から探索していって、もしビットが立っているなら、その部分に対応する要素を（生成した二進数の）部分集合とする、といった感じでしょうか。
今回は & と >> にしか触れませんでしたが、機会があれば、他の演算子も競プロの例題とともに記事にしてみたいです。
