企业官网建设流程全解析

给你一个数组，除一个数只出现一次外，其余每个数都出现两次，把它找出来。要求线性时间、常数空间。

不准用哈希表（空间不满足）、不准排序后扫描（时间不满足）、更不准2×sum(set) − sum(nums)（溢出且空间超标）。

正解只有一行：

returnfunctools.reduce(lambdaa,b:a^b,nums)

第一次见这行代码的人几乎都会愣一下——为什么“成对出现的数”会在异或里自己消失？

因为它精确对应了异或最本质的三条性质。

这三条性质撑起了整个位运算世界的半壁江山，而很多人只记住了“异或是二进制的无进位加法”，却没意识到它同时是一个完备的代数结构。

今天把这三条讲透，你会顺带理解二进制Trie为什么能用异或做贪心、lowbit到底在取什么。

📦 题目速览（30秒读懂）

题目1：只出现一次的数字（LC.136）

非空数组，除某个元素只出现一次外，其余均出现两次。找出那个只出现一次的元素。

示例：[2,2,1]→1；[4,1,2,1,2]→4
要求：线性时间 + 常数空间。

题目2：只出现一次的数字III（LC.260，延伸）

恰好有两个元素只出现一次，其余均出现两次。找出这两个元素。

示例：[1,2,1,3,2,5]→[3,5]
示例：[-1,0]→[-1,0]

🧠 核心思路：异或的三条性质

异或（XOR，记作^）是“两位不同则为1，相同则为0”。

真正让它在算法里大放异彩的，是它的代数性质：

第三条是最容易被低估的。它意味着“一堆数异或起来”这个操作与输入顺序无关，只与“每个数出现了几次”有关。于是：

nums = [4, 1, 2, 1, 2] 全体异或 = 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) ← 交换结合律，把成对的重排到一起 = 4 ^ 0 ^ 0 ← 自反性 = 4 ← 恒等性

一句话核心：异或只关心“出现次数的奇偶”——出现偶数次的全部归零，出现奇数次的留下。
这就是为什么它是天然的“奇偶计数器”，而且成本只有O(1)空间。

⚠️一个常见误解：a ^ a = 0只对偶数次成立。
若其余元素出现三次（LC.137），异或就失效了——那时必须换成“逐位统计mod3”或“有限状态机”。记住这条边界，比记住解法更重要。

LC.260：异或 + 分组

现在有两个“单身”数字x、y。全体异或得到的是s = x ^ y——两个数被混在了一起，怎么拆开？

关键观察：因为x ≠ y，所以s ≠ 0，s的二进制里至少有一位是1。而s的第k位为1，意味着x和y在第k位上不同。

于是我们拿到一个天然的分类标准：按第k位是否为1，把整个数组分成两组。

• x和y必然分在不同的两组
• 成对出现的数字，两个副本第k位相同，必然落在同一组

于是每组内部都退化成了LC.136——各自异或即得答案。

取哪一位？取s中最低的那个1最方便：

lowbit = s & (-s)

这行代码在树状数组时已经出现过。这里给它一个更普适的解读：n & (-n)取出n的二进制中最低位的那个1所对应的权重，它是位运算工具箱里的标准件之一。

🖼️ 图解算法（手把手走一遍）

以nums = [1, 2, 1, 3, 2, 5]为例（答案[3, 5]）。

第一步：全体异或，逐元素累计

最终s = 6 = 110₂，正是3 ^ 5 = 6✓。注意中间值忽大忽小——异或不是累加，是逐个抵消。

第二步：取lowbit分组

s = 6 = 110₂ lowbit = s & (-s) = 110 & 010 = 010₂ = 2

lowbit = 2说明我们按第1位是否为1来分组：

第三步：两组各自异或

A组（第1位为1）：2 ^ 3 ^ 2 = 3 ← 两个2抵消，留下3 B组（第1位为0）：1 ^ 1 ^ 5 = 5 ← 两个1抵消，留下5

答案[3, 5]✓

为什么分组后“成对的数不会散开”？
因为两个副本是同一个数，第k位必然相同，所以必然同组。
这是整个算法成立的关键，也是面试时最该讲清楚的一句。

💻 代码实现（Python + Java）

Python版

classSolution:# ---------- LC.136 只出现一次的数字 ----------defsingleNumber(self,nums:list[int])->int:ans=0forxinnums:ans^=x# 成对的自我抵消，单身的留下returnans# ---------- LC.260 只出现一次的数字III ----------defsingleNumberIII(self,nums:list[int])->list[int]:s=0forxinnums:s^=x# s = x ^ y，且s != 0mask=s&(-s)# lowbit：取最低位的1作为分组依据a=b=0forxinnums:ifx&mask:# 该位为1的一组a^=xelse:# 该位为0的一组b^=xreturn[a,b]

Java版

classSolution{publicintsingleNumber(int[]nums){intans=0;for(intx:nums)ans^=x;returnans;}publicint[]singleNumberIII(int[]nums){ints=0;for(intx:nums)s^=x;// s = x ^ yintmask=s&(-s);// lowbitinta=0,b=0;for(intx:nums){if((x&mask)!=0)a^=x;elseb^=x;}returnnewint[]{a,b};}}

⚠️防坑提醒（必看）：

• s & (-s)只在s ≠ 0时有意义。题目保证恰有两个单身数字，所以s ≠ 0成立。
• 分组判定用x & mask（位与结果非零），不是x & mask == mask。
• Python整数是无限位补码语义，-5 & 5一样得到lowbit，无需额外处理。

⏱️ 复杂度分析（面试必问）

空间是这个系列里最“干净”的O(1)——只有一个整数变量在滚动。
这也是为什么面试官爱考它：它逼你放弃“记下来”的直觉，改用“抵消掉”的直觉。

🚀 举一反三：5道高频变体题

💬 面试追问模拟（提前准备，惊艳全场）

Q1：为什么a ^ a = 0？

从定义出发：异或是“两位不同为1”。a与自己做异或，第k位上两个比特必然相同，所以结果每一位都是0。
这是逐位成立的，与进位无关——这正是异或比加法好用的根本原因：没有进位，位与位之间彻底解耦。

Q2：不用临时变量交换两个数（a ^= b; b ^= a; a ^= b）可靠吗？

原理成立，但工程上不推荐：
① 若a和b是同一个变量（同一地址），三步之后会清零；
② 可读性差，编译器本就会做寄存器优化；
③ 对浮点数、对象完全不适用。面试里说“我知道原理但不会这么写”是加分项。

Q3：LC.260的分组位换成任意为1的位行不行？

行。只要取s中任意一个为1 的位即可完成分组，lowbit只是最容易写的一种。
若要取最高位的1，可以用1 << (s.bit_length() - 1)，效果完全相同。

Q4：出现三次的情况怎么做（LC.137）？

异或只能区分奇偶，三次需要mod3。
两种做法：
①逐位统计——对每一位统计1的个数，对3取模，O(32n)；
②有限状态机——用两个变量ones/twos表示“出现1次的位”和“出现2次的位”，一遍扫描O(n)、O(1)空间，是最优解。

🧩 实战小技巧（刷题党必备）

• 口诀：自反抵消，恒等保留，交换结合随意重排；两个单身先混后拆，lowbit分组。
• 模板：全体异或 → 得s；若只有一个单身，s即答案；若有两个，用s & (-s)分组再异或。
• 防坑：a^a=0只对偶数次成立；s & (-s)必须先保证s ≠ 0。

📈 实际应用场景（不止是刷题）

• 校验与纠错：RAID奇偶校验、网络传输校验和
• 加密：一次性密码本（OTP），明文 ^ 密钥 ^ 密钥 = 明文
• 差异检测：两份配置/文件按块异或，非零处即差异
• 状态压缩：权限位、开关集合用位掩码，异或用来“翻转”某一位

🎁 今日思考题（评论区见）

LC.137（其余元素出现三次）用“逐位统计mod3”是O(32n)，用有限状态机是O(n)。
如果元素出现k次（k为任意整数），逐位统计mod k的复杂度会变成多少？它和有限状态机相比哪个更通用？