前言
本专栏上一篇博客学习了前缀和有关进阶的习题
就是前缀和和hash结合起来会很妙
今天我们来学习新的算法——位运算
话不多说，fellow me
基本位运算符
按位与（AND，&）
规则：对应位均为1时结果为1，否则为0
示例：5 & 3（二进制101 & 011）结果为001（十进制1）
按位或（OR，|）
规则：对应位至少一个为1时结果为1
示例：5 | 3（101 | 011）结果为111（十进制7）
按位异或（XOR，^）
规则：对应位不同时结果为1，否则为0
示例：5 ^ 3（101 ^ 011）结果为110（十进制6）
按位非（NOT，~）
规则：每位取反（0变1，1变0）
示例：~5（假设8位，00000101取反为11111010，即十进制-6）
位移运算
左移（<<）：高位丢弃，低位补0
示例：5 << 1（101左移1位为1010，即10）
右移（>> 和 >>>）
算术右移（>>）：高位补符号位（负数补1，正数补0）
示例：-5 >> 1（二进制11111011右移为11111101，即-3）
逻辑右移（>>>）：高位补0（无符号右移）
示例：-5 >>> 1结果为较大正数（具体值取决于位数）
基本的位运算就是这些啦，下面再给大家看一些东西
异或 ^ 运算 消消乐（相同的两个数） 交换率
无进位相加
给定数 判断二进制位
将二进制位修改成 1
将二进制位修改成 0
提取二进制位 最右侧的 1 消去最右侧的 1
这些东西在位运算的习题中可是大有用处~~~
只出现一次的数字
只出现一次的数字
思路:
这题看到其他都是出现了两次,可以直接用按位异或全部消除,剩下的就是那个只出现一次的数据了
这个还是很简单的
class Solution
{
public:
int singleNumber(vector<int>& nums)
{
int ans = 0;
for(auto x : nums)
ans ^= x;
return ans;
}
};
汉明距离
汉明距离
思路：
题目是要我们找出二进制位不同的个数，想起 按位异或 操作，二进制位相同为 0，不同为 1
我们可以对两个数异或操作之后，再一步一步消除最右侧的 1，累积个数
直接一点也可以一步一步运算符左移，一位一位比较
// 直接一位一位比较
class Solution
{
public:
int hammingDistance(int x, int y)
{
int ans = 0;
for(int i = 0; i < 32; i++)
{
if(((x >> i) & 1) != ((y >> i) & 1))// 判断当前位置是否相同
ans++;
}
return ans;
}
};
// 按位异或之后 再逐步消除右侧的 1
class Solution
{
public:
int hammingDistance(int x, int y)
{
int ans = 0;
int cur = x ^ y;
while(cur)
{
cur = cur & (cur - 1);
ans++;
}
return ans;
}
};
比特位计数
思路：
和上一题其实差不多，数出1的个数，可以直接暴力不断右移找1，也可以不断消除最右侧的1，累积次数
class Solution
{
public:
vector<int> countBits(int n)
{
vector<int> ans;
for(int i = 0; i <= n; i++)
{
int ret = 0;
int x = i;
while(x)
{
x = x & (x - 1);//一边消除一边计数
ret++;
}
ans.push_back(ret);
}
return ans;
}
};
class Solution
{
public:
vector<int> countBits(int n)
{
vector<int> ans;
for(int i = 0; i <= n; i++)
{
int ret = 0;
int x = i;
for(int j = 0; j < 32; j++) // 遍历每一位
{
if((x>>j) & 1 == 1)
ret++;
}
ans.push_back(ret);
}
return ans;
}
};
位1的个数
位1的个数
思路：
简简单单，就是数二进制1的个数，再别说了，上代码
class Solution
{
public:
int hammingWeight(int n)
{
int ans = 0;
while(n)
{
n = n & (n - 1);
ans++;
}
return ans;
}
};
只出现一次的数字 III
只出现一次的数字III
来上点难度吧
思路：
如果是一个数字只出现一次就非常简单，但是有两个数字，当然我们可以用hash直接计数就行，简简单单
但是这题要求不开额外空间，那只能用位运算了，但是有两个数字，怎么处理呢
我们将整个数组进行按位异或运算之后，剩下的就是两个唯一的数字的异或了，相同为0，不同为1，我们可以取二进制最右侧的1，按照这一位不同来对数组里面的数字进行分组，这样就分成了两个不同的组，一组是这一位的数字为0，一组是为1，分组按位异或一遍之后，就得到了两个只出现一次的数字
如果实在不理解，可以那一组数据试验一下的
class Solution
{
public:
vector<int> singleNumber(vector<int>& nums)
{
int cur = 0;
for(auto i : nums)
cur ^= i; //这里的longlong是防止越界
int cut = cur & (-(long long)cur);// 二进制最右侧的一个 1
int x = 0, y = 0;
for(auto i : nums)
{
if((i & cut) == cut) // 分组按位 异或
x ^= i;
else
y ^= i;
}
return {x, y};
}
};
判断字符是否唯一
判断字符是否唯一
思路：
一眼hash秒了，但是如果不用额外的数据结构，会很加分，我想加点分
想到每一个整型，会有四个字节，32个比特位，我们可以直接把32个比特位做hash，这样就储存在一个整型当中了
也就是——位图的思想
看我来操作操作吧
class Solution
{
public:
bool isUnique(string astr)
{
int ans = 0;
for(auto i : astr)
{
int x = i - 'a';
if((ans >> x) & 1) // 判断ans二进制的 x位 是否被占据过
return false;
ans = ans | ( 1 << x); // 把ans二进制的 x位修改为 1 ---占据
}
return true;
}
};
总结
核心概念：
位运算直接操作二进制位，包含与（&）、或（|）、异或（^）、非（~）及位移（<<、>>）。其核心在于位级控制，如提取特定位、消除重复项（异或消消乐）、快速统计（n & (n-1)消去最右1）等
常见应用：
去重与判重：异或消去偶数次重复数，位图判字符唯一性
高效计算：左移/右移实现乘除2的幂次，统计1的个数优化算法复杂度
分组处理：通过最右1的差异分离数据（如找出两个唯一数）
注意事项:
符号位：右移时注意算术（补符号位）与逻辑（补0）的区别
溢出风险：左移可能导致数据溢出，需结合数据类型范围判断
今天的内容就到这里啦，不要走开，小编持续更新中~~~
