位运算详解：运算符、技巧与示例

位运算解决什么问题

整数是一排二进制位，许多问题其实就是在处理这些位：rwx 这样的文件权限、功能开关、网络掩码、像素颜色、紧凑的选项集合、校验和与哈希。按位运算符让你一次操作就能读取和修改许多位，既节省内存又非常快。

面试题也常用到位运算技巧，因为它们能给出优雅的 O(1) 空间解法，例如在其他数字都出现两次时，找出只出现一次的那个数。

运算符

示例使用 a = 12（二进制 1100）和 b = 10（二进制 1010）。

a, b = 12, 10
print(bin(a), bin(b))         # 0b1100 0b1010
print(a & b, a | b, a ^ b)    # 8 14 6
print(~a, a << 1, a >> 2)     # -13 24 3
print(f"{a ^ b:04b}")         # 0110
print(int("1010", 2))         # 10

单个二进制位的操作

位的下标从最右边（最低有效位）开始，从 0 计数。掩码 1 << i 只有第 i 位为 1。

实例：统计二进制中 1 的个数

Brian Kernighan 的方法不断清除最低位的 1，直到什么都不剩，所以循环次数等于 1 的个数，而不是位的个数。以 x = 44（二进制 101100）为例追踪：

def count_bits(x):
    count = 0
    while x:
        x &= x - 1        # drop the lowest set bit
        count += 1
    return count

print(count_bits(44))     # 3
print((44).bit_count())   # 3
print((44).bit_length())  # 6

int.bit_count() 自 Python 3.10 起可用。int.bit_length() 返回用二进制表示该数所需的位数（不含符号）。

Python 中的经典技巧

from functools import reduce
from operator import xor

# Every number appears twice except one: pairs cancel out with XOR.
print(reduce(xor, [4, 1, 2, 1, 2]))   # 4

# Swap two integers without a temporary variable (for illustration only).
x, y = 5, 9
x ^= y; y ^= x; x ^= y
print(x, y)                            # 9 5

# Bitmask as a set: enumerate all subsets of 3 items.
items = ["a", "b", "c"]
for mask in range(1 << len(items)):
    print(mask, [items[i] for i in range(len(items)) if mask >> i & 1])
# 0 []
# 1 ['a']
# 2 ['b']
# 3 ['a', 'b']
# 4 ['c']
# 5 ['a', 'c']
# 6 ['b', 'c']
# 7 ['a', 'b', 'c']

掩码 0 是空集，5（二进制 101）对应 ['a', 'c']，7 则是全部三个元素。位掩码动态规划采用同样的思想，把掩码作为状态，适用于元素不超过约 20 个的问题，例如小规模输入上的旅行商问题。

另外两个经典用法：x & 1 对奇数为 1；把 0 到 n 的所有数与列表中的所有值一起做异或，可以找出那个缺失的数。

时间与空间复杂度

位掩码为每个可能的元素使用一个二进制位，所以 64 个标志可以放进一个 64 位整数，而不必用 64 个独立的布尔变量或列表元素。

常见错误

• 负数：Python 的整数表现得好像有无穷多个符号位，所以 ~5 是 -6，bin(-5) 是 -0b101，而不是补码字符串。要查看 32 位的位模式，请先加掩码：-5 & 0xFFFFFFFF。
• Python 中负数的右移是算术右移：-8 >> 1 是 -4，-1 >> 10 仍是 -1。
• 定宽语言中的溢出：在 Java 或 C 中，对 32 位 int 做 1 << 31 会变成负数或未定义行为；请使用 64 位类型，并写成 1L << 40 或 1ULL << 40。
• 混淆逻辑运算符与按位运算符：and 和 or（C 系语言中的 &&、||）返回真值，而 & 和 | 按位工作。
• 可读性：把 x * 2 换成 x << 1，在现代编译器或 Python 中都不会更快，反而让代码更难读。

实际应用

• Unix 文件权限：chmod 754 设置三组各 3 位的权限（rwx = 4 + 2 + 1）。
• 网络：IPv4 子网掩码，ip & mask 可得到 CIDR 地址块的网络地址。
• 标志与选项：Python 的 re.IGNORECASE | re.MULTILINE 和 enum.Flag 都用“或”来组合选项。
• 图形与颜色：24 位 RGB 值把红、绿、蓝打包成 (r << 16) | (g << 8) | b。
• 数据结构与算法：布隆过滤器、位集、树状数组（使用 i & -i）、哈希与校验和。
• 面试题：只出现一次的数字、比特位计数、2 的幂、颠倒二进制位、丢失的数字、用位掩码枚举子集、不使用 + 求两整数之和。