DSA Interview Prep · 课时

位掩码：设置、清除、翻转与检查

Q: 「位掩码：设置、清除、翻转与检查」这节课中我会学到什么？

实现用于设置、清除、翻转和检查单个位的辅助函数，并在子集枚举问题中使用位掩码表示子集。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

实现用于设置、清除、翻转和检查单个位的辅助函数，并在子集枚举问题中使用位掩码表示子集。

位掩码：设置、清除、翻转与检查 是 CoddyKit 上的免费 DSA Interview Prep 课时。这是第 3 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。

什么是位掩码

位掩码是一个整数，用于选择、修改或测试另一个整数中的特定位。掩码会在您关注的位置设为 1，在其他位置设为 0。位掩码与按位运算符结合使用，可以在不影响其他位的情况下执行细粒度的位操作。

四种基本的掩码操作是：设置（将一位置为 1）、清除（将一位置为 0）、切换（翻转一位）和检查（测试一位是否为 1）。它们分别使用不同的运算符——OR、AND 与 NOT 的组合、XOR 和 AND——并配合掩码 1 << k。

# 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 运算，因此保持不变。

设置位具有幂等性——多次调用的效果与调用一次相同。如果第 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) 的所有位都设为 1，只有第 k 位为 0。与 0 进行 AND 运算会强制目标位变为 0；与 1 进行 AND 运算则会保留其他所有位。

与设置位一样，清除位也具有幂等性。清除一个已经为 0 的位不会改变数字。在 Python 中，~(1 << k) 对任意 k 都能正确工作，因为 Python 会自动处理符号扩展——从概念上说，补码的所有更高位都设为 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 应用于单个位时的基本性质。

切换是四种操作中唯一一种不具有幂等性的操作——调用两次会恢复为原始值。因此，它非常适合在两种状态之间交替的功能，例如开关，或紧凑整数表示中的布尔标志。

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))，以获得布尔结果。

检查位是非破坏性的，不会修改 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 在子集中，第 k 位就为 1，否则为 0。这样可以将一个子集压缩为单个整数，并实现 O(1) 操作：成员测试（mask & (1 << k)）、添加元素（mask | (1 << k)）、移除元素（mask & ~(1 << k)）以及集合并集/交集（mask1 | mask2 和 mask1 & mask2）。

对于 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)，因为每个元素有三种状态：位于外层掩码但不在子掩码中、同时位于两者中，或两者都不在其中。

这种技术会出现在“将数组划分为 XOR 相等的子集”或“找出任意子集的最大 AND 值”等问题中。高效枚举子掩码的能力是高级位掩码动态规划的典型特征。

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 用于解决状态包含 the 已访问元素子集 的问题。经典示例是旅行商问题（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

多位掩码：提取字段

有时您需要提取的不只是单个位，而是一个多位字段——一段连续的位。要提取从起始位置到起始位置加长度减 1 的位，请创建一个由 length 个连续 1 位组成的掩码：mask = (1 << length) - 1，然后使用 (n >> start) & mask。

这种技术用于解析打包整数格式（例如 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 状态中使用位掩码编码已访问节点或元素的集合
权限系统：使用 OR 组合 READ/WRITE/EXECUTE 标志，使用 AND 进行检查
网格访问跟踪：对于较小的网格，将已访问的单元格打包到一个整数中

位掩码有用的一个重要信号是：问题涉及一个较小的集合（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

高效枚举位的技巧

遍历掩码中的置位位时，常用两种技术。第一种是移位并检查方法：向右移位并检查 LSB。第二种是隔离最低置位位方法：使用 n & -n 隔离最低置位位，处理它，然后使用 n &= n - 1 将其清除。第二种方法只访问置位位，因此掩码稀疏时速度更快。

在这种语言中，您还可以使用 bin(n).count('1') 或 n.bit_count()（3.10 及更高版本）统计 1 位的数量。要获取每个置位位的位置，可以使用 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}')

快速检查

检查您对本课数据结构与算法——编程面试准备相关概念的理解。

课程回顾

本课介绍了：the 四种基本位掩码操作分别是设置（OR）、清除（AND-NOT）、翻转（XOR）和检查（移位后使用 AND），整数可以表示子集，其中每一位编码一个元素是否属于该集合，从而支持 2^n 个子集的枚举，以及多位字段提取和位掩码 DP 使用相同的掩码原理来编码更复杂的状态。接下来我们将使用本课和上一课的技术，学习位计数、缺失数字和位反转。

常见问题解答

「位掩码：设置、清除、翻转与检查」课时是免费的吗？

是的 — 「位掩码：设置、清除、翻转与检查」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。

「位掩码：设置、清除、翻转与检查」这节课中我会学到什么？

实现用于设置、清除、翻转和检查单个位的辅助函数，并在子集枚举问题中使用位掩码表示子集。你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 DSA Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 3 节课，共 4 节。

「位掩码：设置、清除、翻转与检查」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 DSA Interview Prep 课中编写并运行代码吗？

能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 DSA Interview Prep