【优选算法】位运算

在这里插入图片描述

常见位运算总结
- 1、基础位运算
- 2、给一个数n，确定它的二进制位的第x位上是0还是1
- 3、将一个数n的二进制位的第x位改成1
- 4、将一个数n的二进制位的第x位改成0
- 5、位图的思想
- 6、提取一个数n的二进制位中最右侧的1
- 7、将一个数n的二进制位中最右侧的1变为0
- 8、位运算的优先级
- 9、异或（^）运算的运算律
一、[位1的个数](https://leetcode.cn/problems/number-of-1-bits/description/)
二、[比特位计数](https://leetcode.cn/problems/counting-bits/description/)
三、[汉明距离](https://leetcode.cn/problems/hamming-distance/description/)
四、[只出现一次的数字](https://leetcode.cn/problems/single-number/description/)
五、[只出现一次的数字 III](https://leetcode.cn/problems/single-number-iii/description/)
六、[判定字符是否唯一](https://leetcode.cn/problems/is-unique-lcci/description/)
七、[丢失的数字](https://leetcode.cn/problems/missing-number/description/)
八、[两整数之和](https://leetcode.cn/problems/sum-of-two-integers/description/)
九、[只出现一次的数字 II](https://leetcode.cn/problems/single-number-ii/description/)
十、[消失的两个数字](https://leetcode.cn/problems/missing-two-lcci/description/)
结尾

常见位运算总结

1、基础位运算

左移操作符 >> 、右移操作符 << 、按位取反 ~ ，这三个操作符我不做讲解。

接下来讲解3个操作符以及它使用方法对应的记忆方法

按位与：& 有0就是0
按位或：| 有1就是1
按位异或：^ 相同为0相异为1/无进位相加
在这里插入图片描述

2、给一个数n，确定它的二进制位的第x位上是0还是1

首先我们认为一个整数有32位、它最低位是0位，它的最高位为31位，那么就可以使用(n >> x)&1的操作来判断这个数的第x位是0还是1，因为n>>x能够将数字n上的第x位移动到第0位，1除了第0位上是1，其他位都是0，异或后结果只会出现第0位上为0/1其他位为0的情况，所以结果是0则数n二进制位的第x位上是0，是1则数n二进制位的第x位上是1。

在这里插入图片描述

3、将一个数n的二进制位的第x位改成1

首先我们认为一个整数有32位、它最低位是0位，它的最高位为31位，那么就可以使用n|=(1<<x)的操作将数字n的二进制位的第x位改成1。1<<x能够将1的第x位变为1，异或后无论n上的第x位上是0是1都会变为1。

在这里插入图片描述

4、将一个数n的二进制位的第x位改成0

首先我们认为一个整数有32位、它最低位是0位，它的最高位为31位，那么就可以使用n&=(~(1<<x))的操作将数字n的二进制位的第x位改成0。1<<x能够将1的第x位变为1，按位与后除了第x位上为0其他位上都为1，再与n按位与后，n中的第x位都会被0变为1，其他位都是与1按位与，则都不变。

在这里插入图片描述

5、位图的思想

位图的本质就是哈希表，我们在之前就学习过哈希表，哈希表很多情况下是数组，假设是一个int类型的数组，可以通过在数组中存储某些数组来表示某些意义，现在我们可以通过变量的比特位来表示某些信息，假设一个int类型的变量，一个int类型的变量有32位，其中的每一位存储的0/1都可以分别表示某种信息。

在这里插入图片描述

6、提取一个数n的二进制位中最右侧的1

首先我们认为一个整数有32位、它最低位是0位，它的最高位为31位，那么就可以使用n&-n的操作提取一个数n的二进制位中最右侧的1。这里的-n也就~n+1，-n能够将最右侧1的左侧所有二进制数字变成相反的，+1能将右侧所有二进制数字变为0，按位与后就只剩下最右侧的1。
在这里插入图片描述

7、将一个数n的二进制位中最右侧的1变为0

首先我们认为一个整数有32位、它最低位是0位，它的最高位为31位，那么就可以使用n&(n-1)的操作将一个数n的二进制位中最右侧的1变为0。-1能够将数字n最右侧1的左侧二进制数字变成相反的（包括它本身），按位与后右侧不变，左侧都不同则都变为0，就可将最右侧的1变为1。

在这里插入图片描述

8、位运算的优先级

位运算的优先级大家可以在其他文章中查看，这里建议大家能加括号就加括号。

9、异或（^）运算的运算律

a^0 = a
a^a = 0
a^b^c = a^(b^c)

一、位1的个数

题目描述：

思路讲解：
在上面常见位运算总结中讲到了如何将一个数的二进制位中最右侧的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;
    }
};

九、只出现一次的数字 II

题目描述：

思路讲解：
题目中讲到了有一个数只出现过一次，其他的数都出现了三次，那么将所有数的二进制位罗列出来，那么将所有数对应每一位相加起来会出现两种情况：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};
    }
};