企业官网建设流程全解析

面试被问到“不用加号怎么计算两个整数之和”的时候，我第一次是完全懵的。后来在“优选算法-位运算”这个专题里认真啃了第35、36、37题，才真正把异或、与、左移这些东西串成了一条线。这三道题分别是两个整数之和、只出现一次的数字||、消失的两个数字，题目难度从易到难，但核心都落在位运算上。很多朋友刷位运算的时候，背了“异或可以消去出现偶数次的元素”就开始套题，一旦碰到负数、出现三次、缺失两个数就全乱套。这篇文章打算把三道题放在一起彻底讲清楚，从底层规则一直讲到手写代码，顺便把Python处理负数位运算的那个大坑也一并排掉。适合正在集中刷算法题、准备面试手撕代码，或者对位运算一直似懂非懂的读者。

1. 位运算基础：做这三道题前，先搞懂这几条规则

1.1 为什么这三道题值得放在一起刷

这三道题不是一个简单的难度递进，而是三个完全不同的位运算方向。

第35题“两个整数之和”逼你重新理解加法的本质——加法不是算术上的符号运算，而是“不进位加”和“进位”两步走的位级过程。第36题“只出现一次的数字||”则告诉你异或不是万能的，偶数次出现可以消掉，三次出现就需要计数和取模。第37题“消失的两个数字”又把异或结果当成线索，用二进制位把两个缺失数字拆到不同分组里。

三题连起来刷完，你会非常直观地感受到一件事：位运算在处理“每一位独立”“出现次数”“缺失元素”这类问题时，可以把很多看起来复杂的逻辑压缩到常数空间里。

1.2 高频运算符的语义，必须烂熟于心

位运算的核心操作其实就四个：异或、与、或、位移。先把语义按下不表，直接上结论表：

除了上面这些，还有两个几乎每道位运算题都用得到的衍生技巧：

• x & -x提取最低位的1，后面的第37题要靠它分组。
• x & (x-1)消掉最低位的1，虽然这三题没直接用到，但面试时经常作为引子。

理解位运算的关键不在死记结论，而在于想清楚每个运算符对“单个二进制位”做了什么。加法中的每一位都独立产生结果，进位是额外生成的，用电路语言描述这就是半加器。

1.3 唯一的隐藏大坑：Python的整数没有位数限制

这一节提前讲，因为后面35、36题都会遇到。

在Java和C++里，int是32位定长整数，超出部分直接截断，负数用补码表示。但Python的整数是变长的，当你在Python里写-1，它的补码看起来像是无限多个1向左延伸；当你写2**100，它也能准确地表示出来。

这个特性在做普通算法题时很爽，但做位运算题就是灾难。比如在Java里写一个循环加法，进位最终会因为溢出被丢弃，循环自然结束；同一套逻辑搬到Python里，进位会无限向左移动，循环根本停不下来。所以后面所有涉及32位语义的运算，我都会先做一步：

MASK = 0xFFFFFFFF x &= MASK

这相当于把Python变长整数强行裁剪成32位视角，然后再按int32的规则走。等算完了再根据符号位把结果还原成Python里的正常负数。这个话题在第2题、第3题都会反复出现。

2. 第35题：两个整数之和——异或做无进位加法，与运算找进位

2.1 题目本身在考什么

题目描述很简单：给定两个整数a和b，求它们的和，但禁止使用+和-运算符。

这个限制要表达的不是“你背过某个位运算模板就能过”，而是“你知不知道计算机底层是怎么做加法的”。在CPU里面，加法器就是不折不扣地用异或和与运算搭出来的。由异或负责本位的相加，由与运算负责生成进位，再通过移位把进位送到下一位。

2.2 核心观察：异或就是不带进位的加法

先做一个不太起眼但很关键的表：

看见没有？除了1+1的情况，其他所有情况下a^b和a+b的“本位”完全一致。1+1时异或得到0，丢掉的是那个进位。所以说，异或恰好完成的是“不考虑进位”的加法。

2.3 进位为什么是(a & b) << 1

那丢掉的进位去哪了？从上面的表也能看出，只有两个位都是1时才会产生进位。要找到这样的位置，用与运算刚刚好：a & b把所有“两个都为1”的位标了出来。进位是向左移动一位的，所以完整的进位公式就是：

carry = (a & b) << 1

我用7 + 13手动推一遍，帮助把过程看透：

注意第二轮的细节：异或结果变成0了，但进位是20，所以循环还得继续。最终当进位b变成0时，a就是答案。

每推一轮，进位都会向左移动一位。在32位int内，最多32轮后进位一定被移出可表示范围并截断为0，所以循环一定终止。

2.4 常规语言解法

在Java或C++中，代码非常短：

public int getSum(int a, int b) { while (b != 0) { int carry = (a & b) << 1; a = a ^ b; b = carry; } return a; }

这里有一个顺序陷阱：carry必须先算出来，再更新a。因为第二行a = a ^ b用的是旧的b，如果先改a，后面的进位和异或就全乱了。

2.5 Python版本：不要忘记32位掩码

Python版本如果不加任何处理，直接照抄上面循环，a、b稍微带点负数就会出问题。原因就是我第1.3节提到的：Python整数是无限长的，进位不会自动截断。

完整可用版本长这样：

def getSum(a: int, b: int) -> int: MASK = 0xFFFFFFFF MAX = 0x7FFFFFFF # 统一转成32位视角，负数变成补码对应的无符号整数 a &= MASK b &= MASK while b: carry = ((a & b) << 1) & MASK a = (a ^ b) & MASK b = carry # 如果结果小于等于int32最大值，说明是正数 if a <= MAX: return a # 否则是无符号视角下的负数，减2^32还原成真正的负数 return a - (1 << 32)

解释一下最后两行的还原逻辑。在32位视角下，0xFFFFFFFF表示-1，但按无符号整数读却是4294967295。这个数大于int32最大值，所以它对应的应该是一个负数。把它减去2^32，就得到-1，Python就能以正常负数返回给外面了。

用负数验证一下，比如算-1 + 1：

• -1 & MASK得到0xFFFFFFFF，即4294967295。
• 每轮异或、与、左移都在32位视角里进行。
• 循环结束后a等于0，直接返回0。

我自己第一次用Python刷这题时，没有加掩码，跑到某个负数用例就死循环了。这类问题不亲自踩一次，真的想不到。

2.6 这道题的常见追问

面试官看到你写完后，往往不会直接放你走，大概率会追加几个问题：

• 为什么不用递归？递归和循环本质相同，无非是把while换成函数自身调用，复杂度没有区别，还容易爆栈。
• 负数也能用这个规律吗？在补码表示下，加法器的逻辑对所有整数都一致，所以负数同样适用。
• 如果数字超过32位怎么办？题目默认int范围，如果扩展成大整数，就要把掩码扩大，比如用0xFFFFFFFFFFFFFFFF模拟64位。

3. 第36题：只出现一次的数字||——逐位统计与模3计数器

3.1 哈希表解法为什么不是这道题的终点

这道题描述是：给定一个整数数组，除了某一个元素只出现一次，其余每个元素都恰好出现三次，找出那个出现一次的元素。

最自然的做法是哈希表，统计每个数字出现的次数，出现一次的那个就是答案。哈希表很清晰，时间O(n)，空间也是O(n)。但题目通常明确要求“只用O(1)额外空间”，所以哈希表只能作为热身答案，真正的考点在于位运算。

从上一题的“两个数相加”，到这里变成“一堆数里找唯一出现一次的数”，很多人第一反应还是异或。但异或有个硬约束：只能消去出现偶数次的数字。出现三次，异或完根本消不掉。那怎么办？换个角度看每一位的出现次数。

3.2 逐位统计法：每一位单独数1的个数，对3取模

把数组里的所有数字想象成32个并列的位平面。对于第i位，把所有数字的这一位加起来，会得到一个整数值。一个出现三次的数字，它在第i位上如果是1，就会贡献3个1；如果是0，就贡献0个1。所以对所有“出现三次”的数字，第i位累计的1的个数永远是3的倍数。剩下那个只出现一次的数字，第i位如果是1，总数模3就会余1；如果是0，就余0。

换句话说，对每一位做一次“统计所有数字第i位为1的个数，再对3取模”，就能还原出目标数字每一位的取值。

代码写出来并不复杂：

def singleNumber(nums: list[int]) -> int: ans = 0 for i in range(32): cnt = 0 for x in nums: cnt += (x >> i) & 1 if cnt % 3: ans |= (1 << i) # 如果第31位为1，说明答案在32位视角里是负数 if ans >> 31: ans -= 1 << 32 return ans

时间复杂度是O(32n)，空间O(1)。这已经能满足绝大多数面试要求了。32次遍历听起来不少，但每一位上的运算很轻，实际跑起来完全没有性能压力。

这里要提醒一点：Python里负数右移是算术右移，高位补1，但在统计低位时(x >> i) & 1拿到的仍然是二进制从低到高的第i位本身，所以统计逻辑不受影响。整体思路是按32位补码模型去还原数字。

3.3 进阶：用两个变量实现模3状态机

逐位统计是“最笨但最稳”的解法。如果再往下走一层，能不能一次遍历同时处理32位？可以，这就是状态机解法。

把每一个二进制位看成一个计数器，这个计数器只需要记住三种状态：出现了0次、出现了1次、出现了2次。当一个数字的第i位再次为1时，计数器就加1；加到3次说明这一类数字出现了3次，模3清零。

要用一个变量表示三种状态，二进制上至少需要两个bit。这两个bit分别记为twos和ones，状态编码如下：

对每个输入数字x，考察它的每一位，状态转移规则是：

这个状态表翻译成语法的位运算，就两行：

ones = (ones ^ x) & ~twos twos = (twos ^ x) & ~ones

但注意，这两行有先后依赖问题。如果先把ones更新了，那么第二行里的~ones已经是新值，不是旧状态里的ones。用Python的并行赋值可以避免这个麻烦：

def singleNumber(nums: list[int]) -> int: ones = twos = 0 for x in nums: ones, twos = (ones ^ x) & ~twos, (twos ^ x) & ~ones return ones

返回值是ones，因为状态“出现1次”最终停留在那个只出现一次的数字上。这个写法在面试中很有竞争力，时间复杂度O(n)，空间O(1)，而且只需要一遍遍历。

如果好奇为什么代码能生效，可以对照状态表慢慢推一组小数据。我第一次推的时候，拿手边的数字2, 2, 2, 5一行一行算，算完就清楚多了。建议你也这样试一次，比背代码有用得多。

3.4 扩展：如果每个数字出现4次、5次怎么办

逐位统计法几乎不需要改，把cnt % 3改成cnt % k就行。状态机则需要更多的状态变量：出现k次，理论上需要ceil(log2(k))个bit来记录状态。比如出现4次，状态空间至少是4个：0次、1次、2次、3次，对应两位二进制。实现时状态转移会更绕，还得手动剔除非法组合。

所以从工程角度，逐位统计是更通用、更不容易写错的方法。状态机则是面试中展示功底的加分项，二者各有所长。面试时先讲逐位统计，再补一句“如果要求线性时间并且只用几个变量，还可以用模3状态机”，印象分会好很多。

4. 第37题：消失的两个数字——异或结果里的分组信号

4.1 题目描述与两个主流方向

这道题输入是长度为N-2的数组，包含1到N中除了两个数字之外的所有整数，要求用O(N)时间、O(1)空间找到缺失的那两个数字。

看到“缺失两个”，一般有两个解题方向：一是利用异或的性质，把缺失的两个数字从混合异或结果中分离出来；二是利用和、平方和构造方程组求解。前者是位运算专题的延续，后者是纯数学。

个人更推荐异或分组法，因为它没有溢出、没有浮点误差，概念上还和第35、36题的位运算一脉相承。

4.2 第一步：把整个数组和1到N全部异或，得到缺失对异或值

核心技巧：把数组中的所有数字异或一遍，再把1到N所有数字异或一遍，两个结果再异或起来。

为什么这样做？因为除缺失数字以外，每个数字都会在“数组”里出现一次，又在“1到N的完整集合”里出现一次，总共出现两次，而x ^ x = 0，所以它们全部抵消。最后剩下的就是：

xor_all = missing1 ^ missing2

举个例子。假设N=6，数组是[1, 2, 3, 6]，缺失的是4和5。

手动计算一下：

1^2^3^6 ^ 1^2^3^4^5^6

成对的1、2、3、6全部抵消，剩下的就是4^5，等于0b001，也就是十进制的1。

4.3 第二步：用最低位的1把集合分成两组

现在手里只有missing1 ^ missing2，怎么把它们拆开？

missing1和missing2一旦不同，它们的二进制表示中必然至少有某一位不同。这一位上一个是1，另一个是0。如果按这一位把数字分成两组——低bits为1的一组、为0的一组——那么missing1和missing2必然落在不同的组里。

先找到这个“分水岭”。xor_all中为1的位，恰恰就是两位缺失数字不同的位置。取最低的那个1就行：

lowbit = xor_all & -xor_all

x & -x提取最低位1，这是位运算里的经典操作。

然后分别把数组和完整的1到N数字按lowbit分组，各组内部异或：

def missingTwo(nums: list[int], n: int) -> list[int]: xor_all = 0 for x in nums: xor_all ^= x for i in range(1, n + 1): xor_all ^= i lowbit = xor_all & -xor_all a = b = 0 for x in nums: if x & lowbit: a ^= x else: b ^= x for i in range(1, n + 1): if i & lowbit: a ^= i else: b ^= i return [a, b]

这里最容易犯的错误是：只遍历原数组，不遍历1到N。为什么必须两个集合都遍历？因为分组的目标是让“同一组内除了缺失数字以外，其他数字都出现正好两次”。原数组里的每个数只出现一次，完整集合里的每个数又出现一次，合起来才构成“两次”。只拿一边的数据，组内异或结果就是乱的。

继续用上面的例子验证。xor_all = 1，最低位1对应的lowbit = 1。

按第0位分组：

• 组1（第0位为1）：nums中的1、3，加上完整集合中的1、3、5。异或结果为5。
• 组0（第0位为0）：nums中的2、6，加上完整集合中的2、4、6。异或结果为4。

完美得到缺失数字4和5。

4.4 数学法：和与平方和解方程

异或分组不是唯一的解法。数学法也很有意思：设缺失的两个数为x、y，记：

S = (1 + 2 + ... + n) - sum(nums) = x + y T = (1^2 + 2^2 + ... + n^2) - sum(x^2 for x in nums) = x^2 + y^2

知道x+y和x²+y²，就能求出xy：

xy = (S^2 - T) / 2

于是x、y是一元二次方程t² - S·t + xy = 0的两个根：

x = (S - sqrt(S^2 - 4xy)) / 2 y = S - x

这个解法思路很直观，但有两个需要注意的地方：

• 求和、平方和可能非常大，C++里必须用long long，再极端一点还可能溢出。
• 涉及开根号，如果语言里是浮点sqrt，大数场景下可能有精度问题。Python里可以用math.isqrt取整再验证平方关系。

相比之下，异或分组法没有溢出也没有浮点误差。所以实战中我更推荐异或版本。

两种方法可以整理成一张对比表，方便面试时快速选择：

如果面试官是奔着“位运算”这个话题来的，建议优先讲异或分组法；如果对方更看重通用性，再补充一句“其实数学求和也是一种思路”，两种解法都会能显著加印象分。

5. 三题串起来的复习：从消元、计数到分组

5.1 三条递进线，一条比一条深

这三道题如果单独刷，每一道都只是零散的知识点；放在一起看，是一条很清晰的递进链路。

第35题让你理解“异或等于无进位加法，与+左移等于进位”。这是位运算最底层的一种组合应用。第36题把视角拔高到“每一位的计数”：出现偶数次可以用异或消，出现奇数次时把每一位上的1累计起来取模。到了第37题，异或的结果不再只是“消元”工具，而是“线索”——两个缺失数字异或后的每一个1位，都给我们提供了分组的依据。

一个知识点从“认识”到“应用”再到“通过线索反推原值”，这三道题刚好覆盖了这三个层次。

5.2 通用思考框架

根据这三道题，我总结出一个做位运算题的思考顺序：

1. 先看问题里的每个个体能不能被拆成独立的二进制位。能的话，位运算大概率是突破口。
2. 再看出现次数与目标的关系：出现偶数次优先想异或，出现奇数次优先想逐位计数+取模，缺失多个数优先想异或+分组。
3. 最后检查语言和平台差异。用Python做题时，凡是涉及32位、负数的位运算，都要先想清楚要不要加掩码。

5.3 易错点复盘

把我自己走过的弯路汇总成一张表，刷题时对照自查：

5.4 一点个人体会

位运算题是最不适合靠背模板的一类题。这样说可能有点绝对，但我后来复盘发现，真正把题做透的人，基本都经历过一个“拿着笔在纸上一条一条推二进制过程”的阶段。我建议别急着提交代码，先挑个小例子，在纸上写出来每一步a和b的值、状态机的状态变化、分组后各个组的异或结果。这个“手动模拟”的过程，比看十篇题解都有用。

我自己最开始刷第36题的状态机时，光one、two的赋值顺序就错了好几遍。后来把每个输入数字的每一位都画成状态转移表，才彻底明白~twos和~ones到底在清除什么。那次以后，再遇到“出现k次找唯一一次”的变形题，我甚至能直接推出新的状态方程。位运算的乐趣也恰恰在这里：表象千变万化，底层就那么几条规则。把规则吃到骨头里，万变不离其宗。

这三道题做完，位运算这个专题里最典型的“消元、计数、分组”三种模型基本就都覆盖了。接下来如果想继续深化，可以再去找找涉及“前缀异或”“离线查询+异或”的题目，思维上会更加游刃有余。