【优选算法篇】：深入浅出位运算--性能优化的利器
✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：优选算法篇–CSDN博客
文章目录
- 一.位运算
- 一.位运算概述
- 二.常见的位运算操作符
- 三.常见的位运算使用场景
- 二.例题
- 1.判断字符是否唯一
- 2.丢失的数字
- 3.两整数之和
- 4.只出现一次的数字||
- 5.只出现一次的数字|||
- 6.消失的两个数字
一.位运算
一.位运算概述
位运算（Bitwise operation）是直接对整数在内存中的二进制位进行操作的运算。在计算机编程中，位运算非常高效，因为它们直接在二进制层面上操作数据，能够以较少的操作实现复杂的逻辑。下面是几种常用的位运算符号讲解。
二.常见的位运算操作符
-
按位与（&）
- 规则：
- 对两个整数对应的二进制位进行操作，如果对应的二进制位都为1，则结果位为1，否则为0。
- 示例：
- 假设我们有整数5（二进制为0101）和3（二进制为0011）。
- 5 & 3的计算过程为：
- 0101
- &0011
- 0001（结果为1）
- 应用场景：
- 常用于掩码操作。例如，要判断一个整数的某一位是否为1，可以将该整数与一个只有对应位为1的掩码进行按位与操作。
- 规则：
-
按位或（|）
- 规则：
- 对两个整数对应的二进制位进行操作，如果对应的二进制位中有一个为1，则结果位为1。
- 示例：
- 对于整数5（0101）和3（0011）。
- 5 | 3的计算过程为：
- 0101
- |0011
- 0111（结果为7）
- 应用场景：
- 可以用于设置某些位的值。例如，要将一个整数的某几位设置为1，可以将该整数与一个只有对应位为1的数进行按位或操作。
- 规则：
-
按位异或（^）
- 规则：
- 对两个整数对应的二进制位进行操作，如果对应的二进制位不同，则结果位为1，相同则为0。
- 示例：
- 对于整数5（0101）和3（0011）。
- 5 ^ 3的计算过程为：
- 0101
- ^0011
- 0110（结果为6）
- 应用场景：
- 常用于加密算法中的简单加密和解密操作，因为一个数与另一个数进行两次异或操作会得到原数。
- 规则：
-
按位取反（~）
- 规则：
- 对一个整数的二进制位进行取反操作，即0变为1，1变为0。
- 示例：
- 对于整数5（0101）。
- ~5的计算过程为：
- 0101取反后为1010（结果为 - 6，因为在有符号数的表示中，取反后会涉及到补码等概念，在8位二进制表示下，1010表示 - 6）
- 应用场景：
- 在一些底层的逻辑判断和数据处理中，用于反转数据的某些特性。
- 规则：
-
左移（<<）
- 规则：
- 将一个整数的二进制位向左移动指定的位数，右边空出的位用0填充。
- 示例：
- 对于整数5（0101），5 << 2表示将5的二进制位向左移动2位。
- 0101 << 2后变为010100（结果为20，因为左移n位相当于乘以2的n次方，这里5×2² = 20）
- 应用场景：
- 常用于快速乘以2的幂次方的计算，在优化算法中经常用到。
- 规则：
-
右移（>>）
-
规则：
- 将一个整数的二进制位向右移动指定的位数。如果是无符号数，左边空出的位用0填充；如果是有符号数，根据不同的编程语言和机器，可能是用符号位填充（算术右移）或者用0填充（逻辑右移）。
-
示例：
-
对于整数12（1100），12 >> 1表示将12的二进制向右移1位。
-
算术右移（有符号数）：
1100>>1变为1110（结果为-6，因为对于有符号数右移后要保持不变，原数12（假定位8位有符号数二进制表示为1110，符号位为1表示负数，将数值部分右移1位表示负数，将数值部分右移1位后得到1110，在补码表示下为-6）。
-
逻辑右移：
1100>>1变为0110（结果为6，逻辑右移是简单的将二进制位右移，左边补0）。
-
-
应用场景：
- 常用于快速除以2的幂次方的计算呢，不过对于有符号数的算术右移要注意符号相关的问题。
-
三.常见的位运算使用场景
二.例题
1.判断字符是否唯一
题目：
算法原理：
利用位图的思想，一个整型有32位，正好可以存放26个字母，一位对应一个字母。
计算每个字母对应的位置，再将该位置标记为1，通过左移即可实现找到对应的位置。
如果该位置已经标记为1时，说明存在重复元素。
这里有一个小的优化，因为每个字母只能出现一次，所以字符串最大长度只能为26，如果字符串长度大于26时，即可直接返回false。
代码实现：
bool isUnique(string astr){
//鸽巢原理优化
if(astr.length()>26){
return false;
}
//位图思想
int bitmap = 0;
for(auto ch : astr){
//先求出字符所对应的位置下标
int i = ch - 'a';
//如果当前字符的位置为一说明字符重复
if((bitmap>>i)&1==1){
return false;
}
bitmap |= (1 << i);
}
return true;
}
2.丢失的数字
题目：
算法原理：
根据异或的特点，相同为0，相异为1，将丢失数字的数组和没有丢失数字的原数组中所有的值全部异或即可找到丢失的数字。
代码实现：
int missingNumber(vector<int>& nums){
//位运算
int ans = nums[0];
for (int i = 1; i < nums.size();i++){
ans ^= nums[i];
}
for (int i = 0; i < nums.size() + 1;i++){
ans ^= i;
}
return ans;
}
3.两整数之和
题目：
算法原理：
代码实现：
//371.两整数之和
int getSum(int a, int b){
while(b){
int cur=a;
a ^= b;
b &= cur;
b <<= 1;
}
return a;
}
4.只出现一次的数字||
题目：
算法原理：
代码实现：
int singleNumber(vector<int>& nums){
int ret = 0;
for (int i = 0; i < 32;i++){
int sum = 0;
//求出数组中每个数的第i位之和
for(auto num : nums){
if((num>>i)&1==1){
sum++;
}
}
//求出只出现一次数字的第i位是1还是0
sum %= 3;
//修改ret的第i位
if(sum==1){
ret |= (1 << i);
}
}
return ret;
}
5.只出现一次的数字|||
题目：
算法原理：
代码实现：
vector<int> singleNumber(vector<int>& nums) {
int tmp=0;
for(auto num : nums){
tmp^=num;
}
int mapbit=0;
for(int i=0;i<32;i++){
if(((tmp>>i)&1)==1){
mapbit=i;
break;
}
}
int ans1=0,ans2=0;
for(auto num : nums){
if(((num>>mapbit)&1)==1){
ans1^=num;
}
else{
ans2^=num;
}
}
return {ans1,ans2};
}
6.消失的两个数字
题目：
算法原理：
这道题其实就是前面两种题型的综合，丢失的数字+只出现一次的数字|||。
具体的算法原理就不再讲解，可以直接看代码实现来理解。
代码实现：
vector<int> missingTwo(vector<int>& nums){
//1.将当前数组和没有消失的两个数字的原数组全部异或
int tmp = 0;
for (auto num : nums){
tmp ^= num;
}
for (int i = 1; i <= nums.size() + 2;i++){
tmp ^= i;
}
//2.找到异或后的值哪一位为1
int mapbit = 0;
for (int i = 0;i<32;i++){
if(((tmp>>i)&1)==1){
mapbit = i;
break;
}
}
//3.根据异或后的值哪一位为1将两个数组中的所有值划分成两个，两个消失的数字分别在其中一个
int ans1 = 0, ans2 = 0;
for (auto num : nums){
if(((num>>mapbit)&1)==1){
ans1 ^= num;
}
else{
ans2 ^= num;
}
}
for (int i = 1; i <= nums.size() + 2; i++)
{
if(((i>>mapbit)&1)==1){
ans1 ^= i;
}
else{
ans2 ^= i;
}
}
return {ans1, ans2};
}
以上就是关于位运算算法的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！
