【位运算】算法实战

妖狐艹你老母 2023-10-14 23:57 91阅读 0赞

#### 文章目录 ####

*  一、算法原理
 *   *  常见的位运算总结
 *  二、算法实战
 *   *  1. leetcode面试题01.01. 判断字符是否唯一
     *  2. leetcode268 丢失的数字
     *  3. leetcode371 两整数之和
     *  4. leetcode004 只出现一次的数字II
     *  5. leetcode面试题17.19. 消失的两个数字
 *  三、总结

--------------------

## 一、算法原理 ##

计算机中的数据都以二进制形式存储和处理，位运算直接对二进制位进行操作。常见的位运算符包括与（`&`）、或（`|`）、异或（`^`）、取反（`~`）和左移（`<<`）、右移（`>>`）等。

![在这里插入图片描述][78b8b2928baf490691d59e8cec582620.png]

--------------------

### 常见的位运算总结 ###

1.  `基础位运算`  
    ![在这里插入图片描述][7bb3c5cc76fa4c018538c88d305dc6ef.png]
2.  `给一个数n，确定它的二进制表示中第x位是0还是1`  
    ![在这里插入图片描述][84de44b9a7a743b194de629307f43008.png]
3.  `将一个数n的二进制表示的第x位修改成1`  
    ![在这里插入图片描述][33819eeef4fb432da0f1b3ac2930da9d.png]
4.  `将一个数n的二进制表示的第x位修改成0`  
    ![在这里插入图片描述][60e8064e8333437da7b539b233df5ed1.png]
5.  `位图的思想`  
    ![在这里插入图片描述][896197b1c1824d9ab418d4c6ae947858.png]
6.  `提取一个数(n)二进制表示中最右侧的1`  
    ![在这里插入图片描述][da15d7e5af15461394673c202235fc74.png]
7.  `干掉一个数(n)二进制表示中最右侧的1`  
    ![在这里插入图片描述][42c7b6bc75094467a258bf3ad83d7454.png]
8.  `位运算的优先级：` **能加括号就加括号**
9.  `异或(^)运算的运算律`  
    ![在这里插入图片描述][bac8b04f52214c889ba9fd37cda36323.png]

--------------------

## 二、算法实战 ##

### 1. leetcode面试题01.01. 判断字符是否唯一 ###

> ![在这里插入图片描述][da77254167fb461e9f8732044241d31a.png]  
> [判断字符是否唯一][Link 1]

**解题思路：位图的思想**

这道题目我们可以使用位图的思想来解决，因为题目告诉我们字符串中只有小写字母，所以我们只需要一个int类型的整数来充当位图的32个bit位即可。

首先，将位图的所有bit位置为零，默认字符串中的字符都未在位图中出现过。然后遍历整个字符串，检测该字符是否在位图中出现过，如果当前字符未在位图中出现过，说明当前字符是第一次出现，此时我们将其在位图中的位置（`当前字符-'a'`）置为1即可，然后接着向后遍历字符串，如果该字符再次出现，我们就可以从位图中检测到该字符已经在出现过了。直接返回`false`即可，否则继续向后遍历字符串，如果遍历所有字符后发现都只出现一次，则说明该字符串符合题意。

**代码实现：**

class Solution {
        
    public:
        bool isUnique(string astr) {
        
            int num = 0;
            
            for(int i = 0; i < astr.size(); i++)
            {
        
                int index = astr[i] - 'a';
                if(((num>>index) & 1) == 1)
                    return false;
                else
                    num |= 1 << index;
            }
            return true;
        }
    };

--------------------

### 2. leetcode268 丢失的数字 ###

> ![在这里插入图片描述][b2ab1452ec604337b0233d7aa05a27a1.png]  
> [丢失的数字][Link 2]

**解题思路：异或运算**

因为题目中告诉我们数组中【1~n】丢失了一个数字，所以我们可以先将数组中的数字 `^` 起来，然后在将这个 `^` 的结果与【1~n】中所有的数字异或，因为按位 `^` 运算满足交换律和结合律，所以按位 ^ 的结果中，丢失的数字出现了一次，其余的数字都出现了两次，将这一堆数字异或起来，结果即为丢失的数字。

![在这里插入图片描述][3ff8d1418e3e4006a14108c4b58692a9.png]

**代码实现：**

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

--------------------

### 3. leetcode371 两整数之和 ###

> ![在这里插入图片描述][b7df8aab56c8443883d485279208a489.png]  
> [两整数之和][Link 3]

**解题思路：异或运算-无进位相加**

因为题目要求我们不能使用运算符`+`和`-`来计算两整数之和，因此我们可以将整数 a 和 b 的和，拆分为 a 和 b 的`无进位相加结果`与`进位结果的和`，**无进位相加结果** 我们可以使用两整数`^`来实现，**进位结果**我们可以使用`(a & b) << 1`来实现。下面我们来举一个例子：

![在这里插入图片描述][3517c3c1db1f42ebba829cde314f14d0.png]

每次将`无进位相加结果`与`进位结果的和`分别赋予a和b，循环此过程，直到进位为 0。最终a就是我们所要求的结果。当我们赋给无符号类型一个超出它表示范围的值时，结果是初始值对无符号类型表示数值总数取模的余数。因此，我们可以使用无符号类型来防止溢出。

**代码实现：**

lass Solution {
        
    public:
        int getSum(int a, int b) {
        
            while(b != 0)
            {
        
                int x = a ^ b; // 先算出无进位相加的结果
                unsigned int carry = (a & b) << 1; // 算出进位
                a = x;
                b = carry;
            }
            return a;
        }
    };

--------------------

### 4. leetcode004 只出现一次的数字II ###

> ![66a8b8dcb59440a2abfb245cfd58e1f2.png][]  
> [只出现一次的数字II][II]

**解题思路：**

数组中的每个元素的每一个二进制位不是1就是0，而题目中又告诉我们只有一个元素出现一次，其余元素都出现了三次，所以对于数组中的每一个元素 `x`，我们使用位运算 `(x >> i) & 1` 得到 x 的第 i 个二进制位，并将它们相加再对 3 取余，得到的结果一定为 0 或 1，即为答案的第 i 个二进制位。

所以，答案的第 i 个二进制位就是数组中所有元素的第 i 个二进制位之和除以 3 的余数。可以先初始化一个`ret = 0`，然后根据余数的值来判断该数对应的二进制位应该置为0还是1，如果余数为1，我们则需要手动将该位置置为1，`ret |= (1 << i)`，否则则不需要处理。

**代码实现：**

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

--------------------

### 5. leetcode面试题17.19. 消失的两个数字 ###

> ![在这里插入图片描述][32ec7d1f6275403686554be226f2a9aa.png]  
> [消失的两个数字][Link 4]

**解题思路：**

这道题目其实我们可以用力扣的第260题 [**只出现一次的数字III**][III] 的思想来做，具体解决方式如下：

因为数组中包含从 1 到 N 所有的整数，但其中缺了两个数字，现在数组的长度为n。所以数组中原本应该包含的数字是【1，n + 2】。我们可以将原来数组中的数字和【1，n + 2】，组合到一起，现在我们就可以将问题转化一下：求数组中只出现一次的两个数字。

解决这个问题我们可以分为两步：`整体异或`和`分组异或`。整体异或：将题目给出的数组中的所有数字和【1，n + 2】中所包含的数字全部异或起来，得到的结果就是只出现一次的两个数字的异或结果：`a^b`。接下来我们需要提取出`该数字二进制表示中最低位的1`。假设该位置为第k位，我们就可以把 所有数中的元素`（题目中给出的数字和【1，n + 2】的数字）`分成两类，其中一类包含所有二进制表示的第 k 位为 0 的数，另一类包含所有二进制表示的第 k 位为 1 的数。

*  对于任意一个在 所有元素中 出现两次的元素，该元素的两次出现会被包含在同一类中；
 *  对于任意一个在所有元素中只出现了一次的元素，即 x1 和 x2， 他们会被包含在不同的类中。

因此，我们将这两类元素分别异或起来，就可以得到不同的两个结果，一个结果是x1，另一个结果是x2，这两个数字则是只出现一次的两个数字，即本题中我们需要寻找的两个消失的数字。

**代码实现：**

class Solution {
        
    public:
        vector<int> missingTwo(vector<int>& nums) {
        
            int ret = 0;
            for(int i = 1; i <= nums.size()+2; i++)
                ret ^= i;
            for(auto e : nums) ret ^= e;
            int lowbit = ret & -ret; // 找出最后一个不同的比特位
            int ret1 = 0, ret2 = 0;
            for(int i = 1; i <= nums.size()+2; i++){
         // 分组异或
                if(lowbit & i) ret1 ^= i;
                else ret2 ^= i;
            }
            for(auto e : nums){
        
                if(lowbit & e) ret1 ^= e;
                else ret2 ^= e;
            }
            return {
        ret1, ret2};
        }
    };

--------------------

## 三、总结 ##

位运算可以直接操控数字的二进制位，节约内存，使程序运行更快，可靠性高。在算法中使用位运算可以大大降低算法的时间复杂度和空间复杂度，恰当的位运算使用也能使程序变得更加简洁和优美。

[78b8b2928baf490691d59e8cec582620.png]: https://img-blog.csdnimg.cn/78b8b2928baf490691d59e8cec582620.png
[7bb3c5cc76fa4c018538c88d305dc6ef.png]: https://img-blog.csdnimg.cn/7bb3c5cc76fa4c018538c88d305dc6ef.png
[84de44b9a7a743b194de629307f43008.png]: https://img-blog.csdnimg.cn/84de44b9a7a743b194de629307f43008.png
[33819eeef4fb432da0f1b3ac2930da9d.png]: https://img-blog.csdnimg.cn/33819eeef4fb432da0f1b3ac2930da9d.png
[60e8064e8333437da7b539b233df5ed1.png]: https://img-blog.csdnimg.cn/60e8064e8333437da7b539b233df5ed1.png
[896197b1c1824d9ab418d4c6ae947858.png]: https://img-blog.csdnimg.cn/896197b1c1824d9ab418d4c6ae947858.png
[da15d7e5af15461394673c202235fc74.png]: https://img-blog.csdnimg.cn/da15d7e5af15461394673c202235fc74.png
[42c7b6bc75094467a258bf3ad83d7454.png]: https://img-blog.csdnimg.cn/42c7b6bc75094467a258bf3ad83d7454.png
[bac8b04f52214c889ba9fd37cda36323.png]: https://img-blog.csdnimg.cn/bac8b04f52214c889ba9fd37cda36323.png
[da77254167fb461e9f8732044241d31a.png]: https://img-blog.csdnimg.cn/da77254167fb461e9f8732044241d31a.png
[Link 1]: https://leetcode.cn/problems/is-unique-lcci/
[b2ab1452ec604337b0233d7aa05a27a1.png]: https://img-blog.csdnimg.cn/b2ab1452ec604337b0233d7aa05a27a1.png
[Link 2]: https://leetcode.cn/problems/missing-number/
[3ff8d1418e3e4006a14108c4b58692a9.png]: https://img-blog.csdnimg.cn/3ff8d1418e3e4006a14108c4b58692a9.png
[b7df8aab56c8443883d485279208a489.png]: https://img-blog.csdnimg.cn/b7df8aab56c8443883d485279208a489.png
[Link 3]: https://leetcode.cn/problems/sum-of-two-integers/
[3517c3c1db1f42ebba829cde314f14d0.png]: https://img-blog.csdnimg.cn/3517c3c1db1f42ebba829cde314f14d0.png
[66a8b8dcb59440a2abfb245cfd58e1f2.png]: https://img-blog.csdnimg.cn/66a8b8dcb59440a2abfb245cfd58e1f2.png
[II]: https://leetcode.cn/problems/WGki4K/
[32ec7d1f6275403686554be226f2a9aa.png]: https://img-blog.csdnimg.cn/32ec7d1f6275403686554be226f2a9aa.png
[Link 4]: https://leetcode.cn/problems/missing-two-lcci/
[III]: https://leetcode.cn/problems/single-number-iii/