目录
前言
一.常见的小问题
1.给定一个数n,确定它的二进制表示中的第x位是0还是1
2.给定一个数n，将它的二进制表示中的第x位修改成1
3.给定一个数n，将它的二进制表示中的第x位修改成0
4.给定一个数n，提取它的二进制表示中最右侧的1（即将其它位置位0）
5.给定一个数n，去掉它的二进制表示中最右侧的1
6.异或运算的规则
二.典型例题
前言
位运算是一类常考的题型，关于位运算的操作符有以下几种:
按位取反（~）
左移操作符（<<）
右移操作符（>>）
按位与（&）
按位或 （|）
按位异或（^）
重点要区分&，|和^这几个操作符，按位与是有0则0，按位或是有1则1
按位异或相同为0，相异为1。也可以记成“无进位相加”，例如1+1=2， 因为是二进制所以变成0，但是不进位。
接下来介绍怎么利用这些操作符来解决常见的问题
一.常见的小问题
1.给定一个数n,确定它的二进制表示中的第x位是0还是1
首先声明，默认最低位是第0位。
方法：将n右移x位，与1做按位与操作，若结果为1，则n的第x位是1，若结果是0，则第x位是0
说明：右移操作是为了将第x位移到最低位，方便与1的最低位按位与，而1的其它位全是0，有0则0，故其它位的结果肯定是0，而最低位的结果则取决于x位是0还是1
代码操作：(n >> x) & 1
2.给定一个数n，将它的二进制表示中的第x位修改成1
方法：将1左移x位，再与n按位或
说明：将1左移x位是为了对n的第x位进行“定向打击”，1的第x位是1，其余位是0。按位或的特点是有1则1，故结果的第x位肯定是1，其它位取决于n的其它位是0还是1,和原来相比不会变化
代码操作：n = (1 << x) | n
3.给定一个数n，将它的二进制表示中的第x位修改成0
方法：将1左移x位，按位取反，再与n按位与
说明：按位与的特点是有0则0，故结果的第x位肯定是0，其它位取决于n的其它位是0还是1，和原来相比不会发生变化
代码操作：n = (~(1 >> x) ) & n
4.给定一个数n，提取它的二进制表示中最右侧的1（即将其它位置位0）
方法：n & -n
说明：由n向-n转变，先将n按位取反，然后加1，这样使得n最右侧的1，左边区域全变成相反，右边区域全变成0，而按位与的特点是有0则0，故只有最右侧的1异或的结果是1，其余全是0。
5.给定一个数n，去掉它的二进制表示中最右侧的1
方法：n & (n - 1)
说明：由n到n-1，最右侧1的左边区域不变，右边区域（包括1）全部变成相反，按位与的特点是有0则0，故最右侧的1肯定会变成0，其余位不变
6.异或运算的规则
a ^ 0 = a
a ^ a = 0
a ^ b ^ c = a ^ c ^ b
二.典型例题
接下来有几道例题，大家可以先尝试做一做，答案放在下面了
位1的个数
class Solution {
public:
int hammingWeight(uint32_t n)
{
int ret = 0;
for (int i = 0; i <= 31; i++)
{
if (((n >> i) & 1) == 1)
{
ret++;
}
}
return ret;
}
};
比特位计数
class Solution {
public:
vector<int> countBits(int n)
{
//x&(x-1)将x的最右侧的1变成0
vector<int> v(n + 1);
for (int i = 0; i <= n; i++)
{
int x = i;
int count = 0;
while (x)
{
count++;
x = x & (x - 1);
}
v[i] = count;
}
return v;
}
};
汉明距离
class Solution {
public:
int hammingDistance(int x, int y)
{
int n = x ^ y;
//统计有多少个1
int ret = 0;
while (n)
{
ret++;
n = n & (n - 1);
}
return ret;
}
};
只出现一次的数字
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for (int i = 0; i < nums.size(); i++)
{
ret ^= nums[i];
}
return ret;
}
};只出现一次的数字iii
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
//目标：将两个单身狗分开，相同的数不拆散，再将两组分别异或
//方法：根据两个单身狗任意一个不同的比特位来进行分组
int n = 0;
for (auto e : nums)
{
n ^= e;
}
//找到比特位是1的位置--两个单身狗这一位不同
int pos = 0;
for (int i = 0; i <= 31; i++)
{
if (((n >> i) & 1) == 1)
{
pos = i;
break;
}
}
//根据这一位置的值将所有数分成两组异或
int ret1 = 0, ret2 = 0;
for (auto e : nums)
{
if (((e >> pos) & 1) == 0)
{
ret1 ^= e;
}
else
{
ret2 ^= e;
}
}
return {ret1, ret2};//隐式类型转换
}
};
