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 & y10進数のみで表すと以下のようになります。
>>> x
13
>>> y
10
>>> x & y
8どう計算されたかは2進数で見てみるとわかります。
>>> bin(x)
'0b1101'
>>> bin(y)
'0b1010'
>>> bin(x & y)
'0b1000'以下のようにビット単位でAND処理がされています。
1101
&)1010
-----------
1000OR
ビットごとにORをとります。
とりあえず実装すると...
x | y10進数のみで表すと以下のようになります。
>>> x
13
>>> y
10
>>> x | y
15どう計算されたかは2進数で見てみるとわかります。
>>> bin(x)
'0b1101'
>>> bin(y)
'0b1010'
>>> bin(x | y)
'0b1111'以下のようにビット単位でOR処理がされています。
1101
|)1010
-----------
1111XOR
ビットごとにXORをとります。
とりあえず実装すると...
x ^ yXORはどちらかが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)の値を返します。
とりあえず実装すると...
~x10進数のみで表すと以下のようになります。
>>> x
13
>>> ~x
-142進数でみても、単純に反転してないことがわかります。
>>> 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のサンプル問題
