ビット演算 右シフトを使って列挙する方法

ビット演算 右シフトを使って組み合わせを列挙する方法

目的

競技プログラミングでよく出てくる右シフト演算を使ってパターンを列挙するみたいな方法を自分用にメモっておく

例題

AtCoder Beginner Contest 079のC問題などがそう。
問題としては、A,B,C,Dの4つの変数が与えられて、A op1 B op2 C op3 D = 7となるような演算子(+か-)をop1,op2,op3に入れる。
例えば、A=1,B=2,C=2,D=2の場合、A + B + C + D = 7になるので、op1,op2,op3全て+となる。

ビット演算の導入

この問題で出てくる組み合わせは以下

op1	op2	op3
-	-	-
+	-	-
-	+	-
+	+	-
-	-	+
+	-	+
-	+	+
+	+	+

これを3bitだとみて、2進数を10進数にすると以下のようになる(逆でわかりずらくてすみません)

1ビット目	2ビット目	3ビット目	10進数
0	0	0	0
1	0	0	1
0	1	0	2
1	1	0	3
0	0	1	4
1	0	1	5
0	1	1	6
1	1	1	7

ではどうやって、この組み合わせを列挙できるのか。

実装

Pythonで書くとこんな感じかと。

N = 3
for i in range(2**N): 
  ops = ""
  for j in range(N):
    if (i>>j) & 1:
      ops += "+"
    else:
      ops += "-"
  print(ops)

出力はこんな感じで、全部列挙できてる

---
+--
-+-
++-
--+
+-+
-++
+++

何をやってるのか

(i>>j) & 1だけ見ればいい。
(i>>j)はiをjビット右シフトする。右シフトに関してはこれ

iをjビットずらすとこんな感じ

i>>j & 1のようにiをjビットずらして、1とアンド取るとどうなるか。

このように列挙することができた。