【Python】Atcoderで使われるビット演算・ビットシフト・bit全探索についてまとめる

bit演算、bit全探索について勉強しました。

いくつかのWebページや書籍に当たってみたので、自分なりに調べた内容をまとめておきます。

bit全探索とは

選ぶ/選ばない2択がn回あり、その全パターン(2のn乗回)を調べる時に用いる探索方法です。

以下のような問題を考えるときに使うことができます。

・YesかNoで答える問題が2のn乗個ある。

・n人が皿1か皿2のどちらかにボールを載せる

・n桁の数字abcd・・・について、各桁の間に+か-のどちらかを入れて計算結果をxにする

・n冊の本の選び方の全パターンを列挙する

n回の選択肢のそれぞれについて、選ぶ/選ばないという選択肢が2つあることから、選ばないことを0、選ぶことを1のbitとして考え、全てのパターンを繰り返しながら調べていきます。

全パターン調べるので、全探索の一種ですが、そこにbit操作が含まれています。

bit全探索について考える前に、2進数とbit操作について振り返ります。

基本のコード

まずは全パターンを列挙するためのコードを記載します。

このコードを使いまわしつつ、問題に合わせて中身の処理や判定を変更しています。

以下は選ぶを1、選ばないを0として、3つの本の選び方の組み合わせについて全パターンを列挙しています。

#3冊の本の選び方を全列挙する
n=3
for i in range(2**n):
  #ここで必要に応じて初期化
  list = [0]*3
  for j in range(n):
    if (i>>j)&1:
      #ここで問題に応じて判定・処理
      list[j]=1
  #問題によってはここでも判定・処理
  print(list)

#出力
[0, 0, 0]
[1, 0, 0]
[0, 1, 0]
[1, 1, 0]
[0, 0, 1]
[1, 0, 1]
[0, 1, 1]
[1, 1, 1]

#3冊の本の選び方を全列挙する

n=3

for i in range(2**n):

#ここで必要に応じて初期化

list = [0]*3

for j in range(n):

if (i>>j)&1:

#ここで問題に応じて判定・処理

list[j]=1

#問題によってはここでも判定・処理

print(list)

#出力

[0, 0, 0]

[1, 0, 0]

[0, 1, 0]

[1, 1, 0]

[0, 0, 1]

[1, 0, 1]

[0, 1, 1]

[1, 1, 1]

Atcoderで使うことができるようにまずは使いまわせるコードを紹介しましたが、

以降では2進数などbit全探索の前提となる知識について記載していきます。

Pythonでの2進数と10進数の扱い

2進数として扱う

n=0b1010      #先頭にobを付けることで1010を2進数として扱うことができる。
print(bin(n)) #0b1010 →bin()を使うと2進数で表示
print(n)      #10　　　→10進数で表示

n=0b1010 #先頭にobを付けることで1010を2進数として扱うことができる。

print(bin(n)) #0b1010 →bin()を使うと2進数で表示

print(n) #10　　　→10進数で表示

私たちが普段使っている数字は10進数と呼ばれますが、bit全探索ではbit演算を行うために2進数を扱います。

10進数での”10″は2進数では”1010″になります。

“1010”をそのままnに代入すると扱いなれている10進数として代入されます

そこで、”0b”を先頭につけることで”1010″を2進数として代入することができます。

※”bin()”については次の項目に記載しました。

2進数で表示

n=10
print(bin(m)) #0b1010　→bin()を使うことで2進数で表記できる

1 2	n=10 print(bin(m)) #0b1010　→bin()を使うことで2進数で表記できる

10進数の”10″を2進数で表示してみます。

“n=10″で10進数の”10″をnに代入しました。

つづいて”print(bin(n))”とすることで2進数の”1010″として表示することができます。

ビット操作について

bit演算

ビット演算とは2進数の演算をすることです。

整数(2進数)の各桁のビットについて、論理演算を一度に行います。

以下の2つの2進数についてビット演算を行ってみます。

“11011100”　10進数では”220″

“10110110”　10進数では”182″

AND(論理積)

“11011100”と”10110110″の各桁で演算を行います。

各桁について、どちらも1ならば1、いずれかが0なら0になります。

Pythonでの演算子は”&”です。

11011100

10110110

↓

10010100

n=0b11011100
m=0b10110110
print(bin(n&m)) #0b10010100
print(n&m)      #148　　→10進数では148

n=0b11011100

m=0b10110110

print(bin(n&m)) #0b10010100

print(n&m) #148　　→10進数では148

OR(論理和)

“11011100”と”10110110″の各桁で演算を行います。

各桁について、いずれか一方でも1なら1になります。

11011100

10110110

↓

11111110

n=0b11011100
m=0b10110110

print(bin(x | y)) #11111110
print(x | y)      #254　10進数では254

n=0b11011100

m=0b10110110

print(bin(x | y)) #11111110

print(x | y) #254　10進数では254

XOR(排他的論理和)

“11011100”と”10110110″の各桁で演算を行います。

各桁について、一致なら0に、不一致なら1になります。

11011100

10110110

↓

01101010

n=0b11011100
m=0b10110110

print(bin(x ^ y)) #0b1101010  →01001010だが、先頭の0は省略して表示されている
print(x^y)        #106  10進数では106

n=0b11011100

m=0b10110110

print(bin(x ^ y)) #0b1101010 →01001010だが、先頭の0は省略して表示されている

print(x^y) #106 10進数では106

2進数で表示した時、先頭の桁が0であった場合は”0b01101010″とはならず、”0b1101010″と表示されています。表記は省略されているだけで、0で埋められています。

NOT(否定)

“11011100”と”10110110″のそれぞれで演算を行います。

1と0が反転します。

11011100

↓

00100011

10110110

↓

01001001

n=0b11011100 
m=0b10110110

print(bin(~x)) #-0b11011101 #マイナス表記になる
print(bin(~y)) #-0b10110111 #マイナス表記になる

n=0b11011100

m=0b10110110

print(bin(~x)) #-0b11011101 #マイナス表記になる

print(bin(~y)) #-0b10110111 #マイナス表記になる

bitシフト

左シフト

1bit左シフトすると2倍、2bit左シフトすると4倍になります。

n = 0b10010 
print(n)         #18         →10進数では18
print(bin(n<<1)) #0b100100   →1bit左シフトして2進数で表示
print(n<<1)      #36　       →1bit左シフトして10進数で表示すると36。2倍になった
print(n*2)       #36         →2進数が代入された変数を10進数で2倍することもできる
print(bin(n*2))  #0b100100   →2進数が代入された変数を10進数で2倍し、2進数で表示
#0b100100

n = 0b10010

print(n) #18 →10進数では18

print(bin(n<<1)) #0b100100 →1bit左シフトして2進数で表示

print(n<<1) #36　 →1bit左シフトして10進数で表示すると36。2倍になった

print(n*2) #36 →2進数が代入された変数を10進数で2倍することもできる

print(bin(n*2)) #0b100100 →2進数が代入された変数を10進数で2倍し、2進数で表示

#0b100100

2進数の”10010″が、2進数の”100100″になりました。

左シフトすると、各桁の数字が1桁ずつ左にすれます。そして右端に0が入ります。今回は1bit左シフトしたので右端に0が1つ加わりました。

右シフト

1bit右シフトすると2分の1、2bit右シフトすると4分の1になります。

n = 0b110110
print(n)                   #54　　　 →10進数では54
print(bin(n>>1))           #0b11011　→1bit右シフトしてZ進数で表示
print(n>>1)                #27　     →1bit右シフトして10進数で表示すると27。2分の1になった
print(n//2)                #27       →2進数が代入された変数を10進数で2分の1にして10進数で表示
print(bin(n//2))           #0b11011　→2進数が代入された変数を10進数で2分の1にして2進数で表示