Pythonでビット単位演算とシフト演算
AtCoderでよく使うような2進数を使った演算をまとめています。
2進数の表し方
まずはPythonでの2進数の基本的な扱いを理解します。
2進数に変換するにはbinを利用します。
1>>> x = 13
2>>> y = 10
3>>> xb = bin(x)
4>>> yb = bin(y)2進数に返還された値が文字列として出力されます。
先頭についている0bというのが、2進数ということを表しています。
1>>> xb
2'0b1101'
3>>> yb
4'0b1010'0bをつけて2進数をそのまま代入すると、10進数に変換されます。
1>>> x = 0b1101
2>>> x
313ビット単位演算
AND
ビットごとにANDをとります。
とりあえず実装すると...
1x & y10進数のみで表すと以下のようになります。
1>>> x
213
3>>> y
410
5>>> x & y
68どう計算されたかは2進数で見てみるとわかります。
1>>> bin(x)
2'0b1101'
3>>> bin(y)
4'0b1010'
5>>> bin(x & y)
6'0b1000'以下のようにビット単位でAND処理がされています。
1 1101
2&)1010
3------
4 1000OR
ビットごとにORをとります。
とりあえず実装すると...
1x | y10進数のみで表すと以下のようになります。
1>>> x
213
3>>> y
410
5>>> x | y
615どう計算されたかは2進数で見てみるとわかります。
1>>> bin(x)
2'0b1101'
3>>> bin(y)
4'0b1010'
5>>> bin(x | y)
6'0b1111'以下のようにビット単位でOR処理がされています。
1 1101
2|)1010
3------
4 1111XOR
ビットごとにXORをとります。
とりあえず実装すると...
1x ^ yXORはどちらかが1の時に1になる処理になります。
10進数のみで表すと以下のようになります。
1>>> x
213
3>>> y
410
5>>> x ^ y
67どう計算されたかは2進数で見てみるとわかります。
1>>> bin(x)
2'0b1101'
3>>> bin(y)
4'0b1010'
5>>> bin(x ^ y)
6'0b111'以下のようにビット単位でXOR処理がされています。
1 1101
2^)1010
3------
4 111反転
単純にビットごとの反転をするのではなく、-(x+1)の値を返します。
とりあえず実装すると...
1~x10進数のみで表すと以下のようになります。
1>>> x
213
3>>> ~x
4-142進数でみても、単純に反転してないことがわかります。
1>>> bin(x)
2'0b1101'
3>>> bin(~x)
4'-0b1110'上位ビットを全て0とし、全てのビットを反転してから2の補数をとり、10進数で-1をかけた値になります。
11101 # 13
20010 # 単純に反転
31110 # 2の補数（反転して+1）
4-1110 # -1をかける単純に反転したい時は
単純に反転したい時はXORを使うと反転できます。
1>>> x ^ 0b1111
22
3>>> bin(x ^ 0b1111)
4'0b10'シフト演算
右シフト
全体を右にシフト、つまり右にずらします。
とりあえず実装すると...
1x >> 1右にずらすと一番下の桁がなくなり、全体の値が右にずれます。
10進数のみで表すと以下のようになります。 2で割り、小数点以下を切り落とした値になります。
1>>> x
213
3>>> x >> 0
413
5>>> x >> 1
66
7>>> x >> 2
83
9>>> x >> 3
101右にずらした様子は2進数でみてみるとわかります。
1>>> bin(x)
2'0b1101'
3>>> bin(x >> 0)
4'0b1101'
5>>> bin(x >> 1)
6'0b110'
7>>> bin(x >> 2)
8'0b11'
9>>> bin(x >> 3)
10'0b1'左シフト
全体を左にシフト、つまり左にずらします。
とりあえず実装すると...
1x << 1左にずらすと一番下の桁に0が追加され、全体が左にずれます。
10進数のみで表すと以下のようになります。 2進数を左にずらすので、2倍された値になります。
1>>> x
213
3>>> x << 0
413
5>>> x << 1
626
7>>> x << 2
852
9>>> x << 3
10104左にずらした様子は2進数でみてみるとわかります。
1>>> bin(x)
2'0b1101'
3>>> bin(x << 0)
4'0b1101'
5>>> bin(x << 1)
6'0b11010'
7>>> bin(x << 2)
8'0b110100'
9>>> bin(x << 3)
10'0b1101000'AtCoderのサンプル問題
C - ORXOR
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
参考
- 6. 式 (expression) — Python 3.9.4 ドキュメント
- 2の補数とは？2の補数の計算方法と表現範囲をわかりやすく解説！1の補数との違いは？C言語での補数計算プログラムもチェック | A-STAR（エースター）
\ この記事が役に立ったと思ったら、サポートお願いします！ /
関連記事
【AtCoder】bisectでリストを二分探索する
【AtCoder】Pythonでキューを使う
【AtCoder】Pythonで素数判定・素数列挙・素因数分解
