📑 本页目录（点开跳转）
07 · 位运算与模拟：把规则拆成小动作
⏱ 8 分钟 ｜ 异或、不能用加减乘除的加法、顺时针打印矩阵
🎯 一句话
规则题不要靠“灵光一闪”：把一轮操作写清楚，再确认边界什么时候收缩。
🧩 题 1：数组中只出现一次的两个数字
所有成对数字异或后都抵消，只剩两个目标的异或。找其中一位为 1 的 bit，就能把两个目标分到不同组。
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；它保证两个目标在这一位不同。
🧩 题 2：不用加减乘除做加法
不进位的和是异或；进位来自两位都为 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 的负数是无限位语义，面试若要求处理负数，要先约定 32 位掩码。
🧩 题 3：顺时针打印矩阵
不要真的“转方向”。每绕一圈，收缩上、右、下、左四条边；每走一条前都确认矩形还没有塌掉。
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]
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| NumPy 与向量化思维 08 · 整数 dtype 的真相 | ⭐ 题 2 那句「Python 的负数是无限位语义，要先约定 32 位掩码」的反面：一旦进了 NumPy，整数就是定宽的，越界不报错、直接回绕，而且没有任何信号 |
🛑 可以停在这里
模拟题的正确打开方式：先写一轮，再写“这一轮结束后哪条边/哪个状态改变”。
✅ 检查点
顺时针打印为什么在下边和左边前要再判断一次边界？
👀 看答案
只有一行或一列时，上边或右边已经把元素拿完了；不检查会重复加入。
⚡ 走神救援
- 异或：相同抵消；用一个不同 bit 把两个目标分组。
- 二进制加法：异或是不进位和，
&左移是进位。 - 螺旋矩阵：每圈收四条边，收缩后立刻检查是否越界。