一、常见的位运算总结（重点！）

1、关于位运算的符号

2、（判断）给一个数字n，确定它的二进制表示中的第X位，是1还是0？

方法：（n>>x）&1

3、（修改）如何把一个二进制的数字的第x位修改为1？

方法：n|=(1<<x)

4、（修改）如何将一个数的二进制的第x位修改为0？

方法：n&= (~(1<<x))

5、（lowbit）提取二进制中最右侧的1

方法：n&(-n)

6、去除二进制中最右侧的1

方法：n&(n-1)

7、位运算的优先级？能加() 就加()

8、异或(^)的运算规律

1. a^0=a
2. a^a=0
3. a^b ^ c=a^ (b^c)交换律

二、判定字符是否唯一

1、题目解析

2、算法原理

3、代码

class Solution 
{
public:bool isUnique(string astr) {// 利用鸽巢原理，如果给的字符串数量大于26，必有重复if(astr.size()>26) return false;int bitmap=0;// 就是刚开始默认32个0for(auto ch:astr){// 把每个字符转化为他的ASC||码值int i=ch-'a';// 先判断该位置是否已经存在（1：存在，0：不存在）if((bitmap>>i)&1==1) return false;// 此时就可以 把第一次出现的进入，位置标为1bitmap|=1<<i;}return true;}
};

三、丢失的数字

1、题目解析

2、算法原理

利用按位异或的规律：
①：a^ 0=a
②：a^ a=0

实际上就是：单身狗问题！

3、代码

class Solution 
{
public:int missingNumber(vector<int>& nums) {int ret=0;// 先把所给的数组 里面的数据异或（^）在一起for(auto n:nums) ret^=n;// 这里的ret保留了之前异或的，再把标准数组异或一下，就相当于所有都异或在一起了for(int i=0;i<nums.size()+1;i++) ret^=i; return ret;}
};

四、两整数之和

1、题目解析

2、算法原理

3、代码

class Solution {
public:int getSum(int a, int b) {while(b!=0){int x=a^b;// 先计算出无进位 相加的结果unsigned int y= (unsigned int) (a&b)<<1;// 算出进位a=x;b=y;// 重复上面的步骤}return a;}
};

五、只出现一次的数字||

1、题目解析

2、算法原理

3、代码

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==1) sum++;}if(sum%3==1)ret|=1<<i;// 把第i位修改为1}return ret;}
};

六、消失的两个数字

1、题目解析

2、算法原理

3、代码

class Solution 
{
public:vector<int> missingTwo(vector<int>& nums) {// 假设a,b是消失的数字// 1、将所有的数异或到一起int tmp=0;for(int  x:nums){tmp^=x;}for(int i=1;i<=nums.size()+2;i++){tmp^=i;}// 此时的tmp就是a^b// 2、找出a、b比特位不同的那一位int diff=0;// 标记比特位不同的几个位置for(int i=0;i<32;i++){if((tmp>>i)&1==1)break;elsediff++;}// 3、根据diff位的不同，对[1~N]、nums分类异或int a=0,b=0;// b存放比特位为1，a存放0for(int i=1;i<=nums.size()+2;i++){if((i>>diff)&1==1) b^=i;else a^=i;}for(int x:nums){if((x>>diff)&1==1) b^=x;else a^=x;}return {a,b};}
};