DSA Interview Prep · レッスン

ビットカウント、Missing Number、ビット反転

DPと最下位のセットビットの工夫を使って0〜nのビット数を計算し、XORで欠落した数を見つけ、32ビット整数のビットを反転します。

「ビットカウント、Missing Number、ビット反転」はCoddyKit上の無料DSA Interview Prepレッスンです。これはレッスン4/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。

ビットカウント問題の概要

Counting Bits問題（LeetCode 338）では、nが与えられたとき、サイズn+1の配列ansを返します。ans[i]はiに含まれる1ビットの数です。素朴な方法では各数のビットを個別に数えるため、O(n log n)かかります。DPを使う方法では、iとその半分、または最下位セットビットとの関係を利用することでO(n)を実現できます。

DPを支える重要な観察は2つあります。(1)i >> 1は最下位ビットを削除するため、bits[i] = bits[i >> 1] + (i & 1)となります。(2)最下位セットビットをクリアすると、bits[i] = bits[i & (i-1)] + 1となります。どちらも時間計算量はO(n)、空間計算量はO(n)（出力配列のため）です。

def count_bits_v1(n):
    # O(n log n): naive individual count
    return [bin(i).count('1') for i in range(n + 1)]

def count_bits_dp(n):
    # O(n): DP using right shift
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)   # i >> 1 drops last bit
    return dp

def count_bits_dp2(n):
    # O(n): DP using lowest-set-bit trick
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i & (i - 1)] + 1   # i & (i-1) clears lowest set bit
    return dp

n = 10
print('Naive:', count_bits_v1(n))
print('DP v1:', count_bits_dp(n))
print('DP v2:', count_bits_dp2(n))

DPの漸化式が成り立つ理由

右シフトによる漸化式dp[i] = dp[i >> 1] + (i & 1)では、2で割ること（右シフト）によって最後のビットを削除します。最後のビットが1ならカウントは1増え、0なら変化しません。したがって、bits[i] = bits[i // 2] + (i mod 2)となります。

最下位セットビットによる漸化式dp[i] = dp[i & (i-1)] + 1では、i & (i-1)によって右端の1ビットをクリアするため、iよりもセットビットが1つ少なくなります。したがって、カウントはその値のカウントに1を加えたものです。どちらの漸化式もiを昇順に処理するため、小さい部分問題が必ず先に解かれます。

# Trace both recurrences for i = 0..8
print('i | i>>1 | i&1 | dp[i>>1]+(i&1) | i&(i-1) | 1+dp[i&(i-1)]')
print('-' * 60)
dp = [0] * 9
for i in range(1, 9):
    # Right shift method
    v1 = dp[i >> 1] + (i & 1)
    # Lowest set bit method
    v2 = dp[i & (i - 1)] + 1
    dp[i] = v1   # either works
    print(f'{i:2d} ({bin(i)[2:]:4s}) | {i>>1:2d} | {i&1} | {v1}               | {i&(i-1):2d}      | {v2}')
print('\nFinal dp:', dp)

Missing Number：XORと加算によるアプローチ

Missing Number問題（LeetCode 268）では、[0, n]の範囲にある相異なるn個の数の配列が与えられ、そのうち1つが欠けています。XORによるアプローチでは、インデックス0..nのすべてと配列内のすべての値をXORします。同じ値の組は打ち消し合い、欠けている数だけが残ります。加算によるアプローチでは、expected = n*(n+1)//2を計算し、expected - sum(nums)を返します。

どちらも時間計算量はO(n)、空間計算量はO(1)です。XORによるアプローチは、固定幅整数を使う言語でもオーバーフローの可能性を避けられるため、より堅牢です。Pythonでは整数が任意精度なので、どちらも問題なく動作します。

def missing_xor(nums):
    n = len(nums)
    result = n
    for i, val in enumerate(nums):
        result ^= i ^ val   # each index i cancels its matching value
    return result

def missing_sum(nums):
    n = len(nums)
    return n * (n + 1) // 2 - sum(nums)

test_cases = [
    [3, 0, 1],           # missing 2
    [0, 1],              # missing 2
    [9,6,4,2,3,5,7,0,1], # missing 8
    [0],                 # missing 1
]
for nums in test_cases:
    print(f'{nums} => XOR={missing_xor(nums)}, Sum={missing_sum(nums)}')

32ビット整数のビット反転

Reverse Bits問題（LeetCode 190）では、32ビット符号なし整数の2進表現を反転します。反復的なアプローチでは、入力の右から左へ32ビットを1つずつ処理し、出力の左から右へ配置します。各反復では、n & 1で右端のビットを取り出し、出力を左シフトして場所を空け、そのビットをORで追加してからnを右シフトします。

32回の反復が終わると、出力整数にはnの32ビットが逆順で格納されます。これはO(32) = O(1)で、呼び出しごとの計算量はO(1)です。また、8ビット単位のキャッシュを使って繰り返し呼び出す場合は、償却計算量もO(1)になります。

def reverse_bits(n):
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)  # shift result left, OR in rightmost bit
        n >>= 1                            # move to next bit
    return result

# Test with known values
print(reverse_bits(0b00000010100101000001111010011100))  # 964176192
print(reverse_bits(0b11111111111111111111111111111101))  # 3221225471
print(reverse_bits(0))   # 0
print(reverse_bits(1))   # 2147483648 (bit 0 goes to bit 31)
print(reverse_bits(0b10000000000000000000000000000000))  # 1

ビット反転：分割統治

より高速なO(log 32) = O(1)のアプローチでは、分割統治による交換を使ってビットを反転します。まず隣接するビットを交換し、次に隣接する2ビットのグループ、続いて4ビットのグループというように交換します。各交換レベルでは、マスクで交互に並ぶグループを分離し、シフトして交互に配置します。5回交換すると、32ビットすべてが反転します。

このアプローチは入力にかかわらずO(1)個の固定操作で実行でき、ハードウェア実装でも使われます。マスクは定数で、0x55555555（交互の01パターン）、0x33333333（交互の0011）、0x0f0f0f0f（交互の00001111）などです。

def reverse_bits_dc(n):
    # Treat n as 32-bit unsigned
    n &= 0xFFFFFFFF
    # Swap adjacent bits
    n = ((n & 0x55555555) << 1)  | ((n >> 1)  & 0x55555555)
    # Swap adjacent 2-bit groups
    n = ((n & 0x33333333) << 2)  | ((n >> 2)  & 0x33333333)
    # Swap adjacent 4-bit groups
    n = ((n & 0x0f0f0f0f) << 4)  | ((n >> 4)  & 0x0f0f0f0f)
    # Swap adjacent bytes
    n = ((n & 0x00ff00ff) << 8)  | ((n >> 8)  & 0x00ff00ff)
    # Swap adjacent 16-bit halves
    n = ((n & 0x0000ffff) << 16) | ((n >> 16) & 0x0000ffff)
    return n & 0xFFFFFFFF

# Verify against iterative version
def reverse_bits_iter(n):
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1); n >>= 1
    return result

for test in [0b10110100, 0b11111111, 0, 1, 0xDEADBEEF]:
    assert reverse_bits_dc(test) == reverse_bits_iter(test)
    print(f'{test:#010x} reversed: {reverse_bits_dc(test):#010x}')

1のビット数（ハミング重み）

Number of 1 Bits問題（LeetCode 191）では、符号なし整数のハミング重み（popcount）を求めます。アプローチにはそれぞれ異なるトレードオフがあります。素朴なループはO(32)、Brian Kernighan法はO(k)（kはセットビット数）、Pythonの組み込みn.bit_count()は3.10以降で利用できます。

Brian Kernighan法は、n & (n-1)のテクニックへの理解を示せるため、面接では好まれます。各反復で最下位セットビットを1つ削除するため、ループの回数は1ビットの数と正確に一致します。したがって、整数が疎な場合は32ビット全体を走査するよりも大幅に高速です。

def hamming_weight_naive(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

def hamming_weight_kernighan(n):
    count = 0
    while n:
        n &= n - 1   # clear lowest set bit
        count += 1
    return count

# Python 3.10+
# def hamming_weight_builtin(n): return n.bit_count()

for n in [0, 1, 11, 128, 255, 0xDEADBEEF]:
    naive = hamming_weight_naive(n)
    kern  = hamming_weight_kernighan(n)
    bits  = bin(n).count('1')
    print(f'{n:#012b} ({n:10d}): naive={naive}, kern={kern}, bin={bits}')

連続するビットの合計：累積アプローチ

範囲[l, r]内の1ビットの数を高速に数えたい場合があります。0..nについてセットビット数の累積和を作成します。prefix[i] = prefix[i-1] + bin(i).count('1')とします。すると、範囲[l, r]のカウントはprefix[r] - prefix[l-1]で求められます。これにより、O(n)の前処理の後、範囲クエリをO(1)で処理できます。

この方法は、範囲に対するビットベースの集計全般に一般化できます。たとえば、[l, r]内でセットビット数が偶数の数を数える場合も、異なる集計関数を使うだけで同じ累積のテクニックを利用できます。

def build_bit_prefix(n):
    prefix = [0] * (n + 2)
    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + bin(i).count('1')
    return prefix

def count_bits_range(prefix, l, r):
    return prefix[r] - prefix[l - 1]

# Build prefix for 0..15
prefix = build_bit_prefix(15)
print('Prefix sums (set bit counts up to i):')
for i in range(16):
    print(f'  i={i:2d} ({bin(i)[2:]:4s}): bits={bin(i).count("1")}, prefix={prefix[i]}')

# Range queries
print(f'\nSet bits in [5, 10]: {count_bits_range(prefix, 5, 10)}')
print(f'Set bits in [1, 15]: {count_bits_range(prefix, 1, 15)}')

負の数のビット反転

Pythonの整数は符号付きで、ビット幅が任意です。LeetCodeの問題でビットを反転するときは、入力を32ビット符号なし整数として扱う必要があります。処理前に入力を& 0xFFFFFFFFでマスクし、32ビットだけが考慮されるようにします。出力も符号なし32ビット整数（非負）にします。

2の補数表現の意味で負になる可能性があるPython整数が与えられた場合は、まず& 0xFFFFFFFFを適用して符号なし32ビット表現に変換してから反転します。結果は常に0以上2^32 - 1以下の非負整数です。

def reverse_bits_signed_safe(n):
    n &= 0xFFFFFFFF   # treat as 32-bit unsigned
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result & 0xFFFFFFFF

# Python treats -1 as all 1s in two's complement
print(f'-1 as 32-bit unsigned: {-1 & 0xFFFFFFFF:#010x}')  # 0xffffffff
print(f'Reversed: {reverse_bits_signed_safe(-1):#010x}')   # 0xffffffff (all 1s reversed = all 1s)

# -2 in 32-bit = 0xFFFFFFFE = 11...10
print(f'-2 as 32-bit unsigned: {-2 & 0xFFFFFFFF:#010x}')  # 0xfffffffe
print(f'Reversed: {reverse_bits_signed_safe(-2):#010x}')   # 0x7fffffff

ビット操作DP：ビット数のパターンを数える

ビットカウント問題から、ビットDPに共通するパターンが分かります。iより小さい値について答えが分かっていれば、定数時間のビット操作でiの答えを計算できます。このパターンは、[0, n]でセットビットがちょうどk個ある数を数える問題（2進数列挙を使います）や、各数を割り切る2の最大のべき乗を求める問題など、他のビットカウント問題にも一般化できます。

もう1つの有用な観察は、iのセットビット数が、各2のべき乗区間内で繰り返しパターンに従うことです。[2^k, 2^(k+1) - 1]のパターンは[0, 2^k - 1]と同じで、各値に1を加えたものになります。この範囲ではビットkが常にセットされているためです。

# Visualise the repeating pattern
def show_bit_pattern(n):
    bits = [bin(i).count('1') for i in range(n + 1)]
    print('i  | bits | pattern')
    for i, b in enumerate(bits):
        block = i.bit_length() - 1 if i > 0 else 0
        print(f'{i:2d} ({bin(i)[2:]:4s}) | {b} | block {block}')
    return bits

bits = show_bit_pattern(15)
# Verify the pattern: bits[i] = bits[i - highest_power] + 1 for i >= 2^k
print('\nVerify pattern:')
for i in range(1, 16):
    highest_pow = 1 << (i.bit_length() - 1)
    if highest_pow < i:
        prev_i = i - highest_pow
        print(f'bits[{i}] = bits[{prev_i}] + 1 = {bits[prev_i]} + 1 = {bits[i]}')

3つを組み合わせる：総合演習

面接問題の中には、ビットカウント、欠損値のロジック、ビット反転を1つの問題に組み合わせるものが多くあります。たとえば、要素がnビット整数である配列から、欠けている値を求める問題です。あるいは、ビットカウントのストリームから欠けている整数を復元する問題もあります。これらには、どのサブテクニックを適用すべきかを見極める力が必要です。

頭の中に判断の地図を作る練習をしましょう。問題に欠けている要素を見つけると書かれていたら、XORまたは加算を考えます。「1を効率的に数える」とあれば、Kernighan法またはDPを考えます。「ビットを反転する」とあれば、反復的な方法または分割統治を考えます。これらが面接におけるビット操作の3つの基本ツールです。

# Integrated exercise: given bit-count array, find the missing number
# arr[i] = number of 1 bits in i, for all i in 0..n except one
# Reconstruct the missing number

def find_missing_from_bit_counts(bit_counts, n):
    # Rebuild full count array
    full = [bin(i).count('1') for i in range(n + 1)]
    # Find which index is missing by comparing
    for i, count in enumerate(bit_counts):
        if full[i] != count:
            return i - 1  # the entry before the mismatch is missing
    return n  # last element missing

# Simpler: use XOR on indices matching bit counts
# (This is simplified for illustration)
bits = [0,1,1,2,1,2,2,3,0,1]  # bit counts for 0..9 with 8 missing
# Normal: [0,1,1,2,1,2,2,3,1,2]
# Missing is index 8
full = [bin(i).count('1') for i in range(10)]
missing_idx = None
for i in range(10):
    if i >= len(bits) or bits[i] != full[i]:
        missing_idx = i
        break
print(f'Missing number: {missing_idx}')

ビット反転のキャッシュ

ビット反転を繰り返し呼び出す場合（ハードウェアシミュレーションなど）は、8ビット単位で結果をキャッシュします。各バイトは0から255までの256通りしかないため、各値に対応する反転後のバイトをあらかじめ計算しておきます。32ビット整数を反転するには、4つの8ビットのチャンクに分割し、それぞれを反転して、順序を逆にして再構成します。

これにより、各呼び出しは4回のテーブル参照とビット操作だけで済み、大量処理では32回の反復ループよりも大幅に高速になります。キャッシュはO(256 × 8)時間で一度だけ構築し、その後のすべての呼び出しでO(1)で再利用できます。

# Build 8-bit reverse cache
def build_reverse_byte_cache():
    cache = [0] * 256
    for i in range(256):
        n, result = i, 0
        for _ in range(8):
            result = (result << 1) | (n & 1)
            n >>= 1
        cache[i] = result
    return cache

cache = build_reverse_byte_cache()

def reverse_bits_cached(n):
    return (cache[n & 0xFF] << 24 |
            cache[(n >> 8) & 0xFF] << 16 |
            cache[(n >> 16) & 0xFF] << 8 |
            cache[(n >> 24) & 0xFF])

# Test
for test in [0b10110100, 0b11111111, 0x12345678]:
    cached  = reverse_bits_cached(test)
    # Reference: iterative
    n, result = test, 0
    for _ in range(32): result = (result << 1) | (n & 1); n >>= 1
    assert cached == result
    print(f'{test:#010x} => {cached:#010x}')

理解度チェック

このレッスンで扱ったData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認します。

レッスンのまとめ

このレッスンでは、ビットカウントにはdp[i] = dp[i >> 1] + (i & 1)またはdp[i] = dp[i & (i-1)] + 1によるDPを使い、時間計算量O(n)で実行できること、欠損値は、すべてのインデックスとすべての値をXORするか、算術的な加算公式を使うことで、O(n)/O(1)で求められること、そして32ビットの反転はO(32)の反復処理、または分割統治によるマスクのテクニックで実行できることを学びました。次は単調スタックについて学び、増加と減少の不変条件、そして次に大きい要素のクエリから始めます。

よくある質問

「ビットカウント、Missing Number、ビット反転」レッスンは無料ですか？

はい。「ビットカウント、Missing Number、ビット反転」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。

「ビットカウント、Missing Number、ビット反転」で何を学びますか？

DPと最下位のセットビットの工夫を使って0〜nのビット数を計算し、XORで欠落した数を見つけ、32ビット整数のビットを反転します。ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

DSA Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。これはレッスン4/4です。

「ビットカウント、Missing Number、ビット反転」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このDSA Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

← DSA Interview Prepに戻る