优选算法第五讲：位运算模块

1.常见的位运算总结

2.判断字符是否唯一

链接: link

class Solution {
public:bool isUnique(string astr) {if(astr.size() > 26) return false;int hash = 0;for(auto e : astr){ //找出下标int i = e-'a';if(hash&(1<<i)) return false;//如果对应位置为1，证明前面已经存在了该字符，返回falseelse hash |= 1<<i;//将字符存储到int变量中}return true;}
};  

3.丢失的数字

链接: link

class Solution {
public:int missingNumber(vector<int>& nums) {int sum = 0;for(auto e : nums) sum ^= e;for(int i = 0; i<=nums.size(); i++) sum ^= i;return sum;}
};

4.两整数之和

链接: link

class Solution {
public:int getSum(int a, int b) {while(b){int x = a^b;unsigned int carry = (unsigned int)(a&b)<<1;a = x;b = carry;}return a;}
};

5.只出现一次的数字II

链接: link

class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for(int i = 0; i<32; i++){int sum = 0;for(auto e : nums)if((e>>i)&1 == 1) sum++;// if((e & (1 << i)) == 1)//  sum++;sum %= 3;if(sum == 1)ret |= 1<<i;}return ret;}
};

6.消失的两个数字

链接: link

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {//先将nums中的所有数据进行异或int sum = 0;for(auto e : nums) sum ^= e;//然后再将1-N之内的数据进行异或for(int i = 1; i<=nums.size()+2; i++) sum ^= i;//找出最右边的1int rightone = sum&(-sum);int num1 = 0;for(auto e : nums)if(e & rightone)num1 ^= e;for(int i = 1; i<=nums.size()+2; i++)if(i & rightone)num1 ^= i;int num2 = sum^num1;return {num1, num2};}
};