🏠 总目录📚 本教程 07 · 位运算与模拟:把规则拆成小动作 ← →
📑 本页目录(点开跳转)

07 · 位运算与模拟:把规则拆成小动作

⏱ 8 分钟 | 异或、不能用加减乘除的加法、顺时针打印矩阵

🎯 一句话

规则题不要靠“灵光一闪”:把一轮操作写清楚,再确认边界什么时候收缩。

上一章的矩阵路径会尝试不同方向,这一章的顺序已经给定。先问“我这一轮要保留或改变什么”,再写代码。学完后,试着独立用纸笔分一次组、传一串进位、收掉一圈格子。

🧩 题 1:数组中只出现一次的两个数字

所有成对数字异或后都抵消,只剩两个目标的异或。找其中一位为 1 的 bit,就能把两个目标分到不同组。

让成对编号消失,再用一位把两个目标分开

一批扫描记录里,大部分编号各出现两次,有两个不同的编号只出现一次。求和不能让相同编号自动消失。我们需要一种逐位运算,使相同的位相消、不同的位留下。

一个二进制位(bit)只能是 0 或 1。以四位为例,从右到左的位权是 1、2、4、8,0110 表示 4 + 2 = 6。异或(XOR,Python 写作 ^)比较对应位,相同给 0,不同给 1。按位与(AND,&)则只保留两边都是 1 的位。下表的规则独立应用到每一位。

一对二进制位的两种运算
两个输入位异或 ^按位与 &
0 和 000
0 和 110
1 和 010
1 和 101

多个数做异或时,每一位只看 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。补码的字宽与符号解释见下面的可选深入。

用 0010 当掩码,只看位权为 2 的一位
分组条件这一组的记录组内异或
与掩码后非零6、7、67
与掩码后为零1、5、51

同一个编号的两次记录一定进同一组,所以在组内仍能抵消。两个目标在检查位上不同,各留在一组。接下来代码先扫出 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。

手算 7 加 1,每行两份新值都会成为下一轮输入
本轮 a / b新 a,异或新 b,与后左移
0111 / 000101100010
0110 / 001001000100
0100 / 010000001000
0000 / 100010000000

进位清空后,暂存值 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++ 有符号溢出规则。

依据:Python 3.14 整数位运算。

🧩 题 3:顺时针打印矩阵

不要真的“转方向”。每绕一圈,收缩上、右、下、左四条边;每走一条前都确认矩形还没有塌掉。

每走完一条边,就从剩余矩形里删掉它

想象要从一盘标签上按顺时针揭下贴纸。如果边界沿用揭之前的值,转弯时角上的贴纸会被取两遍。把四条边界记成从 0 开始的下标。top 和 bottom 是最上、最下的未读行,left 和 right 是最左、最右的未读列。两个端点都包含在剩余矩形里。

原创建例,3 行 4 列,每格用不同的值标记
1234
5678
9101112
把「上、下、左、右」四个下标写成一组,起点为 (0, 2, 0, 3)
动作新读到的值读完后的边界
上边向右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 留到下一轮合并。此时进位仍然非零,先别返回。


⚡ 走神救援

继续: 08 · 字符串与输入:脏输入也要有边界

打卡记录保存在你的浏览器里,首页能看到总进度