预备知识基础运算与真值表假设有两个二进制位a和b运算符名称符号规则真值表与AND同为 1 才为 1000, 010, 100, 111或OR|有一个 1 就为 10|00, 0|11, 1|01, 1|11异或XOR^不同为 1相同为 00^00, 0^11, 1^01, 1^10取反NOT~0 变 11 变 0~0 1, ~1 0左移Left Shift高位丢弃低位补 00011 1 0110(相当于乘 2)右移Right Shift低位丢弃高位补符号位0110 1 0011(相当于除 2)注意C 中对于有符号数是算术右移补符号位对于无符号数是逻辑右移补 0。左移时建议使用无符号数以避免未定义行为。核心心法位运算题目表面上是在考二进制的操作实际上是在考降维打击的能力。普通的算法是在“数值”层面操作比如用哈希表记录数字而位运算是在“比特Bit”层面操作。它利用计算机最底层的特性实现了极致的时间/空间复杂度通常能实现 O(N) 时间O(1) 空间。巧妙的数学规律利用异或的抵消律、按位与的进位规律等。题目一判断字符是否唯一class Solution { public: bool isUnique(string astr) { // 1. 鸽巢原理Pigeonhole Principle优化 if(astr.size() 26) return false; // 2. 初始化位图 int bitMap 0; // 3. 遍历字符串 for(auto ch : astr) { // 计算字符对应的偏移量 (a - 0, b - 1, ..., z - 25) int i ch - a; // 4. 检查该位是否已经被标记为 1 if(((bitMap i) 1) 1) return false; // 5. 将该位标记为 1 bitMap | 1 i; } return true; } };关键步骤详细说明鸽巢原理优化 (if(astr.size() 26) return false;)因为题目规定字符串只包含 26 个小写英文字母。如果字符串长度超过 26根据鸽巢原理必然至少有一个字母重复。这一步可以直接拦截大量无效输入提高效率。位图 (int bitMap 0;)一个int类型在大多数现代计算机中占 32 位。题目只需要用到 26 位对应a到z。初始时这 32 位全是0。我们可以把它想象成一个长度为 26 的布尔数组但这比布尔数组更节省空间。从右往左数第 0 位代表a第 1 位代表b以此类推第 25 位代表z。计算索引 (int i ch - a;)利用 ASCII 码将字符映射为 0 到 25 的整数。检查是否出现过 (if(((bitMap i) 1) 1))bitMap i将位图向右移动i位把目标位移动到最低位。 1与1进行按位与操作。如果最低位是1结果为1如果是0结果为0。如果结果为1说明之前已经遇到过这个字符直接返回false。标记字符 (bitMap | 1 i;)1 i生成一个只有第i位为1其余全为0的数。bitMap | ...按位或赋值。这会将bitMap的第i位设置为1表示该字符已经出现过同时不影响其他位。题目二丢失的数字class Solution { public: int missingNumber(vectorint nums) { int ret 0; // 1. 将数组中的所有元素异或起来 for(auto x : nums) ret ^ x; // 2. 将 [0, n] 范围内的所有整数异或起来 // 注意nums.size() 就是 n所以循环条件是 i n for(int i 0; i nums.size(); i) ret ^ i; return ret; } };这段代码实际上做了一件事把数组里的所有数和[0, n]里的所有数全部混在一起进行异或。根据异或的三个核心性质归零律A ^ A 0相同的数异或抵消为 0恒等律A ^ 0 A任何数与 0 异或还是它自己交换律和结合律A ^ B ^ C C ^ A ^ B异或的顺序不影响结果我们可以把这两次循环合并起来看作一个大的异或运算ret (数组中的所有数) ^ (0 ^ 1 ^ 2 ^ ... ^ n)因为数组中有n个数它们分别是[0, n]中除去了那个缺失数字之外的数。所以除了那个缺失的数字之外其他所有的数字都出现了两次一次在数组里一次在[0, n]的完整序列里。根据归零律所有出现两次的数字都会变成0(0 ^ 0) ^ (1 ^ 1) ^ ... ^ (缺失的数字) ^ ... ^ (n ^ n) 0 ^ 0 ^ ... ^ 缺失的数字 ^ ... ^ 0最后根据恒等律所有的0和那个只出现一次的“缺失数字”异或结果就是那个缺失的数字本身0 ^ 0 ^ ... ^ 缺失的数字 缺失的数字模拟运行以示例 1 为例输入nums [3, 0, 1]此时n 3完整范围是[0, 1, 2, 3]。第一个循环异或数组元素ret 0 ^ 3 ^ 0 ^ 1第二个循环异或完整范围 0~3ret (0 ^ 3 ^ 0 ^ 1) ^ (0 ^ 1 ^ 2 ^ 3)利用交换律重新排列ret (0 ^ 0) ^ (1 ^ 1) ^ (3 ^ 3) ^ 2利用归零律消除成对的数字ret 0 ^ 0 ^ 0 ^ 2利用恒等律得出结果ret 2结果2正是缺失的数字题目三两整数之和class Solution { public: int getSum(int a, int b) { while (b ! 0) // 只要还有进位就继续循环 { int x a ^ b; // 步骤1计算无进位相加的结果暂存到 x // 步骤2计算进位 // 注意这里的 (unsigned int) 强制类型转换非常关键 unsigned int carry (unsigned int)(a b) 1; a x; // 将无进位结果赋值给 a准备下一轮 b carry; // 将进位赋值给 b准备下一轮 } return a; // 当进位 b 为 0 时a 就是最终结果 } };加法在二进制层面可以拆解为两个步骤无进位相加先不管进位把两个数的每一位直接相加。计算进位算出哪些位产生了进位并将进位加到正确的位置上。循环将“无进位的结果”和“进位”作为新的两个数重复上述过程直到没有进位为止。为什么用异或^和按位与异或^模拟“无进位加法”回顾异或的规则0^00,1^10,0^11,1^01。这和不考虑进位的二进制加法结果完全一致。例如1 1 10二进制如果不考虑进位本位应该是0正好是1 ^ 1 0。按位与模拟“进位”什么时候会产生进位只有当两个数的某一位同时为 1时1 1 1才会向高位进 1。所以a b找出了所有需要进位的位。但进位是加到高一位的所以需要左移 1 位 1。模拟一个产生进位的例子输入a 3(二进制0011)b 1(二进制0001)第一轮循环x a ^ b0011 ^ 00010010(即 2)carry (0011 0001) 10001 10010(即 2产生了进位)a 2b 2第二轮循环(b 2 ! 0)x a ^ b0010 ^ 00100000(即 0)carry (0010 0010) 10010 10100(即 4)a 0b 4第三轮循环(b 4 ! 0)x a ^ b0000 ^ 01000100(即 4)carry (0000 0100) 10000 10a 4b 0第四轮循环判断b 0循环结束。返回a即4。 (3 1 4正确)题目四只出现一次的数字IIclass Solution { public: int singleNumber(vectorint nums) { int ret 0; // 1. 遍历整数的 32 个二进制位 (从第 0 位到第 31 位) for(int i 0; i 32; i) { int sum 0; // 2. 遍历数组中的每一个数字 for(int x : nums) { // 3. 提取数字 x 的第 i 位并累加到 sum 中 if(((x i) 1) 1) sum; } // 4. 对统计结果取模 3 sum % 3; // 5. 如果余数为 1说明单独的数字在这一位上是 1用按位或(|)记录到结果中 if(sum 1) ret | 1 i; } return ret; } };核心思路从宏观到微观逐位统计既然不能把整个数字放在一起做运算我们就把整型数字拆解成 32 个独立的二进制位0 或 1逐位去分析和统计。1. 寻找规律为什么可以用逐位统计假设我们的数组是[2, 2, 3, 2]二进制表示如下2 ... 0 0 1 02 ... 0 0 1 03 ... 0 0 1 12 ... 0 0 1 0我们来看看每一个二进制位上所有数字的和是多少第 0 位最右边四个数字分别是0, 0, 1, 0。这一位的总和sum 0010 1。第 1 位四个数字分别是1, 1, 1, 1。这一位的总和sum 1111 4。第 2 位及以上全是0总和sum 0。发现规律了吗除了那个只出现一次的数字3其他数字2都出现了 3 次。这意味着对于任意一个二进制位如果那个“只出现一次的数字”在该位上是 0那么该位上所有数字的和必然是 3 的倍数。如果那个“只出现一次的数字”在该位上是 1那么该位上所有数字的和必然是3 的倍数 1。2. 提取规律数学公式我们把所有数字在第i位上的值加起来然后对 3 取余% 3如果余数是0说明那个单独的数字在第i位上是0。如果余数是1说明那个单独的数字在第i位上是1。这就是这段代码最核心的算法思路关键逻辑推理点假设有 3 个果篮代表数组中的数字。规则是其中 2 个果篮里装着一模一样数量的苹果代表出现了 3 次的其他数字。有 1 个果篮里装着未知数量的苹果代表那个只出现 1 次的数字。现在我们把这三个果篮里的苹果全部倒出来数一数总共有多少个。那 2 个一模一样的果篮它们贡献的苹果总数必然是偶数因为 2 个篮子数量相同。再加上那个未知数量的果篮总苹果数 偶数 未知数。如果我们把总数除以 3取余数因为 2 个果篮的数量一样它们加起来一定是 3 的倍数吗不一定。但是因为我们有3 个篮子相当于数字出现了 3 次如果我们把每个数字出现的次数看作 3 次那么这 3 个相同的数字加起来必然是 3 的倍数。回到二进制位0 或 1对于数组中的某一个特定的二进制位比如第 0 位假设那个“只出现一次的数字”在这一位上是0。那么其他所有数字都出现了 3 次在这一位上要么全是 0要么全是 1因为它们是相同的数字。如果其他数字这一位是 0那么这一位所有数字的和 0是 3 的倍数。如果其他数字这一位是 1那么这一位有 3 个 1总和 3是 3 的倍数。再加上那个单独数字的 0总和依然是 3 的倍数。假设那个“只出现一次的数字”在这一位上是1。那么其他所有数字都出现了 3 次在这一位上要么全是 0要么全是 1。如果其他数字这一位是 0那么这一位总和 03的倍数 1单独数字的1 3 的倍数 1。如果其他数字这一位是 1那么这一位有 3 个 1总和 33的倍数 1单独数字的1 3 的倍数 1。这就是为什么单独数字该位是 0 - 总和是 3 的倍数 -sum % 3 0单独数字该位是 1 - 总和是 3 的倍数 1 -sum % 3 1组装结果ret | 1 i如果sum % 3 1说明单独的数字在这一位上是 1。我们用1 i生成一个只有第i位为 1 的数然后通过按位或|赋值给ret。循环结束后ret的每一个二进制位都被正确设置就是我们要找的答案。总结万能模板这道题是“逐位统计法”的绝佳范例。当遇到数组中数字出现K次只有一个数字出现1次时且K 2异或往往失效此时逐位统计 对 K 取模是万能的通用解法。只需把代码中的% 3改成% K即可解决这一类问题。题目五消失的两个数字class Solution { public: vectorint missingTwo(vectorint nums) { // 1. 将所有的数异或在一起 int tmp 0; for(auto x : nums) tmp ^ x; for(int i 1; i nums.size() 2; i) tmp ^ i; // 此时 tmp a ^ b // 2. 找出 a, b 中比特位不同的那一位 int diff 0; while(1) { if(((tmp diff) 1) 1) break; // 找到最低位的 1 else diff; } // 3. 根据 diff 位的不同将所有的数划分为两类来异或 int a 0, b 0; for(int x : nums) if(((x diff) 1) 1) b ^ x; // 第 diff 位为 1 的分到 b 组 else a ^ x; // 第 diff 位为 0 的分到 a 组 for(int i 1; i nums.size() 2; i) if(((i diff) 1) 1) b ^ i; else a ^ i; return {a, b}; } };核心思路化繁为简分而治之假设数组原本应该是[1, 2, 3, 4, 5]但缺失了2和4实际输入是[1, 3, 5]。如果我们直接对整个数组和完整序列[1, 2, 3, 4, 5]进行异或会发生什么根据我们之前学过的“丢失的数字”的思路ret (数组中的所有数) ^ (1 ^ 2 ^ 3 ^ 4 ^ 5)因为1, 3, 5出现了两次一次在数组里一次在完整序列里它们会互相抵消变成0。最后剩下的ret 2 ^ 4。问题来了我们得到了2 ^ 4的结果但我们不知道2和4分别是多少。怎么把它们拆开呢这就引出了本题最核心的三个步骤步骤 1整体异或得到两个缺失数字的异或结果正如上面所说把数组里的所有数和[1, N]的所有数全部异或在一起。结果tmp等于那两个缺失数字的异或值即a ^ b。步骤 2找出a和b中比特位不同的那一位分组依据因为a和b是两个不同的数字所以它们的二进制表示必然至少有一位是不同的。在a ^ b的结果tmp中为 1 的那一位就是a和b不同的位。代码中的while(1)循环就是在找tmp中最低位的1在哪里找到后记录下这个位置diff。为什么找最低位的 1因为这样最容易通过位运算提取出来tmp -tmp也可以做到但代码里用了循环右移找。步骤 3根据diff位分组分别异或既然a和b在第diff位上不同那么在[1, N]的所有数字中有些数字第diff位是 1有些是 0。在输入的数组中有些数字第diff位是 1有些是 0。关键点a和b必然一个在第diff位是 1另一个是 0。它们会被分到不同的组里于是我们可以把数组里的所有数和完整序列[1, N]的所有数按照第diff位是 0 还是 1分成两组组 A所有第diff位为 0 的数。组 B所有第diff位为 1 的数。神奇的事情发生了在组 A 中除了那个缺失的数字假设是a其他数字都出现了两次一次在数组里一次在完整序列里。它们异或后会变成0最后剩下的就是a。同理组 B 中最后剩下的就是b。这就把一个“找两个数字”的难题拆解成了两个“找单个数字”的简单问题。关键细节说明nums.size() 2题目说数组包含从 1 到 N 的所有整数但缺了两个。所以完整的序列长度是nums.size() 2。例如数组长度是 3说明原本应该是 1 到 5缺了 2 个。diff的计算while(1)循环从第 0 位开始逐位检查tmp的二进制位。找到第一个为 1 的位就break。这个diff就是a和b第一个不同的比特位。分组异或代码中使用了两个for循环。第一个for循环遍历输入数组nums。第二个for循环遍历完整序列[1, nums.size() 2]。在循环内部通过((x diff) 1) 1判断该数字属于哪一组。属于组b的就b ^ x属于组a的就a ^ x。因为相同的数字除了缺失的两个会被分到同一组并互相抵消最终a和b就会分别剩下那两个缺失的数字。识别信号特征一明确要求“不使用额外空间”O(1) 空间复杂度这是最强烈的信号。当题目要求空间复杂度为 O(1)且需要记录状态或去重时普通的哈希表unordered_set/map就不能用了此时必须用位运算位图或异或。特征二数组中的数字出现次数有规律成对、多次重复当题目提到“其他数字都出现了 2 次 / 3 次只有一个数字出现 1 次”时这是位运算的绝对主场。出现 2 次直接用异或^利用A ^ A 0抵消。出现 3 次或 K 次异或失效改用逐位统计 取模。缺失两个数字进阶整体异或 找不同位 分组异或特征三题目明确禁止使用、-、*、/运算符当题目要求“不使用加减乘除计算两数之和”时你只能通过模拟计算机底层的二进制加法来实现。核心思路a ^ b算无进位和(a b) 1算进位循环直到进位为 0。特征四涉及“子集”、“状态压缩”或“布尔数组”当题目需要枚举一个集合的所有子集或者需要用一个整数来表示一个布尔数组比如记录哪些任务已完成、哪些物品已放入背包时位运算尤其是1 i和、|是最高效的工具。特征五需要快速进行“乘除 2 的幂”或“判断奇偶”虽然编译器通常会自动优化但在一些底层代码或竞赛中位运算是最快的。乘 2x 1除 2x 1判断奇偶x 1比x % 2 1更快取模 2 的幂x (2^n - 1)比x % 2^n更快特征六与二进制表示、比特位直接相关的题目题目字面上就提到了“二进制”、“比特位”、“0 和 1”等词汇。
算法 --位运算
预备知识基础运算与真值表假设有两个二进制位a和b运算符名称符号规则真值表与AND同为 1 才为 1000, 010, 100, 111或OR|有一个 1 就为 10|00, 0|11, 1|01, 1|11异或XOR^不同为 1相同为 00^00, 0^11, 1^01, 1^10取反NOT~0 变 11 变 0~0 1, ~1 0左移Left Shift高位丢弃低位补 00011 1 0110(相当于乘 2)右移Right Shift低位丢弃高位补符号位0110 1 0011(相当于除 2)注意C 中对于有符号数是算术右移补符号位对于无符号数是逻辑右移补 0。左移时建议使用无符号数以避免未定义行为。核心心法位运算题目表面上是在考二进制的操作实际上是在考降维打击的能力。普通的算法是在“数值”层面操作比如用哈希表记录数字而位运算是在“比特Bit”层面操作。它利用计算机最底层的特性实现了极致的时间/空间复杂度通常能实现 O(N) 时间O(1) 空间。巧妙的数学规律利用异或的抵消律、按位与的进位规律等。题目一判断字符是否唯一class Solution { public: bool isUnique(string astr) { // 1. 鸽巢原理Pigeonhole Principle优化 if(astr.size() 26) return false; // 2. 初始化位图 int bitMap 0; // 3. 遍历字符串 for(auto ch : astr) { // 计算字符对应的偏移量 (a - 0, b - 1, ..., z - 25) int i ch - a; // 4. 检查该位是否已经被标记为 1 if(((bitMap i) 1) 1) return false; // 5. 将该位标记为 1 bitMap | 1 i; } return true; } };关键步骤详细说明鸽巢原理优化 (if(astr.size() 26) return false;)因为题目规定字符串只包含 26 个小写英文字母。如果字符串长度超过 26根据鸽巢原理必然至少有一个字母重复。这一步可以直接拦截大量无效输入提高效率。位图 (int bitMap 0;)一个int类型在大多数现代计算机中占 32 位。题目只需要用到 26 位对应a到z。初始时这 32 位全是0。我们可以把它想象成一个长度为 26 的布尔数组但这比布尔数组更节省空间。从右往左数第 0 位代表a第 1 位代表b以此类推第 25 位代表z。计算索引 (int i ch - a;)利用 ASCII 码将字符映射为 0 到 25 的整数。检查是否出现过 (if(((bitMap i) 1) 1))bitMap i将位图向右移动i位把目标位移动到最低位。 1与1进行按位与操作。如果最低位是1结果为1如果是0结果为0。如果结果为1说明之前已经遇到过这个字符直接返回false。标记字符 (bitMap | 1 i;)1 i生成一个只有第i位为1其余全为0的数。bitMap | ...按位或赋值。这会将bitMap的第i位设置为1表示该字符已经出现过同时不影响其他位。题目二丢失的数字class Solution { public: int missingNumber(vectorint nums) { int ret 0; // 1. 将数组中的所有元素异或起来 for(auto x : nums) ret ^ x; // 2. 将 [0, n] 范围内的所有整数异或起来 // 注意nums.size() 就是 n所以循环条件是 i n for(int i 0; i nums.size(); i) ret ^ i; return ret; } };这段代码实际上做了一件事把数组里的所有数和[0, n]里的所有数全部混在一起进行异或。根据异或的三个核心性质归零律A ^ A 0相同的数异或抵消为 0恒等律A ^ 0 A任何数与 0 异或还是它自己交换律和结合律A ^ B ^ C C ^ A ^ B异或的顺序不影响结果我们可以把这两次循环合并起来看作一个大的异或运算ret (数组中的所有数) ^ (0 ^ 1 ^ 2 ^ ... ^ n)因为数组中有n个数它们分别是[0, n]中除去了那个缺失数字之外的数。所以除了那个缺失的数字之外其他所有的数字都出现了两次一次在数组里一次在[0, n]的完整序列里。根据归零律所有出现两次的数字都会变成0(0 ^ 0) ^ (1 ^ 1) ^ ... ^ (缺失的数字) ^ ... ^ (n ^ n) 0 ^ 0 ^ ... ^ 缺失的数字 ^ ... ^ 0最后根据恒等律所有的0和那个只出现一次的“缺失数字”异或结果就是那个缺失的数字本身0 ^ 0 ^ ... ^ 缺失的数字 缺失的数字模拟运行以示例 1 为例输入nums [3, 0, 1]此时n 3完整范围是[0, 1, 2, 3]。第一个循环异或数组元素ret 0 ^ 3 ^ 0 ^ 1第二个循环异或完整范围 0~3ret (0 ^ 3 ^ 0 ^ 1) ^ (0 ^ 1 ^ 2 ^ 3)利用交换律重新排列ret (0 ^ 0) ^ (1 ^ 1) ^ (3 ^ 3) ^ 2利用归零律消除成对的数字ret 0 ^ 0 ^ 0 ^ 2利用恒等律得出结果ret 2结果2正是缺失的数字题目三两整数之和class Solution { public: int getSum(int a, int b) { while (b ! 0) // 只要还有进位就继续循环 { int x a ^ b; // 步骤1计算无进位相加的结果暂存到 x // 步骤2计算进位 // 注意这里的 (unsigned int) 强制类型转换非常关键 unsigned int carry (unsigned int)(a b) 1; a x; // 将无进位结果赋值给 a准备下一轮 b carry; // 将进位赋值给 b准备下一轮 } return a; // 当进位 b 为 0 时a 就是最终结果 } };加法在二进制层面可以拆解为两个步骤无进位相加先不管进位把两个数的每一位直接相加。计算进位算出哪些位产生了进位并将进位加到正确的位置上。循环将“无进位的结果”和“进位”作为新的两个数重复上述过程直到没有进位为止。为什么用异或^和按位与异或^模拟“无进位加法”回顾异或的规则0^00,1^10,0^11,1^01。这和不考虑进位的二进制加法结果完全一致。例如1 1 10二进制如果不考虑进位本位应该是0正好是1 ^ 1 0。按位与模拟“进位”什么时候会产生进位只有当两个数的某一位同时为 1时1 1 1才会向高位进 1。所以a b找出了所有需要进位的位。但进位是加到高一位的所以需要左移 1 位 1。模拟一个产生进位的例子输入a 3(二进制0011)b 1(二进制0001)第一轮循环x a ^ b0011 ^ 00010010(即 2)carry (0011 0001) 10001 10010(即 2产生了进位)a 2b 2第二轮循环(b 2 ! 0)x a ^ b0010 ^ 00100000(即 0)carry (0010 0010) 10010 10100(即 4)a 0b 4第三轮循环(b 4 ! 0)x a ^ b0000 ^ 01000100(即 4)carry (0000 0100) 10000 10a 4b 0第四轮循环判断b 0循环结束。返回a即4。 (3 1 4正确)题目四只出现一次的数字IIclass Solution { public: int singleNumber(vectorint nums) { int ret 0; // 1. 遍历整数的 32 个二进制位 (从第 0 位到第 31 位) for(int i 0; i 32; i) { int sum 0; // 2. 遍历数组中的每一个数字 for(int x : nums) { // 3. 提取数字 x 的第 i 位并累加到 sum 中 if(((x i) 1) 1) sum; } // 4. 对统计结果取模 3 sum % 3; // 5. 如果余数为 1说明单独的数字在这一位上是 1用按位或(|)记录到结果中 if(sum 1) ret | 1 i; } return ret; } };核心思路从宏观到微观逐位统计既然不能把整个数字放在一起做运算我们就把整型数字拆解成 32 个独立的二进制位0 或 1逐位去分析和统计。1. 寻找规律为什么可以用逐位统计假设我们的数组是[2, 2, 3, 2]二进制表示如下2 ... 0 0 1 02 ... 0 0 1 03 ... 0 0 1 12 ... 0 0 1 0我们来看看每一个二进制位上所有数字的和是多少第 0 位最右边四个数字分别是0, 0, 1, 0。这一位的总和sum 0010 1。第 1 位四个数字分别是1, 1, 1, 1。这一位的总和sum 1111 4。第 2 位及以上全是0总和sum 0。发现规律了吗除了那个只出现一次的数字3其他数字2都出现了 3 次。这意味着对于任意一个二进制位如果那个“只出现一次的数字”在该位上是 0那么该位上所有数字的和必然是 3 的倍数。如果那个“只出现一次的数字”在该位上是 1那么该位上所有数字的和必然是3 的倍数 1。2. 提取规律数学公式我们把所有数字在第i位上的值加起来然后对 3 取余% 3如果余数是0说明那个单独的数字在第i位上是0。如果余数是1说明那个单独的数字在第i位上是1。这就是这段代码最核心的算法思路关键逻辑推理点假设有 3 个果篮代表数组中的数字。规则是其中 2 个果篮里装着一模一样数量的苹果代表出现了 3 次的其他数字。有 1 个果篮里装着未知数量的苹果代表那个只出现 1 次的数字。现在我们把这三个果篮里的苹果全部倒出来数一数总共有多少个。那 2 个一模一样的果篮它们贡献的苹果总数必然是偶数因为 2 个篮子数量相同。再加上那个未知数量的果篮总苹果数 偶数 未知数。如果我们把总数除以 3取余数因为 2 个果篮的数量一样它们加起来一定是 3 的倍数吗不一定。但是因为我们有3 个篮子相当于数字出现了 3 次如果我们把每个数字出现的次数看作 3 次那么这 3 个相同的数字加起来必然是 3 的倍数。回到二进制位0 或 1对于数组中的某一个特定的二进制位比如第 0 位假设那个“只出现一次的数字”在这一位上是0。那么其他所有数字都出现了 3 次在这一位上要么全是 0要么全是 1因为它们是相同的数字。如果其他数字这一位是 0那么这一位所有数字的和 0是 3 的倍数。如果其他数字这一位是 1那么这一位有 3 个 1总和 3是 3 的倍数。再加上那个单独数字的 0总和依然是 3 的倍数。假设那个“只出现一次的数字”在这一位上是1。那么其他所有数字都出现了 3 次在这一位上要么全是 0要么全是 1。如果其他数字这一位是 0那么这一位总和 03的倍数 1单独数字的1 3 的倍数 1。如果其他数字这一位是 1那么这一位有 3 个 1总和 33的倍数 1单独数字的1 3 的倍数 1。这就是为什么单独数字该位是 0 - 总和是 3 的倍数 -sum % 3 0单独数字该位是 1 - 总和是 3 的倍数 1 -sum % 3 1组装结果ret | 1 i如果sum % 3 1说明单独的数字在这一位上是 1。我们用1 i生成一个只有第i位为 1 的数然后通过按位或|赋值给ret。循环结束后ret的每一个二进制位都被正确设置就是我们要找的答案。总结万能模板这道题是“逐位统计法”的绝佳范例。当遇到数组中数字出现K次只有一个数字出现1次时且K 2异或往往失效此时逐位统计 对 K 取模是万能的通用解法。只需把代码中的% 3改成% K即可解决这一类问题。题目五消失的两个数字class Solution { public: vectorint missingTwo(vectorint nums) { // 1. 将所有的数异或在一起 int tmp 0; for(auto x : nums) tmp ^ x; for(int i 1; i nums.size() 2; i) tmp ^ i; // 此时 tmp a ^ b // 2. 找出 a, b 中比特位不同的那一位 int diff 0; while(1) { if(((tmp diff) 1) 1) break; // 找到最低位的 1 else diff; } // 3. 根据 diff 位的不同将所有的数划分为两类来异或 int a 0, b 0; for(int x : nums) if(((x diff) 1) 1) b ^ x; // 第 diff 位为 1 的分到 b 组 else a ^ x; // 第 diff 位为 0 的分到 a 组 for(int i 1; i nums.size() 2; i) if(((i diff) 1) 1) b ^ i; else a ^ i; return {a, b}; } };核心思路化繁为简分而治之假设数组原本应该是[1, 2, 3, 4, 5]但缺失了2和4实际输入是[1, 3, 5]。如果我们直接对整个数组和完整序列[1, 2, 3, 4, 5]进行异或会发生什么根据我们之前学过的“丢失的数字”的思路ret (数组中的所有数) ^ (1 ^ 2 ^ 3 ^ 4 ^ 5)因为1, 3, 5出现了两次一次在数组里一次在完整序列里它们会互相抵消变成0。最后剩下的ret 2 ^ 4。问题来了我们得到了2 ^ 4的结果但我们不知道2和4分别是多少。怎么把它们拆开呢这就引出了本题最核心的三个步骤步骤 1整体异或得到两个缺失数字的异或结果正如上面所说把数组里的所有数和[1, N]的所有数全部异或在一起。结果tmp等于那两个缺失数字的异或值即a ^ b。步骤 2找出a和b中比特位不同的那一位分组依据因为a和b是两个不同的数字所以它们的二进制表示必然至少有一位是不同的。在a ^ b的结果tmp中为 1 的那一位就是a和b不同的位。代码中的while(1)循环就是在找tmp中最低位的1在哪里找到后记录下这个位置diff。为什么找最低位的 1因为这样最容易通过位运算提取出来tmp -tmp也可以做到但代码里用了循环右移找。步骤 3根据diff位分组分别异或既然a和b在第diff位上不同那么在[1, N]的所有数字中有些数字第diff位是 1有些是 0。在输入的数组中有些数字第diff位是 1有些是 0。关键点a和b必然一个在第diff位是 1另一个是 0。它们会被分到不同的组里于是我们可以把数组里的所有数和完整序列[1, N]的所有数按照第diff位是 0 还是 1分成两组组 A所有第diff位为 0 的数。组 B所有第diff位为 1 的数。神奇的事情发生了在组 A 中除了那个缺失的数字假设是a其他数字都出现了两次一次在数组里一次在完整序列里。它们异或后会变成0最后剩下的就是a。同理组 B 中最后剩下的就是b。这就把一个“找两个数字”的难题拆解成了两个“找单个数字”的简单问题。关键细节说明nums.size() 2题目说数组包含从 1 到 N 的所有整数但缺了两个。所以完整的序列长度是nums.size() 2。例如数组长度是 3说明原本应该是 1 到 5缺了 2 个。diff的计算while(1)循环从第 0 位开始逐位检查tmp的二进制位。找到第一个为 1 的位就break。这个diff就是a和b第一个不同的比特位。分组异或代码中使用了两个for循环。第一个for循环遍历输入数组nums。第二个for循环遍历完整序列[1, nums.size() 2]。在循环内部通过((x diff) 1) 1判断该数字属于哪一组。属于组b的就b ^ x属于组a的就a ^ x。因为相同的数字除了缺失的两个会被分到同一组并互相抵消最终a和b就会分别剩下那两个缺失的数字。识别信号特征一明确要求“不使用额外空间”O(1) 空间复杂度这是最强烈的信号。当题目要求空间复杂度为 O(1)且需要记录状态或去重时普通的哈希表unordered_set/map就不能用了此时必须用位运算位图或异或。特征二数组中的数字出现次数有规律成对、多次重复当题目提到“其他数字都出现了 2 次 / 3 次只有一个数字出现 1 次”时这是位运算的绝对主场。出现 2 次直接用异或^利用A ^ A 0抵消。出现 3 次或 K 次异或失效改用逐位统计 取模。缺失两个数字进阶整体异或 找不同位 分组异或特征三题目明确禁止使用、-、*、/运算符当题目要求“不使用加减乘除计算两数之和”时你只能通过模拟计算机底层的二进制加法来实现。核心思路a ^ b算无进位和(a b) 1算进位循环直到进位为 0。特征四涉及“子集”、“状态压缩”或“布尔数组”当题目需要枚举一个集合的所有子集或者需要用一个整数来表示一个布尔数组比如记录哪些任务已完成、哪些物品已放入背包时位运算尤其是1 i和、|是最高效的工具。特征五需要快速进行“乘除 2 的幂”或“判断奇偶”虽然编译器通常会自动优化但在一些底层代码或竞赛中位运算是最快的。乘 2x 1除 2x 1判断奇偶x 1比x % 2 1更快取模 2 的幂x (2^n - 1)比x % 2^n更快特征六与二进制表示、比特位直接相关的题目题目字面上就提到了“二进制”、“比特位”、“0 和 1”等词汇。
