前言
上一篇博客，我们已经把位运算的基础知识，以及基本运算都掌握啦
上次的习题还是让人意犹未尽，今天我们来尝试一下难一点的题目
位运算熟练起来真的让人觉得做题是一种享受
fellow me
丢失的数字
丢失的数字
思路：
少了一个数字，给他找回来不就好了吗
让我想到直接对数组 按位异或 一遍， 然后再对 0-n 按位异或一遍，出现两次的都消消乐
剩下的就是我们要找的数字
class Solution
{
public:
int missingNumber(vector<int>& nums)
{
int ans = 0;
for(auto x : nums)
{
ans ^= x; // 按位异或当前数组
}
for(int i = 0; i <= nums.size(); i++)
{
ans ^= i; // 重新按位异或一遍 0-n
}
return ans;
}
};
两整数之和
思路：
乍一看，不让我用运算方法，那不是完蛋了吗
但仔细想想，这不是学了位运算，前面了解到按位异或（^）是无进制加法，按位与（&）是进位
其实可以组合起来使用，我们先算出无进位相加的结果，然后再找出进位，给他加上，再如此反复循环，直到没有进位
class Solution
{
public:
int getSum(int a, int b)
{
while(b != 0)
{
int x = a ^ b; // 无进位相加
// 这里无符号 是防止溢出
unsigned int cur = (unsigned int) (a & b) << 1; // 找出进位
a = x;
b = cur;
}
return a;
}
};
就这么几行，想明白了，还是很简单的
只出现一次的数字II
只出现一次的数字II
思路：
一眼hash直接秒了，但是题目要求常数级空间。。。。。
设要找的数位 ret
由于整个数组中，需要找的元素只出现了「一次」，其余的数都出现的「三次」，因此我们可以根据所有数的「某一个比特位」的总和 %3 的结果，快速定位到 ret 的「一个比特位上」的值是0 还是 1
这样，我们通过 ret 的每一个比特位上的值，就可以将 ret 给还原出来
class Solution
{
public:
int singleNumber(vector<int>& nums)
{
int ret = 0;
for(int i = 0; i < 32; i++)
{
int sum = 0;
for(auto x : nums)
{
if(((x >> i) & 1) == 1) // 判断当前比特位
{
sum++; // 累积个数
}
}
sum %= 3;
if(sum == 1) // 符合条件就把ret当前的比特位置为 1
{
ret = ret | 1 << i;
}
}
return ret;
}
};
做完发现位运算真好奇妙
消失的两个数字
消失的两个数字
最后一题hard难度结尾吧
思路：
缺了两个数字，想到前面热乎的缺一个数字，我们可以按位异或两遍给他找出来，但是找出来的是两个数字的异或
所以我们还要处理这两个数字的异或，分解他们，又想到我们上一次做过的（两个只出现一次的数字）
好像就是两个题目的融合，才让他到了hard的难度
class Solution
{
public:
vector<int> missingTwo(vector<int>& nums)
{
int ans = 0;
for(auto x : nums)
ans ^= x;
for(int i = 1; i <= nums.size() + 2; i++)
ans ^= i;
// 现在找到了两个数字的异或
int x = 0, y = 0;
ans = ans & (-(long long)ans); // 提起ans二进制最右侧的 1
for(auto i : nums) // 分组异或
{
if((i & ans) == ans)
x ^= i;
else
y ^= i;
}
for(int i = 1; i <= nums.size() + 2; i++)// 分组异或
{
if((i & ans) == ans)
x ^= i;
else
y ^= i;
}
return {x, y};
}
};
prefect 位运算完美收官
总结
今天通过几道位运算题目，巩固了位运算的应用技巧：
- 丢失的数字
利用异或性质，两次异或数组和0~n的数，出现两次的抵消，剩下的即为缺失数。 - 两整数之和
通过异或（无进位加法）和与运算左移（进位）模拟加法，循环处理进位直至为零，注意用unsigned避免溢出。 - 只出现一次的数字II
统计每一位1的个数，模3后确定目标数各位的值，逐位组合得到结果。 - 消失的两个数字
结合异或和分组思想，先找到两数异或结果，提取最右1进行分组，分别异或数组和完整序列得到两数。
心得
位运算题目需灵活运用位操作性质，如异或消重、与运算找进位、按位统计等
通过分解问题、逐步处理，能将复杂问题简化，然后逐个击破
今天的内容就到这里啦，不要走开，小编持续更新中~~~~
