前言
上篇谈到了位运算的相关语法及原理和部分基础题目配合讲解，本篇将结合进阶题目，深化对于位运算的掌握运用。
一. 只出现一次的数字||
1.1 题目链接：https://leetcode.cn/problems/single-number-ii/description/
1.2 题目分析：
给定一个数组，该数组内除目标值外，其他值均出现了3次，要求找到该只出现一次的目标值。
时间复杂度为O(n),空间复杂度为O(1).
1.3 思路讲解：
比特位计数：
设要找的数位 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)
{
sum++;
}
}//每个比特位逐次累加
sum%=3;
if(sum==1)
{
ret|=1<<i;
}
}//循环32次确定ret每一个比特位的值
return ret;
}
};
二. 消失的两个数字
2.1 题目链接：https://leetcode.cn/problems/missing-two-lcci/
2.2 题目分析:
给定数组，范围为[1,n]，但里面缺失了两个数字，要求返回这两个缺失数字，返回顺序不做要求。
2.3 思路讲解：
在消失的数字中，我们采用两轮异或的方式，即可直接求出，而本题有两个缺失的数字，我们又该如何处理呢？
- 我们仍可以采取两轮异或的方式，即令sum=0，先与数组内每个元素异或，再与[1,n]内每个元素异或，此时结果即为缺失的数字a和b异或的值。
- 为将a和b分别求出，我们首先需要找出a与b不同的比特位，由于异或的结果相同为0，相异为1，因此我们逐个右移判断，当值为1时即代表该比特位a与b不同。
- 我们将该处位置记录为diff，假设a的diff位为1，b的diff位为0，a分别与数组内diff位的值位1的元素异或，b分别与数组内diff位的值位0的元素异或.
- 最终返回a，b即可
2.4 代码实现：
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
int n=nums.size();
int sum=0;
for(auto e:nums)
{
sum^=e;
}
for(int i=1;i<=n+2;i++)
{
sum^=i;
}//两轮异或之后sum即为缺失数字a与b异或的结果
int diff=0;
while(1)
{
if(sum>>diff&1)
{
break;
}
else
diff++;
}//寻找a和b比特位不同的位置
int a=0,b=0;
for(auto e:nums)
{
if(e>>diff&1)
{
a^=e;
}
else
{
b^=e;
}
}
for(int i=1;i<=n+2;i++)
{
if(i>>diff&1)
{
a^=i;
}
else
{
b^=i;
}
}//逐次异或
return {a,b};
}
};
三. 实际应用场景
-
数据压缩与加密
位运算常用于高效数据压缩算法，如哈夫曼编码，以及对数据进行快速加密与解密。 -
硬件设计与信号处理
在数字电路中，位运算是描述逻辑门操作的基础，例如AND、OR、XOR等。 -
图形与图像处理
位运算在位图处理与图像渲染中具有重要应用，通过掩码操作快速处理像素信息。 -
高效算法设计
位运算能显著优化算法的时间复杂度，尤其在需要频繁操作整数的场景中，如哈希函数、图论算法等。
小结
位运算在计算机科学中扮演着举足轻重的角色，它不仅以其高效和简洁让代码更具性能优势，还通过独特的逻辑体现了数学与工程的完美融合。在学习与实践中，善于发现和利用位运算的特性，能够让算法设计更加优雅，也能更深刻地理解计算机的底层逻辑。
“数尽千般妙，唯有位运藏。” 让我们以这一句诗作结，致敬位运算的奇妙世界。
关于位运算的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！
