C++算法
算法题讲解：位运算应用（两数之和、只出现一次的数字、消失的两个数字）
位运算在算法题中的应用，涵盖两整数之和、只出现一次的数字 II 以及消失的两个数字。解决方案包括利用异或实现无进位加法循环处理进位、统计比特位总和模三还原唯一数字、以及通过异或分组查找缺失数字。
位运算在算法题中的应用，涵盖两整数之和、只出现一次的数字 II 以及消失的两个数字。解决方案包括利用异或实现无进位加法循环处理进位、统计比特位总和模三还原唯一数字、以及通过异或分组查找缺失数字。
^ 运算本质是【无进位加法】& 操作能够得到【进位】的对应位置，但还需要左移 1 才是需要进位的位置。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;
}
};
设要找的数为 ret。 由于整个数组中，需要找的元素只出现了【一次】，其余的数都出现【三次】，因此我们可以用根据所有数的【某一个比特位】的总和 %3 的结果，快速定位到 ret 上的【一个比特位上】的值 是 0 还是 1。 这样我们通过 ret 的每一个比特位上的值，就可以将 ret 还原出来。
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;
}
};
本题相当于就是 268.丢失的数字 + 260.只出现一次的数字||| 组合起来的题。 先将数组中的数和【1，n+2】区间内的所有数【异或】在一起，问题就变成了：有两个数出现了【一次】，其余所有的数出现了【两次】。进而变成了 260.只出现了一次的数字||| 这道题。
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 题利用比特位计数技术，统计所有数字各二进制位出现次数，模 3 结果定位唯一出现一次的数字；第 38 题通过位运算巧妙解决。首先将数组与 [1,n+2] 区间所有数异或，转化为两个数出现一次的问题。核心思路借鉴了 260 题《只出现一次的数字 III》，通过提取不同比特位将数分组异或，最终找到缺失的两个数。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online