1.基础位运算
<< &:有0就是0
>> |:有1就是1
~ ^:相同为0,相异为1 无进位相加(进位时不进位)
eg:下面分别对应& | ^(的两种)
2.给一个数,确定它的二进制表示中的第x位是0还是1
规定:下标的对应是从右向左从0开始的
找到x位是什么,通过&操作,&1(会和其&的数对应,例如1&1=1,0&0=0),将x位向前移动到位置,完整的操作就是(n>>x)&1
3.将一个数n的二进制表示的第x位改成1
找到x位是什么,通过|操作,|1(会和其|的数相反,例如0|1=1,0|0=0),其他位上|0在要变成1的位置|1就可以,n|=(1<<x) 即n=n|(1<<x)
4.将一个数n的二进制的第x位修改成0
找到x位是什么,通过&操作,&1(会和其|的数相同,例如1&0=0),其他位上&1,不变,
n&=~(1<<x) 即n=n&~(1<<x)
5.位图的思想
位图的思想很象哈希表,节省空间,用「二进制位」这个最小的存储单元，直接映射「元素值」和「元素存在状态」，以极致的空间效率实现快速的存在性判断 / 去重
6.提取一个数(n)二进制表示最右侧的1
n变成-n,就是将第一个1的左边区域全部取反右边不变,这样左边就一定有0,通过&操作
n&-n
7.干掉一个数(n)二进制表示中最右侧的1
n&(n-1)因为n-1会向最右侧的1去借位变成0,通过&来消除1
8.运算符的优先级
能加括号就加括号
9.异或(^)运算的规律
1.a^0=a
2.a^a=0(消消乐)
3.a^b^c=a^(b^c)
10.练习题
题目一:
代码:
class Solution {
public:
int hammingWeight(uint32_t n) {
int count=0;
for(int i=0;i<32;i++)
{
if((n>>i)&1==1)count++;//判断第x位是0还是1
}
return count;
}
};
题目二:
代码:
class Solution {
public:
vector<int> countBits(int n) {
vector<int>arr(n+1);
for(int i=0;i<=n;i++)//第几个数
{
int cur=i;
for(int j=0;j<32;j++)//每个数的第几位
{
if(((cur>>j)&1)==1)arr[i]++;
}
}
return arr;
}
};
题目三:
代码:
class Solution {
public:
int hammingDistance(int x, int y) {
int n=x^y;//同为0异为1,变成有多少个1
int count=0;
for(int i=0;i<32;i++)
{
if(((n>>i)&1)==1)count++;
}
return count;
}
};
题目四:
利用消消乐,重复的会消除,a^a=0.a^0=a
eg:4^1^2^1^2=4
代码:
class Solution {
public:
int singleNumber(vector<int>& nums) {
int target=0;
int n=nums.size();
for(int i=0;i<n;i++)
{
target=target^nums[i];
}
return target;
}
};
题目五:
代码:
目录
1.基础位运算
eg:下面分别对应& | ^(的两种)
2.给一个数,确定它的二进制表示中的第x位是0还是1
3.将一个数n的二进制表示的第x位改成1
4.将一个数n的二进制的第x位修改成0
5.位图的思想
6.提取一个数(n)二进制表示最右侧的1
7.干掉一个数(n)二进制表示中最右侧的1
8.运算符的优先级
9.异或(^)运算的规律
10.练习题
题目一:
代码:
题目二:
代码:
题目三:
代码:
题目四:
代码:
题目五:
代码:
