ビット演算子：AND、OR、XOR、NOT、シフト
真理値表とPythonの例ですべての6種類のビット演算子を復習し、左シフト・右シフトと2倍・2分の1の関係を理解します。
「ビット演算子：AND、OR、XOR、NOT、シフト」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
ビット操作が重要な理由
ビット操作を使うと、整数の2進表現を直接操作できます。適切なビット演算のテクニックを使えば、複雑に見える多くの問題が簡単になります。たとえば、O(n)時間・O(1)空間で欠けている数を見つけたり、一時変数なしで変数を交換したり、部分集合をコンパクトに表現したりできます。面接官は、低レベルの理解力と創造的な思考力を確認するために、このような問題を出題します。
Pythonの整数は任意精度であり、メモリが許す限り大きくできます。ただし、ビット操作はハードウェアレベルでは常に標準的な2の補数表現の規則に従います。6種類の演算子はすべて、整数の2進表現をビット単位で処理します。
# All six bitwise operators in Python
a, b = 0b1010, 0b1100 # 10 and 12 in decimal
print(f'a = {bin(a)} = {a}')
print(f'b = {bin(b)} = {b}')
print(f'a & b (AND) = {bin(a & b)} = {a & b}') # 1000 = 8
print(f'a | b (OR) = {bin(a | b)} = {a | b}') # 1110 = 14
print(f'a ^ b (XOR) = {bin(a ^ b)} = {a ^ b}') # 0110 = 6
print(f'~a (NOT) = {~a}') # -11 (two's complement)
print(f'a << 1 (LSH) = {bin(a << 1)} = {a << 1}') # 10100 = 20
print(f'a >> 1 (RSH) = {bin(a >> 1)} = {a >> 1}') # 101 = 5AND演算子：ビットマスキング
AND演算子 (&)は、両方の入力ビットが1の場合にだけ1を出力します。主な用途はマスキングで、数値の特定のビットを選択し、それ以外のビットをすべて0にします。数値nのビットkがセットされているか確認するには、n & (1 << k)を評価します。結果が0以外なら、ビットkは1です。
ANDは最下位のセットビットをクリアするためにも使われます。n & (n - 1)は、右端にある1ビットを取り除きます。これはセットビットを効率的に数える処理や、数値が2のべき乗か確認する処理に使われます（2のべき乗はセットビットをちょうど1つだけ持つため、n & (n-1) == 0となります）。
n = 0b10110100 # 180
# Check if bit 5 is set (0-indexed from right)
bit_5 = (n >> 5) & 1
print(f'Bit 5 of {n}: {bit_5}') # 1
# Clear lowest set bit
print(f'n = {bin(n)}')
print(f'n & (n-1) = {bin(n & (n-1))}') # 10110000, removed the '100'
# Check power of two
for x in [16, 15, 8, 6, 1, 0]:
is_pow2 = x > 0 and (x & (x - 1)) == 0
print(f'{x}: power of 2 = {is_pow2}')OR演算子：ビットのセット
OR演算子 (|)は、入力ビットの少なくとも一方が1の場合に1を出力します。主な用途は、他のビットに影響を与えずに特定のビットを1にセットすることです。数値nのビットkをセットするには、n | (1 << k)を使います。kの位置までシフトした1によってそのビットがオンになり、それ以外のビットは、0とのORでは値が変わらないため、そのまま維持されます。
ORはフラグの結合にも使われます。機能フラグをそれぞれ個別のビットで表す場合、ORによって複数のフラグを有効にできます。たとえば、READ | WRITE | EXECUTEは、3つの権限ビットを1つの整数にまとめます。
# Set bit k in n
def set_bit(n, k):
return n | (1 << k)
n = 0b1000 # 8
print(f'Original: {bin(n)}')
print(f'Set bit 1: {bin(set_bit(n, 1))}') # 1010
print(f'Set bit 0: {bin(set_bit(n, 0))}') # 1001
# Flag combination example
READ = 0b001 # 1
WRITE = 0b010 # 2
EXECUTE = 0b100 # 4
perms = READ | EXECUTE
print(f'READ|EXECUTE permissions: {bin(perms)} = {perms}')
print(f'Has READ: {bool(perms & READ)}')
print(f'Has WRITE: {bool(perms & WRITE)}')
print(f'Has EXECUTE: {bool(perms & EXECUTE)}')XOR演算子：切り替えと差分
XOR演算子 (^)は、入力ビットが異なる場合に1を出力します。XORには、強力な3つの代数的性質があります。a ^ a = 0（同じ入力は相殺される）、a ^ 0 = a（0は単位元である）、そしてXORは交換法則と結合法則を満たします。これらの性質により、XORは一意な要素を見つけるための代表的な手法となっています。
XORは特定のビットを反転するためにも使われます。n ^ (1 << k)は、他のビットをそのままにしてビットkを反転します。ビットkが0なら1になり、1なら0になります。
# XOR properties
print(5 ^ 5) # 0 — same values cancel
print(5 ^ 0) # 5 — zero is identity
print(5 ^ 3 ^ 3) # 5 — 3 cancels itself
# Toggle bit k
def toggle_bit(n, k):
return n ^ (1 << k)
n = 0b1010
print(f'Toggle bit 3: {bin(toggle_bit(n, 3))}') # 0010 (was 1)
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}') # 1011 (was 0)
# XOR swap without temp variable
a, b = 7, 13
a = a ^ b
b = a ^ b # b now gets original a
a = a ^ b # a now gets original b
print(f'After XOR swap: a={a}, b={b}') # a=13, b=7NOT演算子と2の補数
NOT演算子 (~)は、すべてのビットを反転します。Pythonでは、2の補数表現のため、~nは-(n+1)と等しくなります。これは多くの人にとって意外な点です。たとえば、~5 = -6であり、単純に予想される0b11111010ではありません。Pythonの整数は無限精度なので、正の数のすべてのビットを反転すると、2の補数では負の結果になります。
実際には、Pythonでビット操作を行う際に~だけを使うことはほとんどありません。代わりに、ANDと組み合わせて特定のビットをクリアしたり、~n & maskのようにmaskでビット幅を特定のビット数に制限したりします（たとえば32ビットなら& 0xFFFFFFFFを使います）。
# NOT in Python: ~n = -(n+1)
for n in [0, 1, 5, 127]:
print(f'~{n} = {~n}') # all give -(n+1)
# Clear bit k using NOT
def clear_bit(n, k):
return n & ~(1 << k)
n = 0b1111
print(f'Clear bit 2: {bin(clear_bit(n, 2))}') # 1011
print(f'Clear bit 0: {bin(clear_bit(n, 0))}') # 1110
# Limiting to 32-bit with mask
def bitwise_not_32(n):
return ~n & 0xFFFFFFFF
print(f'32-bit NOT of 5: {bin(bitwise_not_32(5))}') # 32 zeros then ones左シフト：2のべき乗による乗算
左シフト演算子 (<<)は、すべてのビットをk個左に移動し、空いた右側の位置を0で埋めます。これは2^kを掛けることと同じです。1ビット左シフトすると値は2倍になり、kビット左シフトすると2^k倍になります。
面接問題では、左シフトはビットマスクの作成に最もよく使われます。1 << kは、ビットkだけがセットされた数値を作成します。これはすべてのビット操作の基礎です。個々のビットのセット、クリア、反転、確認は、すべて1 << kから始まります。
# Left shift = multiply by 2^k
n = 1
for k in range(8):
print(f'1 << {k} = {1 << k}') # 1,2,4,8,16,32,64,128
# Practical use: creating bitmasks
def bit_mask(k):
return 1 << k
print(f'\nBitmask for bit 0: {bin(bit_mask(0))}') # 1
print(f'Bitmask for bit 3: {bin(bit_mask(3))}') # 1000
print(f'Bitmask for bit 7: {bin(bit_mask(7))}') # 10000000
# Fast exponentiation: 2^10 = 1024
print(f'2^10 = {1 << 10}') # 1024右シフト：2のべき乗による除算
右シフト演算子 (>>)は、すべてのビットをk個右に移動し、右端のk個のビットを破棄します。これは2^kによる整数除算と同じです。Pythonの右シフトは常に算術シフトです。左端のビットは符号ビット（正の数では0、負の数では1）で埋められます。
面接でよく使われるテクニックとして、数値nからビットkを取り出すには(n >> k) & 1を使います。これによりビットkが位置0まで移動し、他のすべてのビットがマスクされます。完全なマスクを計算して比較する必要がなく、特定のビットを確認する最も簡潔な方法です。
# Right shift = integer division by 2^k
n = 64
for k in range(7):
print(f'{n} >> {k} = {n >> k}') # 64,32,16,8,4,2,1
# Extract bit k from n
def get_bit(n, k):
return (n >> k) & 1
n = 0b10110101 # 181
print(f'\nBits of {n} ({bin(n)}):')
for k in range(8):
print(f' Bit {k}: {get_bit(n, k)}')
# Negative number right shift (arithmetic)
print(f'-8 >> 1 = {-8 >> 1}') # -4 (fills with sign bit 1)実践的なビット操作のチートシート
ここでは、面接で最もよく使われるビット操作のイディオムをまとめます。これらのパターンは数多くの問題で繰り返し登場するため、覚えておきましょう。
n & 1— nが奇数かを確認n & (n-1)— 最下位のセットビットをクリアn & -n— 最下位のセットビットだけを取り出すn | (1 << k)— ビットkをセットn & ~(1 << k)— ビットkをクリアn ^ (1 << k)— ビットkを反転(n >> k) & 1— ビットkを確認
# Bit trick cheatsheet — all at once
n = 0b10110100 # 180
print(f'n = {bin(n)} = {n}')
print(f'n & 1 (odd check) = {n & 1}') # 0: even
print(f'n & (n-1) (clear lowest bit) = {bin(n & (n-1))}')
print(f'n & -n (isolate lowest bit) = {bin(n & -n)}')
print(f'n | (1<<1) (set bit 1) = {bin(n | (1<<1))}')
print(f'n & ~(1<<2) (clear bit 2) = {bin(n & ~(1<<2))}')
print(f'n ^ (1<<5) (toggle bit 5) = {bin(n ^ (1<<5))}')
print(f'(n>>4) & 1 (check bit 4) = {(n>>4) & 1}')セットビットのカウント（Popcount）
整数に含まれる1ビットの数を数えることを、population count（popcount）と呼びます。素朴な方法では、すべてのビットを順番に調べます。Brian Kernighanのトリックは、最下位のセットビットをn &= n - 1で繰り返しクリアし、nが0になるまでの反復回数を数えることで、より高速に処理します。各反復で1ビットだけが取り除かれるため、ループは1ビットの数とまったく同じ回数だけ実行されます。
Python 3.10以降では、int.bit_count()によって個数を直接取得できます。以前のバージョンでは、Kernighanのトリックが標準的な手動実装です。このテクニックは、LeetCodeの「Hamming Weight」問題も解決します。
# Method 1: naive O(log n)
def count_bits_naive(n):
count = 0
while n:
count += n & 1
n >>= 1
return count
# Method 2: Brian Kernighan O(k) where k = number of set bits
def count_bits_fast(n):
count = 0
while n:
n &= n - 1 # clear lowest set bit
count += 1
return count
# Method 3: Python built-in (3.10+)
# n.bit_count()
for x in [0, 1, 7, 255, 180, 1024]:
naive = count_bits_naive(x)
fast = count_bits_fast(x)
print(f'{x:4d} ({bin(x):10s}): naive={naive}, fast={fast}')Pythonのビット操作：重要な注意点
C/Javaとは異なり、Pythonの整数は任意に大きくできます。32ビットや64ビットのオーバーフローはありません。そのため、32ビット動作を前提とする問題では、結果を固定幅にするために自分でマスクする必要があります。下位32ビットだけを残すには& 0xFFFFFFFFを使います。
PythonのNOT演算子~nは、Cで期待されるようなビット反転結果ではなく、-(n+1)を返します。32ビット問題では、期待される32ビットの補数を得るために~n & 0xFFFFFFFFを使うか、0xFFFFFFFF ^ nを計算します。C形式のビット操作に慣れている多くの受験者が、この違いでつまずきます。
# Python vs C gotchas
# In C: unsigned 32-bit NOT of 5 = 4294967290
# In Python: ~5 = -6
print(f'Python ~5 = {~5}') # -6
print(f'32-bit ~5 = {~5 & 0xFFFFFFFF}') # 4294967290
# No integer overflow in Python
big = 1 << 100 # 2^100: huge number, no overflow
print(f'2^100 = {big}') # works fine
# Right shift on negatives: arithmetic (sign-extending)
print(f'-1 >> 3 = {-1 >> 3}') # -1 (all ones shifted in)
# Safe 32-bit mask for problems expecting C/Java semantics
MASK32 = 0xFFFFFFFF
result = (5 + 0xFFFFFFFE) & MASK32 # simulates 32-bit overflow
print(f'5 + (-2) in 32-bit = {result}') # 3シフト演算子と乗除算
左シフトと右シフトを使うと、2のべき乗による乗算や除算を非常に高速に行えます。ハードウェア上では、ビットシフトは単一命令で実行される一方、乗算や除算は複数サイクルを必要とします。Pythonでは整数の乗算もすでに効率的ですが、この関係を理解するとビットパターンをより明確に捉えられます。
便利な恒等式として、nが2^kの倍数か確認するには(n & (2^k - 1)) == 0を使います。マスク2^k - 1は下位kビットがすべて1になっており、これとANDを取ると2^kで割った余りが得られます。これはn % (2^k)と同じですが、C系の言語ではより高速です。
# Shift vs arithmetic equivalence
for k in range(1, 5):
n = 48
print(f'{n} * 2^{k} = {n * (2**k)} = {n << k} (left shift)')
print(f'{n} // 2^{k} = {n // (2**k)} = {n >> k} (right shift)')
print()
# Check divisibility by power of 2
def divisible_by_power_of_2(n, k):
mask = (1 << k) - 1 # 2^k - 1: lower k bits all 1
return (n & mask) == 0
for n in [16, 24, 32, 15, 100]:
print(f'{n} divisible by 4? {divisible_by_power_of_2(n, 2)}')クイックチェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、ANDはビットをマスクし、ORはビットをセットし、XORはビットを反転して差分を検出し、NOTはビットを反転する（Pythonでは-(n+1)を返す）こと、そしてシフトは2のべき乗による乗算・除算を行うこと、n & (n-1)は最下位のセットビットをクリアし、2のべき乗の判定やビットカウントの基礎となること、そしてPythonには固定幅のオーバーフローがないため、32ビット問題では & 0xFFFFFFFF による明示的なマスキングが必要であることを学びました。次はXORの自己逆元という性質を利用して、単一要素問題の仲間を解決します。
よくある質問
「ビット演算子：AND、OR、XOR、NOT、シフト」レッスンは無料ですか？
はい。「ビット演算子：AND、OR、XOR、NOT、シフト」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「ビット演算子：AND、OR、XOR、NOT、シフト」で何を学びますか？
真理値表とPythonの例ですべての6種類のビット演算子を復習し、左シフト・右シフトと2倍・2分の1の関係を理解します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「ビット演算子：AND、OR、XOR、NOT、シフト」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- ビット演算子：AND、OR、XOR、NOT、シフト
- Single NumberとXORの性質
- ビットマスク：セット、クリア、反転、確認
- ビットカウント、Missing Number、ビット反転