Pythonでビット単位演算とシフト演算

AtCoderでよく使うような2進数を使った演算をまとめています。

スポンサーリンク

2進数の表し方

まずはPythonでの2進数の基本的な扱いを理解します。

2進数に変換するにはbinを利用します。

>>> x = 13
>>> y = 10
>>> xb = bin(x)
>>> yb = bin(y)

2進数に返還された値が文字列として出力されます。

先頭についている0bというのが、2進数ということを表しています。

>>> xb
'0b1101'
>>> yb
'0b1010'

0bをつけて2進数をそのまま代入すると、10進数に変換されます。

>>> x = 0b1101
>>> x
13

ビット単位演算

AND

ビットごとにANDをとります。

とりあえず実装すると...

x & y

10進数のみで表すと以下のようになります。

>>> x
13
>>> y
10
>>> x & y
8

どう計算されたかは2進数で見てみるとわかります。

>>> bin(x)
'0b1101'
>>> bin(y)
'0b1010'
>>> bin(x & y)
'0b1000'

以下のようにビット単位でAND処理がされています。

  1101
&)1010
-----------
  1000

OR

ビットごとにORをとります。

とりあえず実装すると...

x | y

10進数のみで表すと以下のようになります。

>>> x
13
>>> y
10
>>> x | y
15

どう計算されたかは2進数で見てみるとわかります。

>>> bin(x)
'0b1101'
>>> bin(y)
'0b1010'
>>> bin(x | y)
'0b1111'

以下のようにビット単位でOR処理がされています。

  1101
|)1010
-----------
  1111

XOR

ビットごとにXORをとります。

とりあえず実装すると...

x ^ y

XORはどちらかが1の時に1になる処理になります。

10進数のみで表すと以下のようになります。

>>> x
13
>>> y
10
>>> x ^ y
7

どう計算されたかは2進数で見てみるとわかります。

>>> bin(x)
'0b1101'
>>> bin(y)
'0b1010'
>>> bin(x ^ y)
'0b111'

以下のようにビット単位でXOR処理がされています。

  1101
^)1010
-----------
    111

反転

単純にビットごとの反転をするのではなく、-(x+1)の値を返します。

とりあえず実装すると...

~x

10進数のみで表すと以下のようになります。

>>> x
13
>>> ~x
-14

2進数でみても、単純に反転してないことがわかります。

>>> bin(x)
'0b1101'
>>> bin(~x)
'-0b1110'

上位ビットを全て0とし、全てのビットを反転してから2の補数をとり、10進数で-1をかけた値になります。

1101   # 13
0010   # 単純に反転
1110   # 2の補数(反転して+1)
-1110  # -1をかける

単純に反転したい時は

単純に反転したい時はXORを使うと反転できます。

>>> x ^ 0b1111
2
>>> bin(x ^ 0b1111)
'0b10'

シフト演算

右シフト

全体を右にシフト、つまり右にずらします。

とりあえず実装すると...

x >> 1

右にずらすと一番下の桁がなくなり、全体の値が右にずれます。

10進数のみで表すと以下のようになります。
2で割り、小数点以下を切り落とした値になります。

>>> x
13
>>> x >> 0
13
>>> x >> 1
6
>>> x >> 2
3
>>> x >> 3
1

右にずらした様子は2進数でみてみるとわかります。

>>> bin(x)
'0b1101'
>>> bin(x >> 0)
'0b1101'
>>> bin(x >> 1)
'0b110'
>>> bin(x >> 2)
'0b11'
>>> bin(x >> 3)
'0b1'

左シフト

全体を左にシフト、つまり左にずらします。

とりあえず実装すると...

x << 1

左にずらすと一番下の桁に0が追加され、全体が左にずれます。

10進数のみで表すと以下のようになります。
2進数を左にずらすので、2倍された値になります。

>>> x
13
>>> x << 0
13
>>> x << 1
26
>>> x << 2
52
>>> x << 3
104

左にずらした様子は2進数でみてみるとわかります。

>>> bin(x)
'0b1101'
>>> bin(x << 0)
'0b1101'
>>> bin(x << 1)
'0b11010'
>>> bin(x << 2)
'0b110100'
>>> bin(x << 3)
'0b1101000'

AtCoderのサンプル問題

C - ORXOR
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

参考

タイトルとURLをコピーしました