ビットマスク：セット、クリア、反転、確認
個々のビットをセット、クリア、反転、確認するヘルパーを実装し、部分集合列挙問題で部分集合を表すためにビットマスクを適用します。
「ビットマスク：セット、クリア、反転、確認」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
ビットマスクとは
ビットマスクとは、別の整数に含まれる特定のビットを選択、変更、確認するために使う整数です。マスクでは、対象とする位置を1、それ以外の位置を0にします。ビット演算子と組み合わせることで、他のビットに影響を与えず、細かくビットを操作できます。
マスクを使う基本操作は、セット（ビットを1にする）、クリア（ビットを0にする）、トグル（ビットを反転する）、チェック（ビットが1かどうかを確認する）の4つです。それぞれ、マスク 1 << k と OR、AND-NOT、XOR、AND の各演算子を使います。
# The four fundamental bit mask operations
def set_bit(n, k): return n | (1 << k) # OR to set
def clear_bit(n, k): return n & ~(1 << k) # AND-NOT to clear
def toggle_bit(n, k): return n ^ (1 << k) # XOR to toggle
def check_bit(n, k): return (n >> k) & 1 # shift+AND to check
n = 0b10110101 # 181
print(f'n = {bin(n)}')
print(f'set bit 1: {bin(set_bit(n, 1))}')
print(f'clear bit 2: {bin(clear_bit(n, 2))}')
print(f'toggle bit 0: {bin(toggle_bit(n, 0))}')
print(f'check bit 4: {check_bit(n, 4)}')ビットをセットする：ビットをオンにする
ビット k をセットする（現在の値にかかわらず1にする）には、数値とマスク 1 << k の OR を計算します。0 OR 1 = 1、1 OR 1 = 1 なので、対象のビットは1になります。その他のビットは0との OR になるため、値は変わりません。
ビットのセットには冪等性があります。何度実行しても、1度だけ実行した場合と同じ結果になります。ビット k がすでに1なら、結果は変わりません。この性質は、現在の状態を気にせず機能を有効にしたいフラグ管理で重要です。
def set_bit(n, k):
mask = 1 << k
return n | mask
# Set various bits
n = 0b00001010 # 10
print(f'Original: {bin(n)} = {n}')
for k in [0, 3, 6, 7]:
result = set_bit(n, k)
print(f'Set bit {k}: {bin(result)} = {result}')
# Idempotence: setting already-set bit does nothing
n = 0b1111
print(f'\nAlready set: {bin(set_bit(n, 2))} = {bin(n)} (unchanged)')
# Setting multiple bits at once with a combined mask
mask = (1 << 0) | (1 << 2) | (1 << 4) # bits 0, 2, 4
print(f'Set bits 0,2,4: {bin(0 | mask)} = {0 | mask}')ビットをクリアする：ビットをオフにする
ビット k をクリアする（現在の値にかかわらず0にする）には、数値とマスクの補数の AND を計算します。式は n & ~(1 << k) です。補数 ~(1 << k) では、ビット k だけが0で、それ以外のすべてのビットが1になります。0との AND によって対象のビットは0になり、1との AND によって他のビットはそのまま維持されます。
セットと同様に、クリアにも冪等性があります。すでに0のビットをクリアしても、数値は変わりません。Python では、符号拡張が自動的に処理されるため、~(1 << k) は任意の k に対して正しく動作します。概念的には、補数の上位ビットがすべて1になります。
def clear_bit(n, k):
mask = ~(1 << k) # all 1s except bit k
return n & mask
n = 0b11111111 # 255: all bits set
print(f'Original: {bin(n)} = {n}')
for k in [0, 3, 6, 7]:
result = clear_bit(n, k)
print(f'Clear bit {k}: {bin(result)} = {result}')
# Clear multiple bits with combined mask complement
def clear_bits(n, positions):
mask = 0
for k in positions:
mask |= (1 << k)
return n & ~mask
result = clear_bits(0b11111111, [1, 3, 5, 7])
print(f'Clear bits 1,3,5,7: {bin(result)} = {result}') # 0b01010101 = 85ビットをトグルする：ビットを反転する
ビット k をトグルする（0から1、または1から0へ反転する）には、数値とマスク 1 << k の XOR を計算します。1との XOR ではビットが反転し、0との XOR ではビットは変わりません。これは、XOR の基本的な性質を1つのビットに適用したものです。
4つの操作のうち、トグルだけには冪等性がありません。2回実行すると元の値に戻ります。そのため、オンとオフを切り替えるスイッチや、コンパクトな整数表現内のブールフラグなど、2つの状態を交互に切り替える機能に適しています。
def toggle_bit(n, k):
return n ^ (1 << k)
n = 0b10101010 # 170
print(f'Original: {bin(n)}')
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}') # off->on: 10101011
print(f'Toggle bit 1: {bin(toggle_bit(n, 1))}') # on->off: 10101000
print(f'Toggle bit 7: {bin(toggle_bit(n, 7))}') # on->off: 00101010
# Toggle is its own inverse: two toggles = no change
result = toggle_bit(toggle_bit(n, 3), 3)
print(f'Double toggle bit 3: {bin(result)} == original {bin(n)}? {result == n}')
# Toggle all lower k bits
def toggle_lower_k(n, k):
mask = (1 << k) - 1 # k ones in the lowest positions
return n ^ mask
print(f'Toggle lower 4 bits of {bin(n)}: {bin(toggle_lower_k(n, 4))}')ビットをチェックする：ビットがセットされているか確認する
ビット k がセットされているか確認するには、n を k ビット右シフトしてから 1 と AND を計算します。式は (n >> k) & 1 です。これによりビット k が位置0に移動し、上位ビットがすべてマスクされるため、0（ビット k が0）または1（ビット k が1）が残ります。別の方法として、bool(n & (1 << k)) を使えば True/False の結果を得られます。
ビットのチェックは非破壊的な操作であり、n を変更しません。各位置を個別にシフトしてマスクすれば、複数のビットを確認できます。これは数値のビット表現を走査する基本となる方法で、部分集合の列挙やビットマスク状態を使った動的計画法に利用されます。
def check_bit(n, k):
return (n >> k) & 1
def is_bit_set(n, k):
return bool(n & (1 << k))
n = 0b10110101 # 181
print(f'n = {bin(n)} = {n}')
for k in range(8):
print(f'Bit {k}: {check_bit(n, k)} ({"set" if check_bit(n, k) else "clear"})')
# Count set bits using check_bit
def count_set_bits(n):
return sum(check_bit(n, k) for k in range(n.bit_length()))
print(f'\nSet bits in {n}: {count_set_bits(n)}')
# Get bit representation as list (LSB first)
def to_bit_list(n, width=8):
return [check_bit(n, k) for k in range(width)]
print(f'Bit list (LSB first): {to_bit_list(n)}')部分集合の表現に使うビットマスク
n ビットの整数は、n 個の要素からなる集合の部分集合を表せます。ビット k が1なら要素 k が部分集合に含まれ、0なら含まれません。これにより、部分集合を1つの整数に圧縮でき、要素の所属確認（mask & (1 << k)）、要素の追加（mask | (1 << k)）、要素の削除（mask & ~(1 << k)）、集合の和集合・積集合（mask1 | mask2 と mask1 & mask2）を O(1) で実行できます。
n 個の要素がある場合、可能な部分集合は 2^n 個あり、それぞれが 0 から 2^n - 1 までの n ビット整数で一意に表されます。0 から 2^n - 1 までのすべての整数を走査すれば、すべての部分集合を列挙できます。
# Subset representation with bitmasks
elements = ['A', 'B', 'C', 'D']
n = len(elements)
def subset_from_mask(mask):
return [elements[k] for k in range(n) if (mask >> k) & 1]
# Enumerate all 2^n subsets
print('All subsets:')
for mask in range(1 << n): # 0 to 15 for n=4
print(f' {mask:04b}: {subset_from_mask(mask)}')
# Set operations
mask_ab = 0b0011 # {A, B}
mask_bc = 0b0110 # {B, C}
print(f'\nUnion: {subset_from_mask(mask_ab | mask_bc)}')
print(f'Intersection: {subset_from_mask(mask_ab & mask_bc)}')
print(f'Difference A\\B: {subset_from_mask(mask_ab & ~mask_bc & 0b1111)}')マスクのすべての部分集合を走査する
ビットマスク動的計画法では、指定したマスクのすべての部分集合を走査する必要がよくあります。一般的なテクニックは、sub = mask から始め、sub = (sub - 1) & mask で更新しながら、sub が0になるまで繰り返す方法です。各反復で異なるサブマスクが得られます。すべてのマスクについて合計すると O(3^n) です。これは、各要素が外側のマスクには含まれるがサブマスクには含まれない、両方に含まれる、どちらにも含まれない、という3通りの状態を取れるためです。
この手法は、「配列を XOR が等しい部分集合に分割する」問題や「部分集合の AND の最大値を求める」問題などに登場します。サブマスクを効率的に列挙できることは、高度なビットマスク DP の特徴です。
def all_submasks(mask):
submasks = []
sub = mask
while sub > 0:
submasks.append(sub)
sub = (sub - 1) & mask
submasks.append(0) # empty subset
return submasks
mask = 0b1011 # {0, 1, 3}
elements = ['A', 'B', 'C', 'D']
def show(m): return '{' + ','.join(elements[k] for k in range(4) if (m>>k)&1) + '}'
print(f'All submasks of {bin(mask)} = {show(mask)}:')
for sub in all_submasks(mask):
print(f' {bin(sub):6s}: {show(sub)}')
print(f'Total: {len(all_submasks(mask))} submasks (should be 2^{bin(mask).count("1")} = {2**bin(mask).count("1")})')ビットマスクDP：巡回セールスマン問題のプレビュー
ビットマスクDPは、状態に訪問済み要素の部分集合が含まれる問題を解きます。典型例は巡回セールスマン問題（TSP）です。これは、n個の都市をすべて訪問する巡回路の最小コストを求める問題です。状態はdp[mask][city]で表し、maskに含まれる都市を訪問してcityで終了する場合の最小コストを意味します。n個の都市では状態数が2^n × nとなるため、時間計算量はO(n^2 × 2^n)です。n ≤ 20であれば十分実用的です。
マスクは訪問済み集合を圧縮して表します。ビットのセット、クリア、確認は、それぞれ都市への訪問、都市からの離脱、都市の確認に対応します。これがビットマスクDPの核心です。状態を表す集合としてビットを使うことで、コンパクトに管理できます。
# TSP with bitmask DP
import sys
def tsp(dist):
n = len(dist)
INF = float('inf')
# dp[mask][v] = min cost to reach v having visited cities in mask
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0 # start at city 0, only city 0 visited (mask=1=0b0001)
for mask in range(1 << n):
for v in range(n):
if dp[mask][v] == INF: continue
if not (mask >> v) & 1: continue # v must be in mask
for u in range(n):
if (mask >> u) & 1: continue # u must not be visited
new_mask = mask | (1 << u)
dp[new_mask][u] = min(dp[new_mask][u], dp[mask][v] + dist[v][u])
full_mask = (1 << n) - 1
return min(dp[full_mask][v] + dist[v][0] for v in range(1, n))
dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
print('TSP minimum tour cost:', tsp(dist)) # should be 80複数ビットマスク：フィールドの抽出
単一のビットだけでなく、複数ビットのフィールド、つまり連続したビット範囲を抽出したい場合があります。位置startからstart+length-1までのビットを抽出するには、length個の連続した1ビットからなるマスクを作成します。具体的にはmask = (1 << length) - 1とし、続いて(n >> start) & maskを計算します。
このテクニックは、複数の小さな値を1つの整数に格納する、パックされた整数形式（IPアドレス、ピクセルデータ、ハードウェアレジスタなど）の解析に使われます。たとえば、16ビットのRGB565ピクセルでは、赤をビット15-11、緑を10-5、青を4-0に格納します。
def extract_field(n, start, length):
mask = (1 << length) - 1 # e.g., length=3 => mask=0b111
return (n >> start) & mask
# RGB565 pixel format: RRRRRGGGGGGBBBBB
pixel = 0b1111100111001000 # 63432
red = extract_field(pixel, 11, 5) # bits 15-11
green = extract_field(pixel, 5, 6) # bits 10-5
blue = extract_field(pixel, 0, 5) # bits 4-0
print(f'Pixel: {hex(pixel)}')
print(f'Red: {red} ({bin(red)})')
print(f'Green: {green} ({bin(green)})')
print(f'Blue: {blue} ({bin(blue)})')
# Packing values back
def pack_rgb565(r, g, b):
return (r << 11) | (g << 5) | b
packe = pack_rgb565(red, green, blue)
print(f'Repacked: {hex(packed) if (packed := pack_rgb565(red,green,blue)) else 0}')面接問題におけるビットマスク
ビットマスクは、面接問題でよく次のような形で登場します。
- 部分集合の列挙：0から2^n-1までのマスクを使い、2^n個の部分集合をすべて反復処理する
- 状態圧縮DP：訪問済みのノードや要素の集合を、DPの状態内でビットマスクとして表す
- 権限システム：READ/WRITE/EXECUTEフラグをORで組み合わせ、ANDで確認する
- グリッドの訪問済み管理：小さなグリッドでは、訪問済みセルを1つの整数にまとめる
ビットマスクが有効である重要な目印は、問題が小さな集合（n ≤ 20個の要素）を扱い、要素が含まれるかどうかの組み合わせを追跡する必要があることです。より大きな集合には、別の表現方法が必要です。
# Subset sum with bitmask enumeration
def subset_sum_exists(nums, target):
n = len(nums)
for mask in range(1 << n):
total = sum(nums[k] for k in range(n) if (mask >> k) & 1)
if total == target:
subset = [nums[k] for k in range(n) if (mask >> k) & 1]
print(f'Found subset {subset} summing to {target}')
return True
return False
subset_sum_exists([3, 1, 4, 1, 5], 10) # finds a subset summing to 10
# Check if permutation covers all required elements (bitmask approach)
required = 0b11111 # need all 5 elements
visited = 0b01101 # visited elements 0, 2, 3
all_visited = (visited & required) == required
print(f'All required visited: {all_visited}') # False: missing bits 1 and 4効率的なビット列挙のテクニック
マスク内のセットされているビットを反復処理する場合、よく使われるテクニックが2つあります。1つ目はシフトして確認する方法です。右にシフトしながらLSBを確認します。2つ目は最下位セットビットを分離する方法です。n & -nで最下位のセットビットを分離して処理し、その後n &= n - 1でクリアします。2つ目の方法はセットされているビットだけを処理するため、マスクが疎な場合に高速です。
Pythonでは、popcountにbin(n).count('1')やn.bit_count()（3.10以降）も使えます。各セットビットの位置を求めるには、最上位のセットビットに対してn.bit_length() - 1を使います。
# Iterate over set bit positions
def set_bit_positions(n):
positions = []
k = 0
while n:
if n & 1:
positions.append(k)
n >>= 1
k += 1
return positions
# Faster: use lowest-set-bit isolation
def set_bit_positions_fast(n):
positions = []
while n:
lsb = n & -n # isolate lowest set bit
k = lsb.bit_length() - 1 # position of that bit
positions.append(k)
n &= n - 1 # clear lowest set bit
return positions
mask = 0b10110101
print(f'Set positions (naive): {set_bit_positions(mask)}')
print(f'Set positions (fast): {set_bit_positions_fast(mask)}')
print(f'Bit count: {bin(mask).count("1")}')
print(f'Highest set bit: {mask.bit_length() - 1}')理解度チェック
このレッスンで扱ったData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認します。
レッスンのまとめ
このレッスンでは、4つの基本的なビットマスク操作は、セット（OR）、クリア（AND-NOT）、トグル（XOR）、確認（shift-AND）であること、整数で部分集合を表現でき、各ビットが要素1つの所属を表すため、2^n個の部分集合を列挙できること、そして複数ビットフィールドの抽出とビットマスクDPは、より複雑な状態のエンコードにも同じマスクの原則を使うことを学びました。次は、このレッスンと前のレッスンで学んだテクニックを使って、ビットのカウント、欠損値、ビット反転について学びます。
よくある質問
「ビットマスク：セット、クリア、反転、確認」レッスンは無料ですか？
はい。「ビットマスク：セット、クリア、反転、確認」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「ビットマスク：セット、クリア、反転、確認」で何を学びますか？
個々のビットをセット、クリア、反転、確認するヘルパーを実装し、部分集合列挙問題で部分集合を表すためにビットマスクを適用します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「ビットマスク：セット、クリア、反転、確認」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- ビット演算子：AND、OR、XOR、NOT、シフト
- Single NumberとXORの性質
- ビットマスク：セット、クリア、反転、確認
- ビットカウント、Missing Number、ビット反転