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

1.常见的位运算总结
2.判断字符是否唯一
3.丢失的数字
4.两整数之和
5.只出现一次的数字II
6.消失的两个数字

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，证明前面已经存在了该字符，返回false
            else 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;

        //找出最右边的1
        int 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};
    }
};