ビット

「0」か「1」の2通りの状態を表現することができるデータの単位を ビット といいます。
ビットを複数並べたものを ビット列 といいます。たとえば 0011 は4ビットのビット列で、 10101010 は8ビットのビット列です。

Python でのビット列の扱い方

Pythonにはbitsetを直接的に扱う型は用意されていません ¹ 。 int 型でほぼ同様の処理を行うことができます。
この際、整数を2進法で表したものをビット列と同一視し、各桁をビットとみて演算を行います。

整数とビット列の対応

実はこれまで扱ってきた int （整数）型は、コンピュータの内部ではビット列で表現されています。直感的には、整数を 二進法 で表した各桁（0 または 1）をビットとみなし、整数とビット列を対応させています。たとえば十進法の 11 は二進法の 1011 と対応します。

細かい話

すでに学習したとおり、Pythonのint型は符号付きの多倍長整数なので、内部的には通常の固定長（32ビット整数など）とは異なる構造を保持しています。しかし、ユーザー側からすると無限長の 2の補数表現 を仮想的に仮定して演算されている挙動が得られるので、内部的な実装まで気にする必要はありません。2の補数表現というのは負の数を表す方法のひとつです。細かく理解する必要はありませんが、興味がある人は調べてみてください。

ビットごとのAND・OR・XOR演算（& | ^）

ビットごとのAND演算、OR演算、XOR演算はそれぞれ &、 |、 ^ で表現できます。

実行結果

print(6 & 3) # 2 (110 & 011 = 010)
print(6 | 3) # 7 (110 | 011 = 111)
print(6 ^ 3) # 5 (110 ^ 011 = 101)

ビットシフト（<< >>）

左ビットシフト、右ビットシフトはそれぞれ a << b、a >> b で表現できます。
a および b が非負整数のとき、前者は a * (2 ** b) 、後者は a // (2 ** b) と等価です。

print(3 << 2) # 12 (11 -> 1100)
print(13 >> 2) # 3 (1101 -> 0011)

なお、Pythonのintは多倍長整数なので、左右に大きなシフトを行っても誤差なく計算してくれます。

print(1 << 100) # 1267650600228229401496703205376
print(1 << 1000) # 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
print(100000000000000000000000000000000000 >> 100) # 78886
print(100000000000000000000000000000000000 >> 1000) # 0

ただし、あまりに大きな桁数（十進法で4300桁以上）の整数を「出力」しようとするとエラーになります。

print(1 << 15000) # ValueError

a = 1 << 15000 # 代入するだけならエラーにはならない

なおこれは set_int_max_str_digits で解消できます。

from sys import set_int_max_str_digits
set_int_max_str_digits(0)
print(1 << 15000) # 28179...09376

負の数のビットシフト

a << b や a >> b の b が負のときはRuntime Errorになります。 a が負のとき、左シフト a << b は非負の場合と同様、 a * (2 ** b) と等価になります。右シフト a >> b は a // (2 ** b) と等価になります。整数除算の丸めはマイナス方向（負の数の場合は絶対値が大きくなる方向）に丸められる点に注意してください。

print(-3 << 2) # -12
print(-13 >> 2) # -4

以下のコードはいずれもRuntime Error（negative shift count）になります。

print(1 << -1) # Runtime Error

print(1 >> -1) # Runtime Error

ビットごとのNOT演算（~）

この演算はややトリッキーであり、実用上も他の演算子で代用できるので、初学者は必ずしも履修する必要はありません。
整数 x に対するビット毎のNOT演算 ~x は、 -(x+1) と等価です。これは仮想的な無限長の2の補数表現を前提にビット毎に反転を行っていると解釈することもできます。負の数のビット表現を前提にしていることから、AND・OR・XORに比べて直感的に理解しづらいかもしれません。
なおこの演算は2回行うと元の整数に戻ります（ ~~x = x ） ² 。

print(~6) # -7
print(~-7) # 6
print(~~100) # 100

k ビット反転

NOT演算（~）では符号ビットが変わるためやや複雑になっていました。
k ビットの整数の下 k ビットを反転する場合、NOT演算とマスクを併用するか、下 k ビットの整数とビット毎の排他的論理和を用います。

a = 587
print(bin(a))           # 0b1001001011
mask = (1 << 10) - 1
print(bin(mask))        # 0b1111111111
print(bin(a ^ mask))    #  0b110110100
print(bin((~a) & mask)) #  0b110110100

ビット演算の使い道

ビット演算は集合の演算を行う場合や、高速な演算が必要な場合などに用いられます。

集合の操作

整数をビット列とみなすことで、集合を表現することができます。ある要素を含むなら対応するビットを1に、含まないなら0にすることで表現することができます。

具体例

（以下、〇番目は 0-indexed ³ で表します。）
例えば、0〜4の数が書かれたカードのうち、いくつかを手札として持っているとき、この手札を5ビットの整数（0以上32未満の整数）を用いて表現できます。 ここでは「カードに書かれた数に対応する位置のビットを1にする」というルールで手札をビット列に対応付けることにします。例えば {0, 1, 4} という手札は19という整数に対応します。これは2進法の 10011 と対応します。右から0番目、1番目、4番目のビット（桁）が1になっています。2番目、3番目のカードは持っていないので、2番目・3番目の桁は0になっています。

もちろん、配列や set を用いて同様の集合演算を行うことは出来ます。 しかし、上の表に挙げたような単純な集合の操作であれば、 ビット演算を用いることでプログラムがシンプルになったり高速になったりするメリットがあります。

コード例

10要素の集合について {0, 1, 3, 4, 5, 8} および {0, 3, 5, 6, 7, 9} について

print(315 & 745) # 41 {0, 1, 3, 4, 5, 8} ∩ {0, 3, 5, 6, 7, 9} = {0, 3, 5}
print(315 | 745) # 1019 {0, 1, 3, 4, 5, 8} ∪ {0, 3, 5, 6, 7, 9} = {0, 1, 3, 4, 5, 6, 7, 8, 9}

M = (1 << 10) - 1 # 1023
print(315 ^ M) # 708 {2, 6, 7, 9}

高速化

ビット演算では1回の演算で複数のビットについての計算をまとめて行うことができるので、この性質をうまく活かすとプログラムを高速化できることがあります。

最下位ビット

整数 x を2進法表記したときの、ゼロでない最も小さいビットは x & (-x) で取得することができます。

x = 12
print(x & (-x)) # 4

x = 99
print(x & (-x)) # 1

注意点

演算子の優先順位

ビット演算に用いる演算子は四則演算に比べ優先順位が低いものが多いので、明示的に ( ) でくくる必要がある場合があります。
優先順位を全て暗記するのは大変なので、ミスを防ぐためにもなるべく ( ) で囲うと良いでしょう。

print(1 << 5 - 1) # 16
print((1 << 5) - 1) # 31
print(1 & 2 + 3) # 1
print((1 & 2) + 3) # 3

主要な演算子の優先順位を以下に示します。上ほど優先度が高いです。

特定の桁の処理

ビットの取得

整数 i の下から j 番目（0-indexed）のビットを取得したい場合は、右シフトおよびAND演算子でできます。

x = 13 # 2進法で 1101
print((x >> 0) & 1) # 1
print((x >> 1) & 1) # 0
print((x >> 2) & 1) # 1
print((x >> 3) & 1) # 1
print((x >> 4) & 1) # 0
print((x >> 5) & 1) # 0

if 文の判定などでは、 1 を左シフトしたものとANDすることもできます。

x = 13 # 2進法で 1101
for i in range(5):
    if x & (1 << i): # x の下から i ビット目が立っている場合に TRUE
        print(i)

実行結果

0
2
3

ビット全探索

「ビット全探索」と呼ばれるテクニックを紹介します。ビット全探索とは、長さNのすべてのビット列に対して何らかの処理を行うことをいいます。N要素の集合の部分集合すべてを列挙するとも言えます。

N = 3
for i in range(1 << N):
    L = []
    for j in range(N):
        if (i >> j) & 1: # 下から j 桁目のビットが立っている場合
            L.append(j)
    print(i, L)

実行結果

0 []
1 [0]
2 [1]
3 [0, 1]
4 [2]
5 [0, 2]
6 [1, 2]
7 [0, 1, 2]

ビット演算を用いたDP

ビット演算を用いて、各桁をフラグと見てDPのような処理を行うことができます。Pythonのintは多倍長整数なので、それなりに大きな桁（10万桁オーダーなど）でも十分に使えることがあります。

ナップサック問題

N 個の荷物があり、 i 番目の荷物の重さは w_i です。これらから重さの合計が W 以下となるようにいくつかの荷物を選ぶとき、重さの最大値を求めよ。

この問題を解くには、順番に荷物を見て、その時点でどの重さにできるかのリストを更新できれば良いです。リストを使う方法とビット演算を使う方法を比べてみましょう。重さ i が作れる場合、配列では i 番目の要素を1にしますが、ビット演算では下から i 番目のビットを1にします。

リストを使う方法

A = [3, 5, 7, 11] # 荷物の重さ
W = 20 # 重さの最大値
X = [0] * (W+1)
X[0] = 1 # 最初は重さ0だけ可能
for a in A:
    for i in range(a, W+1)[::-1]: # 同じ荷物を2回使わないように、大きい方から更新する
        if X[i-a] == 1:
            X[i] = 1
print(X)
# [1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0]

ビット演算を使う方法

A = [3, 5, 7, 11] # 荷物の重さ
s = 1 # 最初は0番目のbitだけ立てる
for a in A:
    s |= s << a
print(bin(s))
# 0b100101011011101110110101001

コードを比べて見ると、配列では2重ループ、ビット演算では1重ループになっています。これは、1回のビット演算で複数ビットを同時に処理していることからループを1つ少なくすることができていると言えます。

2次元グリッドの表現

（ややマニアックなので必ずしも目を通す必要はありません。）
集合の操作の項で説明した内容を応用すると、 H\times W のグリッド上の図形を1つの整数で表現することができます。具体的には、マス (i, j) を i*W+j 番目のビットに対応させると良いです。場合によっては、左右に番兵を置く実装方法も有効です。

問題

以下の2次元グリッドの問題は、ビット演算で実装することができます。

• ABC307C - Ideal Sheet
• 解説
• ABC322D - Polyomino
• 解説

その他の工夫

その他、並列処理による高速化や、ビット演算と加減・乗除算を組み合わせることで様々な処理を行うことができます。多倍長整数のビット演算・四則演算を簡単に扱うことができる点は、Pythonで競技プログラミングをするメリットのひとつであると言えます。ややマニアックな使い方も含むのでここでは割愛しますが、興味がある方は調べてみてください。

ビット演算の計算量

ワードサイズ ⁴ に収まる場合、1回のビット演算の計算量は O(1) です。桁数が多い場合（ 10^{18} 程度を超える場合）は、 k ビット整数のビット演算の計算量はワードサイズを w として O(k/w) です。つまり、ビットごとの計算を並列処理できれば、およそ w 倍の高速化ができることになります。

特定のビットを取り出す処理

Pythonでのビット演算では、特定のビットを取り出す処理の計算量には注意する必要があります。上で紹介した (x >> i) & 1 や x & (1 << i) は定数時間ではなく、 x のビット数 k に比例する時間 O(k/w) がかかります ⁵ 。ただし定数倍はかなり軽いので、多少オーダーが悪そうでも通る可能性はあります。

たとえば以下の処理の計算量は O(N^2/w) です。計算上は N^2 \gt 10^{11} なので厳しそうに見えますが、1秒程度で実行できます ⁶ 。

N = 320000
x = (1 << N) - 1
s = 0
for i in range(N):
    if (x >> i) & 1:
        s += 1
print(s)

問題

リンク先の問題を解いてください。

EX21.Bitwise Exclusive Or

前のページ | 次のページ