位运算技巧详解

一句话总结

位运算直接操作整数的二进制位，是唯一能达到 O(1) 且常数极小的运算。面试中它主要用于三类场景：异或的性质（消消乐）、n & (n-1)（清掉最低位的 1）、掩码与位移（状态压缩）。掌握十来个固定套路即可覆盖绝大多数位运算题。

⊕

异或 ^

a^a=0、a^0=a、满足交换律结合律 → "成对消除"。

🎯

n & (n-1)

把 n 的二进制中最低位的 1 清零，用于数 1 的个数、判 2 的幂。

🔻

n & (-n)

lowbit：取出最低位的 1 所对应的值，树状数组的基础。

🎭

掩码 mask

用一个整数的每一位表示一个布尔状态，状态压缩 DP。

一、基础运算符回顾

运算符	名称	规则（逐位）	典型用途
`&`	按位与	都为 1 才 1	取指定位、清零、判奇偶 `n&1`
`\|`	按位或	有 1 就 1	设置某位为 1
`^`	按位异或	不同为 1	消去成对元素、不借位加法
`~`	按位取反	0↔1	构造掩码（注意符号位）
`<<`	左移	整体左移，低位补 0	× 2ᵏ
`>>`	右移	整体右移（算术右移补符号位）	÷ 2ᵏ（向下取整）

二、高频技巧清单

2.1 判断奇偶 / 乘除 2 的幂

x & 1              # == 1 为奇数，== 0 为偶数（比 x % 2 快）
x << 1             # x * 2
x >> 1             # x // 2（向下取整）
x << k            # x * 2^k

2.2 交换两个数（不用临时变量）

a ^= b            # a = a ^ b
b ^= a            # b = b ^ (a ^ b) = 原来的 a
a ^= b            # a = (a ^ b) ^ a = 原来的 b
# ⚠️ 注意：a 和 b 是同一个变量时会变成 0！面试常问但工程上不推荐

2.3 操作第 k 位（从 0 开始，从右往左数）

x | (1 << k)       # 把第 k 位设为 1
x & ~(1 << k)      # 把第 k 位清为 0
x ^ (1 << k)       # 翻转第 k 位（0→1, 1→0）
(x >> k) & 1      # 取出第 k 位的值
x & ((1 << k) - 1)  # 取 x 的低 k 位

2.4 n & (n-1)：清掉最低位的 1

# 数二进制中 1 的个数（191 位 1 的个数）
def hammingWeight(n):
    cnt = 0
    while n:
        n &= n - 1              # 每次抹掉最低位的 1
        cnt += 1
    return cnt                   # 循环次数 = 1 的个数，比逐位检查 32 次更快

# 判断是否是 2 的幂（231）：2 的幂只有一位是 1
def isPowerOfTwo(n):
    return n > 0 and (n & (n - 1)) == 0

# 判断是否是 4 的幂（342）：先满足 2 的幂，再检查 1 在奇数位
def isPowerOfFour(n):
    return n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) != 0

2.5 lowbit：n & (-n)

💡 原理：计算机中 -n 用补码表示 = ~n + 1。这让 n 最低位的 1 及其右侧保持不变，其左侧全部取反。相与后，只剩下最低位的那个 1。
用途：树状数组（Fenwick Tree）的索引推进、统计 1 的个数、求最低位 1 的位置。

def lowbit(n):
    return n & -n            # 如 n = 12 (1100) → 4 (0100)

# 用 lowbit 数 1 的个数
def count_ones(n):
    cnt = 0
    while n:
        n -= n & -n           # 减掉最低位的 1
        cnt += 1
    return cnt

三、经典面试题套路

3.1 只出现一次的数字（136）

def singleNumber(nums):
    ans = 0
    for x in nums:
        ans ^= x                 # 成对的全部抵消，剩下的就是落单的
    return ans
# 复杂度 O(n) 时间、O(1) 空间 —— 不用哈希表

3.2 只出现一次的数字 II（137）：每个位单独统计

def singleNumber(nums):
    ans = 0
    for k in range(32):           # 逐位统计
        cnt = sum((x >> k) & 1 for x in nums)
        if cnt % 3:                   # 出现 3 次的会被 % 3 消掉
            ans |= 1 << k
    # 处理负数：Python 整数无限长，需转回有符号 32 位
    return ans - (1 << 32) if ans >= (1 << 31) else ans

3.3 只出现一次的数字 III（260）：分组异或

def singleNumber(nums):
    xor_all = 0
    for x in nums:
        xor_all ^= x             # = a ^ b（两个落单数）

    # 取出 a^b 最低位的 1 —— 说明 a 和 b 在这一位上不同
    diff = xor_all & -xor_all

    a = b = 0
    for x in nums:
        if x & diff:             # 按这一位是否为 1 分成两组
            a ^= x               # 每组里成对的仍会抵消，各剩一个落单数
        else:
            b ^= x
    return [a, b]

3.4 不用加减号做加法（371 / 剑指 Offer 65）

def add(a, b):
    while b:
        carry = (a & b) << 1     # 进位：只有两位都是 1 才产生进位
        a = a ^ b                # 不进位相加：异或就是"半加"
        b = carry                # 把进位再加回去，反复直到进位为 0
    return a

# 剑指 Offer 65（Python 需处理 32 位溢出与负数）
def add_32(a, b):
    MASK = 0xFFFFFFFF
    a, b = a & MASK, b & MASK
    while b:
        a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK
    return a if a <= 0x7FFFFFFF else ~ (a ^ MASK)

3.5 缺失的数字 / 找不同（268 / 389）

# 268 缺失的数字：0..n 中缺一个 → 把下标和值一起异或
def missingNumber(nums):
    ans = len(nums)
    for i, x in enumerate(nums):
        ans ^= i ^ x             # 成对抵消，缺的那个会留下来
    return ans

# 389 找不同：s 比 t 多一个字符
def findTheDifference(s, t):
    ans = 0
    for c in s + t:
        ans ^= ord(c)
    return chr(ans)

四、状态压缩

4.1 用一个整数表示集合

当元素个数 ≤ 20~25 时，可以用一个整数的每一位表示"第 i 个元素是否被选中"，从而把集合状态压缩成一个 int，配合 DP 使用。

S = 0                      # 空集合
S |= 1 << i             # 加入元素 i
S &= ~(1 << i)          # 移除元素 i
(S >> i) & 1            # 判断 i 是否在集合中
S & (1 << i)            # 同上（非 0 即存在）
S1 | S2                  # 并集
S1 & S2                  # 交集
bin(S).count('1')       # 集合大小（1 的个数）

# 枚举 S 的所有非空子集（经典技巧）
sub = S
while sub:
    # 处理子集 sub
    sub = (sub - 1) & S    # 下一个子集

4.2 应用题目

题目	思路
78 子集	用 mask 从 0 到 2ⁿ-1 枚举所有子集
698 / 473 划分为 k 个相等的子集	状态压缩 DP + 记忆化
847 访问所有节点的最短路径	BFS + 状态压缩（当前节点, 已访问集合）
943 最短超级串	状压 DP：dp[mask][i]
691 贴纸拼词	状压 DP：用 mask 表示已拼出的字符

五、注意事项与陷阱

⚠️ 常见坑：
① 运算符优先级：&、^、| 的优先级低于 == 和比较运算符。写 if n & 1 == 1 实际会被解析成 if n & (1 == 1)！必须加括号：if (n & 1) == 1。
② Python 整数无限精度：负数右移会无限补符号位，~n 的结果和 C/Java 不同。处理 32 位题时需手动 & 0xFFFFFFFF 掩码。
③ 位移位数超限：C/C++ 中位移 ≥ 字长属未定义行为。
④ 可读性：a ^= b; b ^= a; a ^= b 交换法在 a、b 同址时会清零，且现代编译器下并不比临时变量快，工程代码不推荐。

记忆口诀：
成对消除用异或；
数 1、判 2 的幂用 n & (n-1)；
取最低位 1 用 n & -n；
设位/清位/翻位用 1 << k 配合 | &~ ^；
集合状态压成 int，枚举子集用 (sub-1) & S。