📑 本页目录(点开跳转)
07 · 位运算与模拟:把规则拆成小动作
⏱ 8 分钟 | 异或、不能用加减乘除的加法、顺时针打印矩阵
🎯 一句话
规则题不要靠“灵光一闪”:把一轮操作写清楚,再确认边界什么时候收缩。
上一章的矩阵路径会尝试不同方向,这一章的顺序已经给定。先问“我这一轮要保留或改变什么”,再写代码。学完后,试着独立用纸笔分一次组、传一串进位、收掉一圈格子。
🧩 题 1:数组中只出现一次的两个数字
所有成对数字异或后都抵消,只剩两个目标的异或。找其中一位为 1 的 bit,就能把两个目标分到不同组。
让成对编号消失,再用一位把两个目标分开
一批扫描记录里,大部分编号各出现两次,有两个不同的编号只出现一次。求和不能让相同编号自动消失。我们需要一种逐位运算,使相同的位相消、不同的位留下。
一个二进制位(bit)只能是 0 或 1。以四位为例,从右到左的位权是 1、2、4、8,0110 表示 4 + 2 = 6。异或(XOR,Python 写作 ^)比较对应位,相同给 0,不同给 1。按位与(AND,&)则只保留两边都是 1 的位。下表的规则独立应用到每一位。
| 两个输入位 | 异或 ^ | 按位与 & |
|---|---|---|
| 0 和 0 | 0 | 0 |
| 0 和 1 | 1 | 0 |
| 1 和 0 | 1 | 0 |
| 1 和 1 | 0 | 1 |
多个数做异或时,每一位只看 1 出现了奇数次还是偶数次,所以次序不影响结果。两个相同的数在每一位都贡献零个或两个 1,放在一起会抵消。用 [6, 1, 7, 6, 5, 5] 手算,两对 6 和 5 都消掉后,mixed = 0001 ^ 0111 = 0110,即十进制 6。
mixed 的两个 1 都能分组。代码用 mixed & -mixed 取最低的那个 1。以四位补码展示,0110 逐位取反再加一,得到 −6 的 1010。取反后的加一翻过末尾的 1,直到碰到第一个 0。于是原数最低的 1 在两边都为 1,更高的位仍然互反。按位与后只剩 0010。补码的字宽与符号解释见下面的可选深入。
| 分组条件 | 这一组的记录 | 组内异或 |
|---|---|---|
| 与掩码后非零 | 6、7、6 | 7 |
| 与掩码后为零 | 1、5、5 | 1 |
同一个编号的两次记录一定进同一组,所以在组内仍能抵消。两个目标在检查位上不同,各留在一组。接下来代码先扫出 mixed,再用掩码分流到 a 或 b,最后只给这两个答案排序。
def two_single_numbers(nums):
mixed = 0
for value in nums:
mixed ^= value
divider = mixed & -mixed
a = b = 0
for value in nums:
if value & divider:
a ^= value
else:
b ^= value
return tuple(sorted((a, b)))
assert two_single_numbers([2, 4, 3, 6, 3, 2, 5, 5]) == (4, 6)
mixed & -mixed 取最低位的 1;它保证两个目标在这一位不同。
输入和成本。代码要求两个不同的整数各出现一次,其余值各出现两次,并且输入能遍历两遍,例如列表。它本身不验证条件。只有成对元素时,mixed 为 0,无法分组,返回的 (0, 0) 不能当作找到两个目标。把一次定宽位运算视作常数,扫 n 个数两遍仍是 O(n) 时间,额外空间 O(1)。Python 的任意精度整数越宽,单次运算和临时整数也越大。
🧩 题 2:不用加减乘除做加法
不进位的和是异或;进位来自两位都为 1 的地方,左移一位。重复到没有进位。
把一轮加法拆成暂存和与待处理进位
个位上 1 + 1 的二进制结果是 10。这一列写 0,左边一列补 1。于是一次更新可以拆开做。令 a、b 是本轮要合起来的两个非负整数。a ^ b 把各列不考虑进位时的结果留下。a & b 找出产生进位的列,<< 1 把每个进位往左挪一位,送到位权翻倍的那一列。
每列只有三种和。两个 0 贡献 0,一边是 1 贡献这一列的位权,两个 1 贡献两倍位权。异或收下第一类和第二类的暂存结果,左移后的按位与收下第三类的进位。因此把两份新结果相加,仍等于本轮的 a + b。
| 本轮 a / b | 新 a,异或 | 新 b,与后左移 |
|---|---|---|
0111 / 0001 | 0110 | 0010 |
0110 / 0010 | 0100 | 0100 |
0100 / 0100 | 0000 | 1000 |
0000 / 1000 | 1000 | 0000 |
进位清空后,暂存值 1000 就是十进制 8。代码每轮用旧的 a 和 b 同时算出两个新值。若先把 a 改成异或结果,再用它计算进位,两个原本都是 1 的位已经丢了。
def add_without_plus(a, b):
while b:
a, b = a ^ b, (a & b) << 1
return a
assert add_without_plus(7, 5) == 12
原函数的输入约定为两个非负整数。按 Python 的无限符号位语义,(−1, 1) 会更新成 (−2, 2),再到 (−4, 4),进位持续向高位移动,循环不会终止。只有题目明确规定 32 位回绕时,才使用 32 位掩码。
若原输入较宽的一方有 w 位,非负数的和最多有 w+1 位。新进位里的每个 1 都来自旧进位中的某个 1,并且往左移了一位。因此只要还有进位,最低的 1 每轮至少左移一位。总共 O(w+1) 轮,每轮做常数次位运算,保留常数个整数。在 Python 大整数上,每次位运算还要处理对应的位宽,按每轮 O(w+1) 位工作量估计,最坏总位工作量为 O((w+1)²)。
可选深入:负数的位模式必须先说字宽
8 位里的 -5,不等于 bin(-5) 的打印格式
固定 w 位补码用模 2^w 的低 w 位编码整数;有符号解释范围是 −2^(w−1) 到 2^(w−1)−1。以 8 位为例,+5 是 00000101,逐位取反加一得到 -5 的 11111011。最高位为 1 时,把无符号值减 256 才得到有符号解释;这不是“符号位加绝对值”。
width = 8
mask = (1 << width) - 1
raw = (-5) & mask
assert format(raw, "08b") == "11111011"
def signed8(bits):
bits &= mask
return bits - (1 << width) if bits & (1 << (width - 1)) else bits
assert signed8(raw) == -5
assert signed8(127 + 1) == -128 # chosen 8-bit wraparound interpretation
for value in range(-128, 128):
assert signed8(value & mask) == value
assert (-5 >> 1) == -3 # Python: floor division by 2, sign extension semantics
print("-5 的8位模式:", format(raw, "08b"), "Python打印:", bin(-5))
Python int 没有固定 8/32 位宽,位运算按无限符号位的补码语义计算;bin(-5) 打印的是 -0b101,不能当成某个字长的内存转储。上文原加法例保留非负输入;若题目明确要求 32 位回绕,须在迭代时截断为低 32 位并按符号位还原结果,否则负数进位可能一直向高位传播。是否允许溢出、字宽多少,都必须先约定,不能从 Python 的无限精度偷换成 C++ 有符号溢出规则。
🧩 题 3:顺时针打印矩阵
不要真的“转方向”。每绕一圈,收缩上、右、下、左四条边;每走一条前都确认矩形还没有塌掉。
每走完一条边,就从剩余矩形里删掉它
想象要从一盘标签上按顺时针揭下贴纸。如果边界沿用揭之前的值,转弯时角上的贴纸会被取两遍。把四条边界记成从 0 开始的下标。top 和 bottom 是最上、最下的未读行,left 和 right 是最左、最右的未读列。两个端点都包含在剩余矩形里。
| 1 | 2 | 3 | 4 |
| 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 |
| 动作 | 新读到的值 | 读完后的边界 |
|---|---|---|
| 上边向右 | 1、2、3、4 | (1, 2, 0, 3) |
| 右边向下 | 8、12 | (1, 2, 0, 2) |
| 下边向左 | 11、10、9 | (1, 1, 0, 2) |
| 左边向上 | 5 | (1, 1, 1, 2) |
| 内圈只剩一行 | 6、7 | 上边移到 2,下边仍是 1,结束。 |
每段循环只读当前边,紧接着缩一条边,所以下一段不再包含刚读的角。只剩一行时,收掉上边后 top > bottom,右边的行范围为空,下边也跳过。只剩一列时,右边读完后 left > right,下边的列范围为空,左边也跳过。
def spiral_order(matrix):
if not matrix:
return []
top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
answer = []
while top <= bottom and left <= right:
for c in range(left, right + 1):
answer.append(matrix[top][c])
top += 1
for r in range(top, bottom + 1):
answer.append(matrix[r][right])
right -= 1
if top <= bottom:
for c in range(right, left - 1, -1):
answer.append(matrix[bottom][c])
bottom -= 1
if left <= right:
for r in range(bottom, top - 1, -1):
answer.append(matrix[r][left])
left += 1
return answer
assert spiral_order([[1, 2, 3], [4, 5, 6], [7, 8, 9]]) == [1, 2, 3, 6, 9, 8, 7, 4, 5]
输入和成本。输入是各行等长的二维列表。空矩阵或零列返回空列表;每行长度不同的输入超出本示例的约定。对非空的 R 行、C 列,四条边每次把访问过的格子移出剩余范围,每格恰好读一次,时间为 O(R × C)。返回列表也占 O(R × C),除它之外只用常数个边界和循环下标。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| NumPy 与向量化思维 08 · 整数 dtype 的真相 | ⭐ 当逐元素加法的结果仍用原定宽整数类型保存时,NumPy 数组可能静默回绕。链接中的 uint8 数组示例里,200 加 100 得到 44。某些标量运算会报警,转换或类型提升的结果要按各自规则判断。NumPy 类型提升文档 |
异或留下所有不同的位,所以还能用来数两串等长二进制标签有几处不同。比如 1010 ^ 1111 = 0101,两个 1 对应两处不同,这个数叫汉明距离(Hamming distance)。在图像匹配中,BRIEF 会把一个局部特征写成二进制描述,再用这个距离比较描述是否接近。BRIEF 作者团队说明
下一章解析字符串时,也可以逐步写下“当前读到哪、哪些内容已确认、何时停止”。例如读到首个不符合规则的字符,先处理停止条件,再决定是否继续更新结果。
本节回顾
模拟题的正确打开方式:先写一轮,再写“这一轮结束后哪条边/哪个状态改变”。
✅ 检查点
顺时针打印为什么在下边和左边前要再判断一次边界?
👀 看答案
只有一行或一列时,上边或右边已经把元素拿完了;不检查会重复加入。
如果 mixed = 0110,改用掩码 0100 也能分开两个目标吗?用 0001 呢?
👀 看答案
0100 可以。它挑的是 mixed 的另一处 1,两个目标在这一位也不同。0001 选中的那一位在 mixed 里为 0,两个目标那一位相同,仍会进同一组。
只走加法的第一轮。若 a = 0011、b = 0001,两个新值是什么?
👀 看答案
异或给 0010,按位与给 0001,左移后也是 0010。两个 2 留到下一轮合并。此时进位仍然非零,先别返回。
⚡ 走神救援
- 异或:相同抵消;用一个不同 bit 把两个目标分组。
- 二进制加法:异或是不进位和,
&左移是进位。 - 螺旋矩阵:每圈收四条边,收缩后立刻检查是否越界。