C++算法
算法位运算实战：两整数之和、只出现一次数字及消失数字
位运算解决三道经典算法题。第一题利用异或无进位加法与按位与进位循环求解两数之和。第二题统计比特位总和模三还原唯一数字。第三题通过异或分组将缺失两数问题转化为单数查找。代码均使用 C++ 实现，时间复杂度优化至线性。
位运算解决三道经典算法题。第一题利用异或无进位加法与按位与进位循环求解两数之和。第二题统计比特位总和模三还原唯一数字。第三题通过异或分组将缺失两数问题转化为单数查找。代码均使用 C++ 实现，时间复杂度优化至线性。
^ 运算本质是【无进位加法】& 操作能够得到【进位】的对应位置，但还需要左移 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};
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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