ビット演算（ビット操作）とは？演算子・テクニック・例題をわかりやすく解説

ビット演算が解く問題

整数はビットの並びであり、多くの問題は実はそのビットに関するものです。rwx のようなファイルのパーミッション、機能フラグ、ネットワークマスク、ピクセルの色、コンパクトなオプションの集合、チェックサム、ハッシュなどです。ビット演算子を使うと、多くのビットを1回の操作で読み書きでき、メモリ使用量が小さく、非常に高速です。

面接でもビットのテクニックがよく出題されます。たとえば、ほかのすべての数が2回ずつ現れる中で1回だけ現れる数を見つける問題のように、空間 O(1) のエレガントな解法が得られるためです。

演算子

例では、a = 12（2進数で 1100）と b = 10（2進数で 1010）を使います。

a, b = 12, 10
print(bin(a), bin(b))         # 0b1100 0b1010
print(a & b, a | b, a ^ b)    # 8 14 6
print(~a, a << 1, a >> 2)     # -13 24 3
print(f"{a ^ b:04b}")         # 0110
print(int("1010", 2))         # 10

1ビットの操作

ビットの位置は、右端（最下位ビット）を0として数えます。マスク 1 << i は、ビット i だけが立っています。

例題：立っているビットの数え上げ

ブライアン・カーニハン（Brian Kernighan）の方法は、最下位の立っているビットを残りがなくなるまでクリアし続けるので、ビット位置の数ではなく、1のビットの数だけ繰り返します。x = 44（2進数で 101100）のトレースです。

def count_bits(x):
    count = 0
    while x:
        x &= x - 1        # drop the lowest set bit
        count += 1
    return count

print(count_bits(44))     # 3
print((44).bit_count())   # 3
print((44).bit_length())  # 6

int.bit_count() はPython 3.10以降で使えます。int.bit_length() は、符号を除いて、その数を2進数で書くのに必要なビット数を返します。

Pythonでの定番テクニック

from functools import reduce
from operator import xor

# Every number appears twice except one: pairs cancel out with XOR.
print(reduce(xor, [4, 1, 2, 1, 2]))   # 4

# Swap two integers without a temporary variable (for illustration only).
x, y = 5, 9
x ^= y; y ^= x; x ^= y
print(x, y)                            # 9 5

# Bitmask as a set: enumerate all subsets of 3 items.
items = ["a", "b", "c"]
for mask in range(1 << len(items)):
    print(mask, [items[i] for i in range(len(items)) if mask >> i & 1])
# 0 []
# 1 ['a']
# 2 ['b']
# 3 ['a', 'b']
# 4 ['c']
# 5 ['a', 'c']
# 6 ['b', 'c']
# 7 ['a', 'b', 'c']

マスク 0 は空集合、5（2進数で 101）は ['a', 'c']、7 は3つの品物すべてです。ビットマスクDPは同じ考え方で、マスクを状態として使い、小さな入力での巡回セールスマン問題など、最大でおよそ20個の要素に対する問題に使います。

ほかにも2つの定番があります。x & 1 は奇数なら1です。0 から n までのすべての数と、リストのすべての値のXORを取ると、欠けている1つの数が見つかります。

時間計算量と空間計算量

ビットマスクは要素1つにつき1ビットを使うので、64個のフラグも1つの64ビット整数に収まります。64個の別々の真偽値変数やリストの要素を使う場合と比べて、小さくて済みます。

よくある間違い

• 負の数：Pythonの整数は、符号ビットが無限に並んでいるかのように動作するので、~5 は -6 で、bin(-5) は2の補数の文字列ではなく -0b101 です。32ビットのパターンを見たいときは、値をマスクします：-5 & 0xFFFFFFFF。
• Pythonでの負の数の右シフトは算術シフトです。-8 >> 1 は -4 で、-1 >> 10 は -1 のままです。
• 固定幅の言語でのオーバーフロー：JavaやCで32ビットintに 1 << 31 を行うと、負の値または未定義の動作になります。64ビット型を使い、1L << 40 や 1ULL << 40 と書いてください。
• 論理演算子とビット演算子の取り違え：and と or（C系の言語では && と ||）は真偽値を返しますが、& と | はビットごとに動作します。
• 可読性：x * 2 を x << 1 に置き換えても、現代のコンパイラでもPythonでも速くはならず、コードが読みにくくなるだけです。

実世界での用途

• Unixのファイルパーミッション：chmod 754 は3ビットのグループ3つを設定します（rwx = 4 + 2 + 1）。
• ネットワーク：IPv4のサブネットマスク。ip & mask で、CIDRブロックのネットワークアドレスが得られます。
• フラグとオプション：Pythonの re.IGNORECASE | re.MULTILINE や enum.Flag は、ORでオプションを組み合わせます。
• グラフィックスと色：24ビットのRGB値は、赤・緑・青を (r << 16) | (g << 8) | b として詰め込んだものです。
• データ構造とアルゴリズム：ブルームフィルタ、ビットセット、フェニック木（i & -i を使います）、ハッシュ、チェックサム。
• コーディング面接の問題：単一の数、ビットの数え上げ、2のべき乗、ビットの反転、欠けている数、ビットマスクによる部分集合、+ を使わない2つの整数の和。