【优选算法】位运算

题目描述：

思路讲解：
在上面常见位运算总结中讲到了如何将一个数的二进制位中最右侧的1修改为0，我们只需要重复这个操作，并记录这个操作的次数，当这个数变为0以后，操作次数就是这个数二进制位中1的个数。

编写代码：

class Solution {
public:
    int hammingWeight(int n) {
        int count = 0;
        while(n > 0)
        {
            // 去掉最右侧的一
            n &= (n - 1);
            count++;
        }
        return count;
    }
};

题目描述：

思路讲解：
这题的思路与上一题的思路一致，只是上一题是获取一个数的二进制位中有多少个1，而本题是获取n个数的二进制位中有多少个1，本质上是一样的，这里不做过多讲解。

编写代码：

class Solution {
public:
    int hammingWeight(int n) {
        int count = 0;
        while(n > 0)
        {
            // 去掉最右侧的1
            n &= (n - 1);
            count++;
        }
        return count;
    }

    vector<int> countBits(int n) {
        vector<int> ans;
        for(int i = 0 ; i <= n ;i++)
            ans.push_back(hammingWeight(i));

        return ans;
    }
};

题目描述：

思路讲解：
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。所以我们只需要将两个数每个对应的二进制位上的数字获取并对比，记录
二进制位不同的位置的数目即可，我们在上面讲到过可以使用(n >> x)&1的操作获取一个数的第x位上的二进制是0还是1。

编写代码：

class Solution {
public:
    int hammingDistance(int x, int y) {
        int count = 0;
        for(int i = 0 ; i <= 31 ;i++)
        {
            if(((x >> i) & 1) != (((y >> i) & 1)))
                count++;
        }

        return count;
    }
};

题目描述：

思路讲解：
在上面异或运算的运算律中我们讲到过a^a=0和a^0=a，本题中除了一个数只出现过一次，其他数都出现过两次，将所有的数异或在一起，出现过两次的数全部异或到一起就是0，出现过一次的数与0异或就是我们需要的结果。

编写代码：

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

题目描述：

思路讲解：

在上面异或运算的运算律中我们讲到过a^a=0和a^0=a，本题中除了两个数只出现过一次，其他数都出现过两次，将所有的数异或在一起，就是两个只出现一次的数相异或的结果。两个数异或的结果的二进制位上有1就代表着两个数在当前位上一定是不同的，我们可以将两数异或结果上某一个1的位置标记，记为pos，将所以pos位上为1的数全部异或在一起，就能够得到其中一个答案，再将两数异或的结果与刚刚得到的一个答案异或，就能够得到另一个答案。

编写代码：

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> v;
        v.resize(2 , 0);
        int xor1 = 0;
        // 将所有数异或，可以得到需要的两个数的异或
        for(auto x : nums)
        {
            xor1 ^= x;
        }
        // 我们知道，异或后的二进制位上的 1，
        // 必定是两个数对应二进制位上的一个，且只有一个 
        // 那我们只需要将某一位上的1的位置记录下来
        // 并且将数组遍历一遍，将这个位置上为1的数全部异或就能得到第一个数
        // 再将第一步中两个数的异或值与第一个数异或就能得到第二个数
        int pos = 0;
        for(int i = 0 ; i < 32 ;i++)
        {
            if( ((xor1 >> i) & 1 ) == 1 )
            {
                pos = i;
                break;
            }

        }
        for(int i = 0 ; i < nums.size() ; i++)
        {
            if(((nums[i] >> pos) & 1) == 1)
            {
                v[0] ^= nums[i];
            }
        }
        v[1] = xor1 ^ v[0];

        return v;
    }
};

题目描述：

思路讲解：
本题最简单的思路就是建立一个数组，将每个字母出现的次数记录下来，当有一个字符出现两次就返回false，但是这样需要花费4*26个字节，而使用位图则只需要4个字节，一个int类型的变量就有32个比特位，将26位小写字母对应到其中的32个比特位中，当遍历到一个字符的时候，就查看对应比特位上是0/1，如果是1就返回false，是0就继续遍历字符串。

本题还有一个优化方案就是雀巢原理，小写字母一共有26个，当字符串的长度超过26时，说明一定有一个字母是出现过两次的。

编写代码：

class Solution {
public:
    bool isUnique(string astr) {
        // 优化 雀巢原理
        if(astr.size() > 26)
            return false;
        
        // 因为小写字母只有26个
        // 而int中有32个比特位
        // 那么这里使用位图来解决问题
        int tmp = 0;
        for(auto e : astr)
        {
            if(((tmp >> (e - 'a')) & 1) == 1)
                return false;
            else
                tmp |= (1 << (e - 'a'));
        }
        return true;
    }
};

题目描述：

思路讲解：
本题最简单的思路就是建立一个大小为n的数组arr，遍历nums并在arr中标记，当nums遍历完后，再遍历arr查看哪个数字没有被标记就是答案，但是这个方法的缺点就是需要使用额外的空间复杂度。

还有可以使用高斯求和，得到0到n之间的数相加后的结果，减去nums中数组中所有数，就是本题的答案。

还可以使用位运算，上课讲到过a^a=0和a^0=a，将0到n中所有的数异或，再与nums数组中所有的数异或，就能够得到本题的答案。使用位运算可以将本题转化为上面只出现一次的数字的那道题。

编写代码：

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

题目描述：

思路讲解：

我们在记忆按位异或使用的时候，按位异或就是无进位相加，那么这里只缺少进位，进位我们可以通过按位与获得，但是需要注意的是获得的进位需要向左侧移动一位。我们将按位异或得到的无进位相加的结果记为tmp1，将按位与获得的进位记为tmp2，持续将tmp1与tmp2按位异或和按位与得到无进位相加与进位，只要当进位tmp2为0时，tmp1就是结果。

编写代码：

class Solution {
public:
    int getSum(int a, int b) {
        int tmp1 = (a & b)<<1;  // 两数按位与后向右移动一位，代表着进位
        int ans = a ^ b;        // 两数异或代表无进位相加
        while(tmp1 != 0)
        {
            int tmp2 = tmp1;    // 记录tmp1
            tmp1 = (tmp1 & ans)<<1; 
            ans ^= tmp2;
        }
        return ans;
    }
};

题目描述：

思路讲解：
题目中讲到了有一个数只出现过一次，其他的数都出现了三次，那么将所有数的二进制位罗列出来，那么将所有数对应每一位相加起来会出现两种情况：3n与3n+1，通过将3n与3n+1进行%3，就能得到0和1的结果，这里得到的1就是只出现过一次的数字对应比特位上的1，只需要将这些1组合到对应的比特位上，得到的数字就是结果。

同理给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现n次，都可以使用这个方法。

编写代码：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int sum = 0;       // 记录所有数字某个二进制位的和
        int num = 0;       // 记录答案
        for(int i = 0 ; i < 32 ; i++)
        {
            for(int ch : nums)
            {
                // 将第i个位置上的二进制数字取出来相加
                sum += ((ch >> i)&1);
            }
            if(sum % 3 != 0)
            {
                num |= (1 << i);
            }
            sum = 0;
        }
        return num;
    }
};

题目描述：

思路讲解：
本道题就是上面只出现一次的数字III和丢失的数字两道题的结合，只需要找到丢失两个数的按位异或的结果就可以使用只出现一次的数字III中的思路，分别得到两个数是哪两个数，这里就不做讲解。

编写代码：

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int tmp = 0;
        int numsLen = nums.size();
        for(int i = 1 ; i <= numsLen + 2; i++)
            tmp ^= i;
        
        for(auto e : nums)
            tmp ^= e;
        
        int lowbit = (tmp & -tmp);
        int ans1 = tmp;

        for(int i = 1 ; i <= numsLen + 2; i++)
            if((lowbit & i) == lowbit)
                ans1 ^= i;

        for(auto e : nums)
            if((lowbit & e) == lowbit)
                ans1 ^= e; 
            
        int ans2 = (tmp ^ ans1);

        return {ans1,ans2};
    }
};