位运算（算法5）

常见位运算总结

五道位运算入门规律题 

1.位1的个数

link：191. 位1的个数 - 力扣（LeetCode）

key：n &= (n-1))可以消去右1； 

code

class Solution {
public:
    int hammingWeight(int n) {
        int ans = 0;
        while(n)
        {
            ++ans;
            n &= (n-1);
        }
        return ans;
    }
};

2.比特位计数

link：338. 比特位计数 - 力扣（LeetCode）

分奇偶后动态规划

code：

class Solution {
public:
    vector<int> countBits(int n) {
        //分奇偶即可
        vector<int> ans(n+1);
        ans[0] = 0;
        for(int i = 1; i <= n; i++)
        {
            if(i%2==1) ans[i] = ans[i-1] + 1;
            else ans[i] = ans[i>>1];
        }
        return ans;
    }
};

3.汉明距离

link:461. 汉明距离 - 力扣（LeetCode）

code

class Solution {
public:
    int hammingDistance(int x, int y) {
        int ret = x ^ y;
        int ans = 0;
        while(ret)
        {
            ++ans;
            ret &= (ret-1);
        }
        return ans;
    }
};

4.只出现一次的数字I

link:136. 只出现一次的数字 - 力扣（LeetCode）

code

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(const auto& e:nums)
        {
            ans ^= e;
        }
        return ans;
    }
};

5.只出现一次的数字III

link:260. 只出现一次的数字 III - 力扣（LeetCode）

code

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        //只要可以把nums分成两批, 每批只有一个所求答案，就可以转化为《只出现一次的数字》
        //通过ans[x >> ctz & 1] ^= x实现
        int ret = 0;
        for(const auto&e:nums)
        {
            ret^=e;
        }
        vector<int> ans = {0, 0};//={ret, ret};
        int ctz = __builtin_ctz(ret);//对于ret>>ctz&1， ans中两元素肯定不一样
        for(const auto&e:nums)
        {
            ans[(e>>ctz)&1]^=e;
        }
        return ans;
    }
};

1.判定字符是否唯一

link:面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

key:

        位图代替哈希表

code

class Solution {
public:
    int bit = 0;//位图代替hash数组
    bool find(int num)
    {
        return (bit>>num) & 1;
    }
    void bset(int num)
    {
        bit |= (1<<num);
    }
    bool isUnique(string astr) {
        int len = astr.size();
        if(len > 26) return false;
        for(auto &e:astr)
        {
            if(find(e-'a')) return false;
            bset(e-'a');
        }
        return true;
    }
};

2.丢失的数字

link:268. 丢失的数字 - 力扣（LeetCode）

key:

        制造条件，运用异或性质找到单身汉

code

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

3.两整数之和

link:371. 两整数之和 - 力扣（LeetCode）

key:

        利用^计算不进位相加

        利用&计算进位

code

class Solution {
public:
    int getSum(int a, int b) {
        //利用异或运算性质：不进位相加
        //  按位与性质可用来寻找进位
        int x = (a^b);
        int y = (a&b)<<1;
        while(y)
        {
            a = x;
            b = y;
            x = (a^b);
            y = (a&b)<<1;
        }
        return x;
    }
};

4.只出现一次的数字II

link:137. 只出现一次的数字 II - 力扣（LeetCode）

key:

        以bite位为单位看待数字

        以bite位为单位做计算（+/-）操作

code

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // 以比特位为单位看待数字
        int ans = 0; 
        for(int i = 0; i < 32; i++)
        {
            int sum = 0;
            for(const auto& e:nums)//求nums第i的bite位和
            {
                sum+=((e>>i)&1);
            }
            sum %= 3;
            if(sum==1) ans |= (1<<i);
        }
        return ans;
    }
};

5.消失的两个数字

link:面试题 17.19. 消失的两个数字 - 力扣（LeetCode）

key:

        同《只出现一次的数字III》

        __builtin_ctz 加 ans[x >> ctz & 1] ^= x

code

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        vector<int> ans={0, 0};
        int ret = 0;
        
        for(const auto& e:nums)
        {
            ret ^= e;
        }
        for(int i = 1; i <= nums.size()+2; i++)
        {
            ret ^= i;
        }
        int ctz = __builtin_ctz(ret);
        for(int i = 1; i <= nums.size() + 2; i++)
        {
            ans[(i>>ctz)&1] ^= i;
        }
        for(const auto& e:nums)
        {
            ans[e>>ctz&1] ^= e;
        }
        return ans;
    }
};