第 46 章 位运算¶
配套例题：BISHI30 二进制数 1、BISHI31 二进制不同位数、BISHI32 被打乱的异或和 来源：S2
bit_op.cpp的技巧清单
语法层面的位运算符（含优先级、负数右移、~x = -x-1）已在
03-运算符与位运算 讲过。
本章讲算法层面：lowbit、子集枚举、状态压缩、异或的代数性质，
以及 Python 大整数带来的两个特殊后果。
46.1 六种运算与它们的算法含义¶
| 运算 | 记法 | 算法里干什么用 |
|---|---|---|
与 & |
\(x \wedge y\) | 取位、判断、集合交 |
或 \| |
\(x \vee y\) | 置位、集合并 |
异或 ^ |
\(x \oplus y\) | 翻转、不进位加法、集合对称差 |
取反 ~ |
\(\lnot x\) | 配合 & 清位 |
左移 << |
\(x \cdot 2^k\) | 造掩码 1 << k |
右移 >> |
\(\lfloor x / 2^k \rfloor\) | 逐位遍历 |
S2 bit_op.cpp 里那句总结值得抄下来：
与用于取数，或用于赋值，异或用于特定位取反。
单点位操作模板¶
(x >> k) & 1 # 先把第 k 位挪到最低位，再用 1 掩掉其余位，结果是 0 或 1
x | (1 << k) # 或运算「有 1 就是 1」，其余位与 0 相或保持不变
x & ~(1 << k) # ~(1<<k) 是「只有第 k 位为 0」的掩码，与之相与即清掉该位
x ^ (1 << k) # 异或 1 翻转、异或 0 不变，所以只有第 k 位被翻
x & (1 << k) # 判断第 k 位是否为 1（结果是 0 或 2^k，非零即真）
整体位操作模板¶
x & 1 # 判奇偶：最低位就是模 2 的余数
x >> 1 # 除以 2（向下取整；Python 里对负数也是向下取整）
x & (x - 1) # 消去最低位的 1：减 1 把该位变 0、其右侧全变 1，相与即抹掉它
x & (-x) # lowbit：只保留最低位的 1（推导见下一节）
x | (x + 1) # 把最低位的 0 置 1：加 1 的进位恰好停在那个 0 上
x & (x + 1) # 消去末尾连续的 1：加 1 后这些位全变 0，相与即抹掉
(1 << k) - 1 # 低 k 位全 1 的掩码：2^k 减 1 会向下借位，把 k 个 0 全借成 1
x & ((1 << k) - 1) # 取 x 的低 k 位，等价于 x mod 2^k（x 非负时）
一律加括号。 Python 的位运算优先级低于比较运算符：
x & 3 == 1实际是x & (3 == 1)=x & False=0。 这条坑在 03-运算符与位运算 已经强调过， 这里再说一次，因为它值得说两次。
46.2 lowbit 与 x & (x-1)¶
这两个是位运算里最重要的恒等式，务必理解为什么成立。
x & (-x)：lowbit¶
Python 的整数是无限位补码，\(-x = \lnot x + 1\)。取反把最低位 1 右边的 0 全变成 1， 加 1 之后进位一路传到那个位置停下——于是 \(x\) 与 \(-x\) 只在最低位的 1 上同时为 1。
x = 0b101100
# -x = ~x + 1：取反后最低位 1 右边的 0 全变 1，加 1 时进位一路传到那个位置停下，
# 于是 x 与 -x 在「最低位的 1」以上完全相反、以下全是 0，只有那一位同时为 1
x & (-x) # 0b100 = 4，最低位的 1
lowbit 是树状数组的核心，见 39-树状数组与线段树。
x & (x-1)：消去最低位的 1¶
\(x - 1\) 把最低位的 1 变成 0、其右边的 0 全变成 1，与原数相与后那一位就没了。
Brian Kernighan 算法数 1 的个数：
def popcount_bk(x):
c = 0
while x: # x 归零即说明所有的 1 都被消掉了
x &= x - 1 # 每次消掉最低位的那个 1，其余位不受影响
c += 1
return c # 循环次数恰好等于 1 的个数，与总位数无关
循环次数等于 1 的个数（而不是位数）。但在 Python 里它比 bin(x).count("1") 慢，
因为后者全在 C 层——见下一节。
判断 2 的幂：
46.3 popcount：3.9 与 3.10+ 的分水岭¶
| 写法 | 可用版本 | 相对速度 | 说明 |
|---|---|---|---|
bin(x).count("1") |
全部 | 1× | 建字符串 + C 层计数 |
x.bit_count() |
3.10+ | 约 3–5× 更快 | 直接数位，无中间对象 |
while x: x &= x-1 |
全部 | 慢 5–10× | 纯 Python 循环 |
本教程的目标环境是 Python 3.9，统一用
bin(x).count("1")。 若 OJ 的 Python 版本 \(\ge\) 3.10，换成x.bit_count()能明显提速。 想两边通吃可以写：但竞赛里不值得为此增加复杂度——先确认 OJ 版本，再一次性选定写法。
其它相关内置：
x.bit_length() # 二进制位数（不含符号位），0 的结果是 0
(13).bit_length() # 4，因为 13 = 0b1101
# n-1 的位数就是「凑齐 n 需要几位」：n 本身是 2 的幂时也不会多进一位
1 << (n - 1).bit_length() # >= n 的最小 2 的幂（n >= 1）
bit_length 是求 \(\lfloor\log_2 x\rfloor\) 的正确姿势（= x.bit_length() - 1），
比 math.log2 快且没有浮点误差，见 45-倍增。
46.4 Python 位运算的两个特殊之处¶
一、位运算不是 \(O(1)\)¶
C/C++ 里 x & y 是一条 CPU 指令。Python 的整数是任意精度的，位运算是 \(O(\text{位数})\)。
| 位数 \(d\) | x & y |
影响 |
|---|---|---|
| \(\le 64\) | 常数，很快 | 无感 |
| \(10^3\) | 约 30 个「肢」 | 仍可接受 |
| \(10^6\) | 3 万个肢 | 每次运算都是毫秒级 |
危险模式：循环里带左移。
# ❌ cur 每轮左移一位，n 轮后有 n 位；而位运算的代价正比于位数，总复杂度 O(n²/30)
cur = a[0]
for i in range(1, n):
cur = (cur & a[i]) << 1
# ✅ 加上提前退出
for i in range(1, n):
cur = (cur & a[i]) << 1
if cur == 0: # 0 与任何数相与仍是 0、左移仍是 0，后面恒为零
break # 位数不再膨胀，整体退回 O(n)
BISHI33 就是被这一条卡的题，完整分析见 22-高精度与大整数 §22.4。
C++ 里
uint64左移 64 次自然归零，Python 会老老实实一直算下去。 凡是循环里有<<，都要问一句：结果会不会无限膨胀？
二、大整数当位集合反而是优势¶
反过来看，Python 的大整数是一个免费的、任意长度的位集合，
而且它的 &、|、^、<< 全在 C 层按 30 位一组批量处理，
比用 list 或 set 模拟快几十倍。
mask = 0 # 第 i 位为 1 表示集合含元素 i；初始是空集
mask |= 1 << i # 加入元素 i：或运算只置位，不影响其他位
mask &= ~(1 << i) # 删除元素 i：与「除第 i 位外全 1」的掩码相与
if mask >> i & 1: ... # 判断是否含 i（>> 的优先级高于 &，但仍建议加括号）
bin(mask).count("1") # 集合大小 = 1 的个数
(mask1 & mask2) != 0 # 交集非空 = 存在某位两边都是 1
这个技巧在位运算优化 DP / 可行性判定里非常有用。 经典例子是 01 背包的可行性版本：
# 「能否凑出重量 w」的 O(nW/30) 解法：用一个大整数当 bitset
reachable = 1 # 第 j 位为 1 表示重量 j 可达；初始只有第 0 位是 1，即只有 0 可达
for w in weights:
# 左移 w 位 = 把每个可达重量 j 都变成 j+w；再或回去 = 「选或不选」两种情况取并集
reachable |= reachable << w # 一次左移就完成了整个 DP 的一轮转移
print((reachable >> W) & 1) # 取第 W 位：1 表示重量 W 可达
这一行 reachable |= reachable << w 抵得上一个 \(O(W)\) 的内层循环，
而且常数只有 \(1/30\)。见 101-背包问题。
46.5 异或的代数性质¶
| 性质 | 式子 |
|---|---|
| 自反 | \(x \oplus x = 0\) |
| 幺元 | \(x \oplus 0 = x\) |
| 交换律 / 结合律 | \(x\oplus y = y\oplus x\)，\((x\oplus y)\oplus z = x\oplus(y\oplus z)\) |
| 自逆 | \(x \oplus y \oplus y = x\)（异或的逆运算是它自己） |
| 不进位加法 | \(x + y = (x \oplus y) + 2(x \wedge y)\) |
由自反 + 交换结合，得到最常用的推论：
一组数全部异或起来，出现偶数次的会互相抵消。
四个直接应用：
| 题型 | 做法 |
|---|---|
| 一堆数里只有一个出现奇数次 | 全体异或 |
| 区间异或和 | 前缀异或，\(X_r \oplus X_{l-1}\)，见 42-前缀和与差分 |
| 交换两数不用临时变量 | a ^= b; b ^= a; a ^= b（Python 里直接 a, b = b, a 更好） |
| 最大异或对 | 01-Trie，见 73-Trie字典树 |
全体异或的惯用写法：
from functools import reduce
from operator import xor
reduce(xor, a, 0) # 0 是异或的幺元，作为初值可让空列表也返回 0；循环全在 C 层
尼姆博弈的 SG 值也是异或，见 50-博弈论。
46.6 子集枚举与状态压缩¶
枚举一个集合的所有子集¶
sub = mask # 从全集开始，按二进制值降序枚举
while True:
# 处理子集 sub
if sub == 0: # 空集也要处理，所以判断放在处理之后
break
# sub - 1 会把 sub 最低位的 1 变 0、其右侧全变 1；& mask 把借出去的位裁回 mask 内部，
# 相当于在「只由 mask 的 1 位构成的计数器」上减 1，因此不重不漏
sub = (sub - 1) & mask # 关键：减 1 后与原集合相与，跳到下一个子集
为什么 (sub - 1) & mask 能不重不漏地枚举所有子集：把 mask 里的 1 位看作
一个「压缩过的二进制计数器」，sub - 1 是这个计数器减 1，& mask 把借位溢出到
mask 外的部分清掉。于是它按降序枚举 \(2^{|mask|}\) 个子集，恰好一次。
总复杂度：对所有 \(2^n\) 个 mask 枚举子集，总数是 \(\sum_k \binom{n}{k} 2^k = 3^n\)。
这是状压 DP 里「枚举子集」类转移的标准复杂度。
| \(n\) | \(2^n\) | \(3^n\) | Python 现实性 |
|---|---|---|---|
| 15 | \(3\times10^4\) | \(1.4\times10^7\) | ⚠️ 勉强 |
| 18 | \(2.6\times10^5\) | \(3.9\times10^8\) | ❌ |
| 20 | \(10^6\) | \(3.5\times10^9\) | ❌ |
Python 的状压 DP 上限大约是 \(n \le 15\)–\(18\)（\(O(2^n \cdot n)\)）。 需要 \(3^n\) 的子集枚举时，\(n \le 13\) 才安全。
其它常用枚举¶
for mask in range(1 << n): # 枚举全集的 2^n 个子集，mask 的第 i 位表示元素 i
for i in range(n):
if mask >> i & 1: # 元素 i 在集合里
...
# 枚举 mask 里的每个 1（只跑 popcount 次，与总位数无关）
m = mask
while m:
low = m & (-m) # lowbit：孤立出最低位的那个 1
i = low.bit_length() - 1 # low 是 2^i，位数减 1 即位号 i
m ^= low # 异或自身即清零该位，进入下一个 1
...
# 枚举 mask 的补集的子集：full 是全集掩码 (1<<n)-1，异或即取补
comp = full ^ mask
状压 DP 的常见状态设计¶
| 状态含义 | 典型题 |
|---|---|
| 「哪些物品已被选」 | 旅行商 TSP、任务分配 |
| 「一行的填充情况」 | 棋盘覆盖、铺砖 |
| 「哪些位置已放置」 | \(n\) 皇后计数 |
完整讲解见 103-区间树形状压DP。
46.7 例题¶
BISHI30 二进制数 1（简单）¶
给非负整数 \(x \le 10^{18}\)，求它二进制表示中 1 的个数。 题面见 BISHI30 原题（牛客）。
import sys
x = int(sys.stdin.buffer.read().split()[0]) # 只有一个数，取第一个 token
print(bin(x).count("1")) # bin(0) 是 '0b0'，计数得 0，边界天然正确
bin(0)是'0b0'，count("1")得 0，边界天然正确，不用特判。'0b'前缀里没有字符'1'，所以不需要bin(x)[2:]切片。- \(10^{18} < 2^{60}\)，C/C++ 要用
unsigned long long，Python 无感。 - 3.10+ 可换成
x.bit_count()，快 3–5 倍；3.9 环境下就用上面这行。
题解见 solutions/BISHI30.py。
BISHI31 二进制不同位数（简单）¶
给 \(1 \le m, n \le 10^9\)，求两者二进制表示中对应位不同的位数。 题面见 BISHI31 原题（牛客）。
异或的定义就是「相同为 0、不同为 1」，所以答案 \(= \operatorname{popcount}(m \oplus n)\)：
import sys
m, n = map(int, sys.stdin.buffer.read().split()[:2])
# 异或的定义就是「相同为 0、不同为 1」，数一数结果里的 1 就是不同位数（汉明距离）
# 位数不等时短的一方高位按 0 参与运算，正好对应题面的「从最低位对齐」
print(bin(m ^ n).count("1"))
- 「从最低位对齐」意味着高位缺失的一方补 0——异或天然就是这个语义。 手动把两个二进制串补齐再逐位比较反而容易把前导零算进去（样例 2 的 7 与 10 正是在考这个）。
- 这题也叫汉明距离，是 01-Trie、最近邻搜索里的基本量。
题解见 solutions/BISHI31.py。
BISHI32 被打乱的异或和（简单）¶
原数组 \(b\) 长 \(n-1\)，令 \(x = b_1 \oplus \cdots \oplus b_{n-1}\)， 把 \(x\) 追加到末尾再打乱。给出打乱后的数组求 \(x\)，答案不唯一时输出任意一个。 题面见 BISHI32 原题（牛客）。
结论比看上去简单得多：任意一个元素都是合法答案。
设新数组为 \(a\)（长度 \(n\)），则
即全体异或恒为 0。于是对任意 \(i\)，去掉 \(a_i\) 后其余元素的异或是
对每一个 \(i\) 都成立，所以随便输出一个元素即可：
import sys
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0])
p = 1
out = []
for _ in range(t):
n = int(data[p])
p += 1
# 全体异或恒为 0，故去掉 a_i 后其余的异或就等于 a_i，任取一个元素都是合法答案
out.append(str(int(data[p]))) # 任取一个元素即为合法的 x
p += n # 跳过这一组剩余的 n 个数据 token
sys.stdout.write("\n".join(out) + "\n")
main()
千万别输出「全体异或」——那恒等于 0，只有恰好 \(x = 0\) 的组才对。 这是本题最经典的错法：算出了正确的性质（总异或为 0），却用错了方向。
另外这题是 special judge，输出与样例不同不代表写错，见 20-输入输出处理。
题解见 solutions/BISHI32.py。
46.8 本章速查¶
| 需求 | 写法 |
|---|---|
| 取第 \(k\) 位 | (x >> k) & 1 |
| 置 1 / 清 0 / 翻转第 \(k\) 位 | x \| (1<<k) / x & ~(1<<k) / x ^ (1<<k) |
| 低 \(k\) 位掩码 | (1 << k) - 1 |
| lowbit | x & (-x) |
| 消去最低位的 1 | x & (x - 1) |
| 判 2 的幂 | x > 0 and (x & (x-1)) == 0 |
| popcount（3.9） | bin(x).count("1") |
| popcount（3.10+） | x.bit_count()，快 3–5× |
| \(\lfloor\log_2 x\rfloor\) | x.bit_length() - 1 |
| 全体异或 | reduce(xor, a, 0) |
| 枚举子集 | sub = (sub - 1) & mask |
| 子集枚举总复杂度 | \(3^n\) |
| 位运算优先级 | 一律加括号 |
| Python 特有 | 结论 |
|---|---|
| 位运算复杂度 | \(O(\text{位数})\)，不是 \(O(1)\) |
循环里带 << |
检查是否无限膨胀，加提前退出 |
| 大整数当 bitset | 优势项，x \|= x << w 一行顶一个内层循环 |
| 状压 DP 上限 | \(n \le 15\)–\(18\)（\(2^n\)）；子集枚举 \(n \le 13\)（\(3^n\)） |
~x |
\(= -x-1\)，Python 无位宽概念 |