位运算与位掩码状态 · HTML
数学 / 逻辑形态
XOR 满足 x^x=0、x^0=x 且交换结合；AND/OR 控制位集合，(x>>b)&1 读取第 b 位。
识别信号
- 成对元素要消去
- 关心奇偶出现次数
- 汉明距离或逐位贡献
- 缺失或唯一元素
- 状态可拆成固定宽度独立位
容易误判的相似信号
| Signal | Why it is different |
|---|
| 需要频次大于奇偶的信息 | 单次 XOR 只保留奇偶；完整频次需哈希或按模位计数。 |
| Python 负数固定宽度假设 | Python 整数无限符号扩展，补码题需显式掩码。 |
核心不变量
聚合 XOR 等于所有出现次数为奇数的值之 XOR；逐位计数可在目标模数下独立恢复位。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | XOR 累积器或长度 W 的位计数数组，以及显式全位掩码。 |
| Transition | 读入 x 时做 acc^=x，或对每一位累加 (x>>b)&1。 |
| Frontier / order | 已扫描元素被压缩为位摘要；未扫描元素不会影响已定义的交换结合结果。 |
Python 骨架
def single_among_pairs(values):
ans = 0
for x in values:
ans ^= x
return ans
def hamming_distance(a, b):
return (a ^ b).bit_count()
def unsigned_low_bits(x, width):
return x & ((1 << width) - 1)
正确性思路
- 交换结合律允许任意重排 XOR。
- 每对相同值自反消成 0。
- 0 不改变剩余唯一值，因此最终即答案。
- a^b 的 1 位恰是两数不同位，bit_count 给汉明距离。
复杂度
| Time | Space | Parameters |
|---|
| XOR 聚合 O(n)，逐位法 O(nW) | O(1) 或 O(W) | n 为元素数，W 为使用的位宽 |
边界条件
- 空输入的 XOR 为 0 但未必有语义
- 负数需指定宽度
- 位移优先级应加括号
- 目标出现次数规则必须匹配模数
- 语言溢出与符号位差异
错误模式
| Pattern | Why it fails / fix |
|---|
| 把 XOR 当加法 | XOR 不保留进位和数值大小。 |
| 无证明地套唯一数模板 | 出现次数模式不同会留下多个值混合。 |
| 忽略符号扩展 | 负数右移与取反必须限制位宽。 |
选择与排除规则
- 其余都成对、一个唯一：XOR。
- 每位贡献独立：逐位计数。
- 需要完整频次：哈希表。
- 负数补码输出：最后用 mask 与符号位转换。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | XOR 结果为 9。 |
| Scenario | 序列 [12,5,12,9,5]。 |
| Walkthrough | 两个 12 与两个 5 分别消成 0，只留下 9。 |
Recall prompts
我的补充