การนับบิต จำนวนที่หายไป และการกลับบิต

ภาพรวมปัญหาการนับบิต

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 ใช้งานได้

# 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)

จำนวนที่หายไป: วิธี XOR และผลรวม

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 บิต

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

การกลับบิต: แบ่งแล้วพิชิต

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 (น้ำหนักแฮมมิง)

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}')

ผลรวมบิตต่อเนื่อง: วิธีใช้คำนำหน้า

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)}')

การกลับลำดับบิตสำหรับจำนวนติดลบ

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 การจัดการบิต: รูปแบบการนับบิต

# 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]}')

รวมทั้งสามแนวคิด: แบบฝึกหัดบูรณาการ

# 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}')

การเก็บบิตไว้ในแคชสำหรับการกลับลำดับบิต

# 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}')

ตรวจสอบความเข้าใจ

สรุปบทเรียน