《算法题讲解指南：优选算法-位运算》--35.两个整数之和，36.只出现一次的数字 ||，37.消失的两个数字
🔥小叶-duck：个人主页
❄️个人专栏：《Data-Structure-Learning》
《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--从优选到贪心
✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游
目录
35.两个整数之和
题目链接：
371. 两整数之和 - 力扣（LeetCode）
题目描述：
题目示例：
解法（位运算）：
算法思路：
- 异或
^运算本质是【无进位加法】 - 按位与
&操作能够得到【进位】的对应位置，但还需要左移1才是需要进位的位置。 - 然后一直循环，直到【进位】变成 0 为止
C++算法代码：
class Solution { public: int getSum(int a, int b) { //解法：位运算(^异或：无进位相加) while(b) { int x = a ^ b; int y = (a & b) << 1; a = x; b = y;//得到进位的对应位置，再左移1才是需要进位的位置 //只进行一次a & b不一定保证新的a和b没有需要进位的位置，所以需要将这个步骤进行循环 //a & b为0则说明没有进位的位置了 } return a ^ b; } };算法总结及流程解析：
36.只出现一次的数字 ||
题目链接：
137. 只出现一次的数字 II - 力扣（LeetCode）
题目描述：
题目示例：
解法（比特位计数）：
算法思路：
设要找的数为 ret。
由于整个数组中，需要找的元素只出现了【一次】，其余的数都出现【三次】，因此我们可以用根据所有数的【某一个比特位】的总和 %3 的结果，快速定位到 ret 上的【一个比特位上】的值 是 0 还是 1。
这样我们通过 ret 的每一个比特位上的值，就可以将 ret 还原出来。
C++算法代码：
class Solution { public: int singleNumber(vector<int>& nums) { //方法一：排序(时间复杂度较大:O(NlogN)，但容易想到) // sort(nums.begin(), nums.end()); // for(int i = 0; i < nums.size() - 1; i += 3) // { // if(nums[i] != nums[i + 1]) // { // return nums[i]; // } // } // return nums.back(); //方法二：位运算(为线性时间复杂度:O(32N)，但非常巧妙比较难想) int ret = 0;//作为位图 for(int i = 0; i < 32; i++) //一个数二进制位的长度,依次修改ret的每一位 { int sum = 0; for(int x = 0; x < nums.size(); x++) //计算nums中所有数的二进制第i位的和 { sum += ((nums[x] >> i) & 1); } ret |= ((sum % 3) << i); //求和结果余3后修改到ret对应第i位的位置 } return ret; } };算法总结及流程解析：
38. 消失的两个数字
题目链接：
面试题 17.19. 消失的两个数字 - 力扣（LeetCode）
题目描述：
题目示例：
解法（位运算）：
算法思路：
本题相当于就是 268.丢失的数字 + 260.只出现一次的数字||| 组合起来的题。
先将数组中的数和【1，n+2】区间内的所有数【异或】在一起，问题就变成了：有两个数出现了【一次】，其余所有的数出现了【两次】。进而变成了 260.只出现了一次的数字||| 这道题。
C++算法代码：
class Solution { public: vector<int> missingTwo(vector<int>& nums) { //位运算 //先将数组nums所有数以及1~N+2区间所有数全部异或一遍，得到消失两数的异或 int ret = 0; int a = 0; int b = 0; //分别表示两个消失的数 for(int i = 0; i < nums.size(); i++) { ret ^= nums[i]; } for(int i = 1; i <= nums.size() + 2; i++) { ret ^= i; } //此时ret = a ^ b //由于a和b一定不同，所以一定会存在某一位比特位一个是0一个是1 ////两者异或后对应的那一位就一定是1，所以我们需要找到那一位 //获取到ret最右侧出现1的比特位位置 int x = 0; while(1) { if(((ret >> x) & 1) == 1) { break; } x++; } //将数组nums所有数以及(1~N+2)区间所有数分成两类： //一类就是第x位比特位值为0，一类就是第x位比特位值为1 ////这样两个消失数就会被分开，通过异或，在数组以及(1~N+2)区间都出现的数就会抵消， //a和b也就分别是这两个消失数了 for(int i = 0; i < nums.size(); i++) { if(((nums[i] >> x) & 1) == 0)//假设a是第x位比特位为0的消失数 { a ^= nums[i]; } else //假设b就是第x位比特位为1的消失数 { b ^= nums[i]; } } for(int i = 1; i <= nums.size() + 2; i++) { if(((i >> x) & 1) == 0) { a ^= i; } else { b ^= i; } }//两次循环则数组中存在的数异或了两次被抵消，a和b就分别是两个消失数 return {a, b}; } };算法总结及流程解析：
结束语
到此，35.两个整数之和，36.只出现一次的数字 ||，37.消失的两个数字 这三道算法题就讲解完了。第35题通过异或和按位与操作实现无进位加法，循环处理进位直至为零，高效求解两数之和；第36题利用比特位计数技术，统计所有数字各二进制位出现次数，模3结果定位唯一出现一次的数字；第37题通过位运算巧妙解决。首先将数组与[1,n+2]区间所有数异或，转化为两个数出现一次的问题。核心思路借鉴了260题《只出现一次的数字III》，通过提取不同比特位将数分组异或，最终找到缺失的两个数。希望大家能有所收获！
