一文搞懂位运算实战：状态压缩与异或去重

问题背景：为什么位运算值得单独训练

很多算法题表面在考数组、字符串、回溯或图论，真正卡点却在“如何高效表示状态”。如果直接使用数组、集合或布尔列表，代码往往能通过小规模数据，但在元素数量增加后面临内存膨胀、复制昂贵、哈希判断不稳定等问题。位运算提供了一种更底层的表达方式：用整数的某一位表示某个元素是否存在，用异或快速抵消成对信息。

本文聚焦两类高频技巧：

1. 状态压缩：把一个有限集合编码成整数，适合子集枚举、权限标记、回溯状态传递。
2. 异或消重：利用 x ^ x = 0、x ^ 0 = x 的性质，在线性时间内找到只出现一次的数字。

它们共同的优势是：常数小、无需额外容器、适合面试中追求最优复杂度的场景。

方案对比：集合、布尔数组与整数位掩码

以“标记若干元素是否被选择”为例，常见方案有三种。

• 使用 set：语义清晰，支持动态增删，但每次哈希存储都有额外开销，状态复制和枚举子集不够直接。
• 使用布尔数组：访问速度快，但状态传递时需要复制列表，回溯代码容易出现忘记恢复现场的问题。
• 使用整数位掩码：一个整数即可表示集合，交并补、翻转、枚举子集都能通过位运算完成；缺点是位数受语言整数宽度和题目规模限制。

在 Python 中整数精度可以自动扩展，但工程和面试题通常仍建议控制在 64 位以内；在 Java、C++ 等语言中则要明确区分 int 与 long。

核心语法：看懂五类高频位操作

状态压缩的关键是把第 i 位当作元素 i 的状态。

• 判断是否存在：mask & (1 << i)，结果非零表示存在。
• 添加元素：mask | (1 << i)，无论原来是否存在，结果都为 1。
• 删除元素：mask & ~(1 << i)，把目标位清零。
• 切换状态：mask ^ (1 << i)，存在变不存在，不存在变存在。
• 统计元素数量：mask.bit_count()，Python 3.8 以下可用 bin(mask).count("1")。

需要特别注意运算优先级：判断语句中建议写成 (mask & (1 << i)) != 0，不要省略括号后直接依赖位运算与比较运算的优先级。

实战一：用状态压缩枚举所有子集

题目描述

给定一个不含重复元素的数组 nums，枚举它的所有子集。数组长度不超过 20。

解题思路

如果数组长度为 n，每个元素都有“选”或“不选”两种状态，因此共有 2^n 个子集。令整数 mask 从 0 遍历到 (1 << n) - 1，若第 i 位为 1，就把 nums[i] 放入当前子集。

下面代码可以直接运行：

from typing import List


def subsets(nums: List[int]) -> List[List[int]]:
    """使用位掩码枚举 nums 的所有子集。"""
    n = len(nums)
    result = []

    # mask 的每一位表示对应下标是否被选择
    for mask in range(1 << n):
        current = []
        for i in range(n):
            # 第 i 位为 1，说明 nums[i] 在当前集合中
            if mask & (1 << i):
                current.append(nums[i])
        result.append(current)

    return result


if __name__ == "__main__":
    print(subsets([1, 2, 3]))

输出包含空集、单元素集合和完整集合，共 8 种结果。

复杂度分析

• 时间复杂度：O(n · 2^n)。共有 2^n 个掩码，每个掩码最多检查 n 位。
• 空间复杂度：O(n · 2^n)，用于保存所有子集；如果只实时处理子集，不计输出，则额外辅助空间为 O(n)。

这种写法和回溯法都能得到正确答案。回溯更适合剪枝题，位枚举更适合“每个组合都必须检查”且 n ≤ 20 的场景。

实战二：回溯中传递位掩码状态

题目描述

给定一个只包含小写字母的字符串数组，找出其中没有重复字符的字符串排列组合。也可以把它理解为：在选择若干字符串时，要求所有字符串的字符集互不相交。

解题思路

把每个字符串预先压缩成一个 26 位整数。两个集合没有交集，当且仅当：

mask_a & mask_b == 0

回溯时不再传递字符集合，而是传递一个整数 used。选择当前字符串前判断交集，选择后通过按位或合并状态。

from typing import List


def max_unique_concat(words: List[str]) -> int:
    """选择若干互不重复字符的单词，求最大总长度。"""
    masks = []
    lengths = []

    for word in words:
        mask = 0
        valid = True

        for ch in word:
            bit = 1 << (ord(ch) - ord("a"))
            if mask & bit:  # 单词内部已有重复字符
                valid = False
                break
            mask |= bit

        if valid:
            masks.append(mask)
            lengths.append(len(word))

    answer = 0

    def dfs(index: int, used: int, total: int) -> None:
        nonlocal answer
        answer = max(answer, total)

        for i in range(index, len(masks)):
            # 两个字符集合相交，不能同时选择
            if used & masks[i]:
                continue

            # 按位或相当于集合求并集
            dfs(i + 1, used | masks[i], total + lengths[i])

    dfs(0, 0, 0)
    return answer


if __name__ == "__main__":
    print(max_unique_concat(["un", "iq", "ue"]))

复杂度分析

• 设合法字符串数量为 m，最坏情况下时间复杂度为 O(2^m)。
• 预处理每个字符串总耗时为所有字符数之和，记为 O(L)。
• 递归栈空间为 O(m)，每个状态只用一个整数保存。

位掩码在这里的价值不只是省空间，更重要的是把“集合是否冲突”从逐字符比较变成一次按位与，剪枝判断非常直接。

实战三：异或找出只出现一次的数字

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现一次的元素。要求线性时间复杂度，并且尽量不使用额外空间。

解题思路

异或有三个核心性质：

1. a ^ a = 0，成对数字会相互抵消。
2. a ^ 0 = a，初始值设为 0 不影响答案。
3. 异或满足交换律和结合律，因此数字顺序不影响结果。

把数组中所有数字连续异或，出现两次的数字全部变成 0，最后剩下的就是唯一数字。

from typing import List


def single_number(nums: List[int]) -> int:
    """利用异或抵消成对数字，返回只出现一次的数字。"""
    result = 0
    for num in nums:
        result ^= num
    return result


if __name__ == "__main__":
    sample = [4, 1, 2, 1, 2]
    print(single_number(sample))  # 输出 4

复杂度分析

• 时间复杂度：O(n)，只遍历一次数组。
• 空间复杂度：O(1)，只使用一个整数变量。

相比哈希表计数的 O(n) 空间，异或解法在“其余数字恰好出现两次”这一强约束下达到了空间最优。

扩展：两个只出现一次的数字怎么办

如果数组中有两个数字 a、b 各出现一次，其余数字出现两次，直接整体异或只能得到 a ^ b。还需要按某一个差异位把原数组分成两组：

• 差异位为 0 的数字异或得到其中一个答案；
• 差异位为 1 的数字异或得到另一个答案。

取最低位差异位可写为：

diff = xor_sum & -xor_sum

这是负数补码表示下的常见技巧。若考虑跨语言兼容，也可以写成 diff = xor_sum & (~xor_sum + 1)，但 Python 中前者更简洁。

完整代码如下：

from typing import List


def two_single_numbers(nums: List[int]) -> List[int]:
    """返回数组中两个只出现一次的数字。"""
    xor_sum = 0
    for num in nums:
        xor_sum ^= num

    # 找到最低的一个不同二进制位
    diff_bit = xor_sum & -xor_sum
    first = 0

    for num in nums:
        if num & diff_bit:
            first ^= num

    second = xor_sum ^ first
    return [first, second]


if __name__ == "__main__":
    print(two_single_numbers([1, 2, 1, 3, 2, 5]))

时间复杂度仍为 O(n)，空间复杂度为 O(1)。

避坑总结：位运算最容易出错的 4 个细节

1. 状态压缩规模失控

错误现象：数组长度达到 25 或 30 后，程序看似正确却运行很久。原因是子集数量按 2^n 增长，n = 30 时已经超过十亿级状态。

修正方法：看到“枚举全部子集”先确认 n 的范围。通常 n ≤ 20 可以直接枚举，20 < n ≤ 25 要考虑折半搜索或强剪枝，更大的数据规模不能把状态压缩当作万能解法。

2. 删除位时误用异或

错误现象：写出 mask ^= (1 << i) 表示删除元素，但当目标位本来就是 0 时，异或反而把它变成 1。

修正方法：语义要区分清楚。添加使用 mask | bit，删除使用 mask & ~bit，只有“翻转选择状态”时才使用 mask ^ bit。

3. 异或题忽视前提条件

错误现象：数组中某个数字出现三次，或存在多个不同数字各出现一次，仍然直接整体异或，得到一个无法解释的结果。

修正方法：普通异或消重只保证成对数字抵消。三次出现可考虑按二进制位统计；两个唯一数字需要按差异位分组；更一般的频次问题应使用哈希计数或逐位模运算。

4. 移位下标和编号不统一

错误现象：字符题中有的地方使用 ord(ch) - ord("a")，有的地方直接使用 ord(ch)，导致掩码位超出预期；集合题中把元素值和数组下标混用，重复值还会覆盖状态。

修正方法：状态压缩前先明确“第几位代表谁”。对下标集合使用 0 到 n-1；对小写字母使用 0 到 25；若元素值有重复或范围很大，应先离散化，不能直接拿原值移位。

结语

位运算不是炫技，而是把有限状态压缩到机器整数中的工程化表达。状态压缩适合小规模集合、子集枚举和回溯剪枝；异或适合处理严格成对出现的数据。掌握判断、添加、删除、切换、交集、并集和差异位这几组基本操作后，很多看似需要哈希表或多维数组的题目，都能简化为一次遍历和一个整数。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。