bit全探索
bit全探索について、コレまでに利用したことがあるが、pythonでの実装の際にプログラムをどのように書いたら良いのかで躓いてしまったので備忘録として書いておく。
基本的なpythonのコード
まず、5 >> 2 & 1を理解しよう！
まず、基本的な演算から押さえていきます。まずは、5 >> 2が何をしているのか。
1．5という数字を、二進数101に変換する。
2．>> 2は、2進数に変換された数字を、2bit分右にずらすことを意味しているので、101→1.01。小数点以下は切り捨てるので、1になる。
3．最後に、2進数の1を10進数にもどして、1を出力。コレまでをまとめると、5 >> 2 → 1の変換を行っている。
次に、ビット論理積（AND）演算子＆について。
- こちらは、2つの数を2進数にしたときの各桁の論理積を出力します。
- 例）
11001010 (202) & 10111001 (185) → 10001000 (136)
最後に、5 >> 2 & 1について。
- コレは、
5という数字を2進数に変換したときの、下2+1桁目のbitが1かどうかを判定してくれるものです。
ということで、bit全探索を行っていきたいと思います。
bit全探索（n=4）
n=4のときの探索を行いたいと思います。全部で、2^4通りあります。以下。
n = 4
for bit in range(1 << n):
print(bin(bit)[2:])
# output
# 0
# 1
# 10
# 11
# 100
# 101
# 110
# 111
# 1000
# 1001
# 1010
# 1011
# 1100
# 1101
# 1110
# 1111
- 例えば、
1011の場合は[操作あり, 操作なし, 操作あり, 操作あり]といったことを後々行いたいわけです。
では、今のような場合はどうしたらいいのでしょうか。