บิตมาสก์: ตั้งค่า ล้าง สลับ และตรวจสอบ

มาสก์บิตคืออะไร

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

ตั้งบิต: เปิดบิต

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

ล้างบิต: ปิดบิต

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

สลับบิต: กลับค่าบิต

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

ตรวจสอบบิต: ตรวจว่าบิตถูกตั้งค่าไว้หรือไม่

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

มาสก์บิตสำหรับแทนเซตย่อย

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

วนผ่านเซตย่อยทั้งหมดของมาสก์

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 ด้วยมาสก์บิต: ภาพรวมปัญหาเซลส์แมนเดินทาง

# 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

มาสก์หลายบิต: การดึงฟิลด์

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

มาสก์บิตในโจทย์สัมภาษณ์

# 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

เคล็ดลับการแจกแจงบิตอย่างมีประสิทธิภาพ

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

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

สรุปบทเรียน