一文详解“位运算“在算法中的应用

找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏： 优选算法专题

目录

位运算的相关介绍（重要） 

136. 只出现一次的数字

191.位1的个数

461. 汉明距离

260. 只出现一次的数字III

面试题01.01.判定字符是否唯一

268.丢失的数字

371.两整数之和

137.只出现一次的数字Ⅱ 

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

位运算的相关介绍（重要） 

我们之前在C语言、Java中都全面的学习了位运算的基本用法。现在我们就可以来看看其在算法中具体是如何操作的。但在此之前得先了解一下"高端的位运算"：

一定要去了解一些高端的写法，不然下面代码的优化，可能一下反应不过来。现在就开始练习： 

136. 只出现一次的数字

题目：

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]
输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：

输入：nums = [1]
输出：1

提示：

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• 除了某个元素只出现一次以外，其余每个元素均出现两次。

思路：相信小伙伴们基本上可以直接把这题秒了，但我们还是从最朴素的解法开始入手。首先，在没学习位运算之前，如果让我们去写的话，肯定是用数组来统计对应元素出现的次数，然后再去遍历找到只出现一次的元素。而后面学习了位运算之后，便可以利用 ^ 操作符的特点（a ^ 0 = a，a ^ a = 0）来找到最终的"单身狗元素"。这里其实就是利用 ^ 操作符 对于奇数次 ^ 一个数字之后，得到的还是这个数字本身，偶数次 ^ 一个数字之后，得到的就是0 来编写代码。

代码实现：（这里只给出位运算的版本）

class Solution {
    public int singleNumber(int[] nums) {
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            ret ^= nums[i];
        }
        return ret;
    }
}

191.位1的个数

题目： 

编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位（setbit 指在某数的二进制表示中值为1 的二进制位）的个数（也被称为汉明重量）。

示例 1：

输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。

示例 2：

输入：n = 128
输出：1
解释：输入的二进制串 10000000 中，共有 1 个设置位。

示例 3：

输入：n = 2147483645
输出：30
解释：输入的二进制串 1111111111111111111111111111101 中，共有 30 个设置位。

提示：

• 1 <= n <= 2^31 - 1

思路：题目的意思也很简单，就是让我们求出一个数中对应的二进制位为1的个数。首先，我们应该要想到直接去暴力枚举32次（将整数的32个比特位都遍历一遍），统计其中对应二进制位为1的个数。在暴力的基础上，我们会发现有的二进位是0的，我们不需要统计，即当一段二进制中前面全部是0了，我们就无需统计了。因此使用 while 循环来遍历统计，当 对应的值没有1时，便停止统计。最后一种直接求1的个数就行，通过大佬们给出的公式套就行了。

代码实现：

1、暴力枚举版：

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if (((1<<i) & n) != 0) { // 这个位是1
                count++;
            }
        }
        return count;
    }
}

2、一点点优化版：

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            if ((n & 1) != 0) {
                count++;
            }
            n >>= 1;
        }
        return count;
    }

    
}

3、大佬秒杀版：

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

第三个版本看不懂的小伙伴，一定要去前面的图片中弄懂，至少要知道公式。 

461. 汉明距离

题目：

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置。

示例 2：

输入：x = 3, y = 1
输出：1

提示：

• 0 <= x, y <= 2^31 - 1

思路：汉明距离就是两个数对应的二进制位中，出现了不同的1的个数。如果两个1出现在了相同的二进制位，那么这个1不加入计算，反之如果一个数对应位置中出现了1，而另一个位置没有，那这个1就是我们要找的。

代码实现：

1、暴力枚举：for循环-32次遍历比较

class Solution {
    public int hammingDistance(int x, int y) {
        // 暴力枚举：
        int count = 0;
        for (int i = 0; i < 32; i++) {
            // 计算出对应位置的值
            int temp1 = ((x>>i) & 1);
            int temp2 = ((y>>i) & 1);
            // 看看两者的值是否相等
            if ((temp1 ^ temp2) == 1) {
                count++;
            }
        }
        return count;
    }
}

2、异或+统计1的个数：题目就是找不同的1，异或之后就可以得到，接下来便是统计1的个数。

class Solution {
    public int hammingDistance(int x, int y) {
        // 异或+统计1的个数
        int count = 0;
        int n = x ^ y;
        while (n != 0) {
            count++;
            n = n & (n-1); // 消除1
        }
        return count;
    }
}

260. 只出现一次的数字III

题目： 

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

输入：nums = [-1,0]
输出：[-1,0]

示例 3：

输入：nums = [0,1]
输出：[1,0]

提示：

• 2 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• 除两个只出现一次的整数外，nums 中的其他数字都出现两次

思路：统计数字出现的次数，同样可以直接暴力哈希的方法，求出最终的结果。我们如果采用 ^ 的方法也是可以写出来的，因为有两个元素都只出现了一次，而其他的元素都出现了两次，那么最终 ^ 的结果就是两个只出现一次的元素 ^ 的结果，而根据这个结果中最右边的1，再次对数组进行分组之后，得到的 ^ 结果就是最终我们要求的结果。

代码实现：

1、暴力枚举：

class Solution {
    public int[] singleNumber(int[] nums) {
        // 暴力枚举：哈希表统计
        Map<Integer, Integer> hash = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            hash.put(nums[i], hash.getOrDefault(nums[i], 0)+1);
        }
        int[] ret = new int[2];
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (hash.get(nums[i]) == 1) {
                ret[j++] = nums[i];
            }
        }
        return ret;
    }
}

2、异或分组统计：先将异或的结果最右边的"1"算出来，再根据这个进行分组（两个只出现一次的元素，肯定是在不同的组别了），再对分组的结果进行 ^ ，最终分别的结果就是只出现一次的元素。

class Solution {
    public int[] singleNumber(int[] nums) {
        // 先分组，再分别统计
        int[] ret = new int[2];
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum ^= nums[i]; // 这个是两个数字的异或结果
        }
        // 找到两个数字有区别的地方进行分组
        int mask = sum & (-sum); // 找到最右边第一个出现的1
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] & mask) == 0) {
                ret[0] ^= nums[i];
            } else {
                ret[1] ^= nums[i];
            }
        }
        return ret;
    }
}

面试题01.01.判定字符是否唯一

题目：

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1：

输入: s = "leetcode" 
输出: false 

示例 2：

输入: s = "abc"
输出: true

限制：

• 0 <= len(s) <= 100
• s[i]仅包含小写字母
• 如果你不使用额外的数据结构，会很加分。

思路：这个题目应该很容易想到 哈希的思想 来遍历统计解决这个问题，但是这个没有用到我们今天学习的位运算知识。我们先回顾一下，哈希的思想就是用一个数组来统计字符出现的次数，那么我们也完全可以用到位图的思想来细化哈希呀！因为题目只有26个字母，因此我们完全可以用一个 整型变量来当作哈希表（使用比特位来记录当前是哪个字符）。

如果想要详细了解位图的小伙伴，可以去看下面这篇文章：位图 

代码实现：

1、哈希思想版：

class Solution {
    public boolean isUnique(String astr) {
        // 哈希表记录遍历的字符
        int[] hash = new int[26];
        for (int i = 0; i < astr.length(); i++) {
            char ch = astr.charAt(i);
            if (hash[ch-'a'] != 0) {
                // 说明已经出现了重复的字符
                return false;
            } else {
                hash[ch-'a']++;
            }
        }
        return true;
    }
}

2、位图思想版（细化版的哈希） ：

class Solution {
    public boolean isUnique(String astr) {
        int ret = 0;
        int n = astr.length();
        if (n > 26) { // 多于26个，那么肯定是有重复的了
            return false;
        }
        for (int i = 0; i < n; i++) {
            int x = astr.charAt(i)-'a';
            if ((ret & (1<<x)) != 0) { // 重复了
                return false;
            } else {
                ret |= (1<<x); // 加入位图
            }
        }
        return true;
    }
}

268.丢失的数字

题目：

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 3：

输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

示例 4：

输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

提示：

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• nums 中的所有数字都 独一无二

思路：

1、我们可以先采用排序的方法，使其有序后，再按照顺序去遍历，查找缺失的元素。

2、也可以采用 哈希的思想，遍历记录出现的次数，然后再遍历哈希表，找到没出现的数字。

3、还可以采用 高斯求和（等差数列的求和公式） 的方法将完整的数组总合求出来，然后再去遍历原数组，对元素作差，即可得到最终结果。

4、在 [0，n] 之间缺失了一个数字，那么只要我们将[0，n+1] 这两个区间的元素全部进行 ^ ，那么就能得到 "只出现一次的元素"。

代码实现（按照序号来的）：

1、排序：

class Solution {
    public int missingNumber(int[] nums) {
        // 找出最大值
        int n = nums.length;
        Arrays.sort(nums); // 排序
        // 缺失的是最大值
        if (n != nums[n-1]) {
            return n;
        }
        for (int i = 0; i < n; i++) {
            if (i != nums[i]) {
                return i;
            }
        }
        return -1;
    }
}

2、哈希表：

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int[] hash = new int[n+1];
        for (int i = 0; i < n; i++) {
            hash[nums[i]]++;
        }
        for (int i = 0; i < n+1; i++) {
            if (hash[i] == 0) { // 找到了
                return i;
            }
        }
        return -1;
    }
}

3、高斯求和：

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int sum = (int)((0+n) / 2.0 * (n+1));
        // (0+n) * (n+1) / 2 ,这个也行
        for (int i = 0; i < n; i++) {
            sum -= nums[i];
        }
        return sum;
    }
}

如果求 sum 时，是先 / 2的话，就会导致结果不正确。因为 /2得到的是一个整数，可能出现分数的情况被忽略了。 

4、异或运算：

class Solution {
    public int missingNumber(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum ^= nums[i];
            sum ^= i;
        }
        return sum ^ nums.length;
    }
}

371.两整数之和

题目：

给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。

示例 1：

输入：a = 1, b = 2
输出：3

示例 2：

输入：a = 2, b = 3
输出：5

提示：

• -1000 <= a, b <= 1000

思路：如果是在笔试中遇到这样的题目的话，我们可以直接来个流氓解法。不是让我们求两个数的和嘛，我们直接返回 a+b 的结果就可以了。当然，在面试中是不能这么做的。

这题本质上是让我们去模拟实现加法的，加法操作可以分为两步：

1、先计算出 无进位相加的结果；

2、再计算出 进位的结果；

3、最后再将两者相加，得到的就是最终的结果。而第三步，其实就是在重复 1、2步，当 进位的结果为0时，那么无进位相加的结果就是最终的结果，此时便可以不在循环了。

代码实现：

class Solution {
    public int getSum(int a, int b) {
        do {
            // 1、计算无进位相加的结果
            int temp = a ^ b;
            // 2、计算进位的结果
            b = (a & b) << 1;
            a = temp;
        } while (b != 0);
        return a;
    }
}

137.只出现一次的数字Ⅱ 

题目：

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

提示：

• 1 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

 思路：首先，应该想到用暴力的思路，用哈希表记录元素出现的次数，然后在去遍历数组找到哈希表中只出现一次的元素。很显然，这种方法不符合题目所期望的那样。

我们可以遍历数组，统计某一个比特位上的数据。
出现了三次的数据，在某个比特位上有两种情况：1、3n个0，3n个1（n <= nums.length）；同样出现了一次的数字也是如此，我们再把这些数据相加，那么同一个比特位就会出现四种情况：
1、 3n个0 + 0        2、 3n个0 + 1         3、 3n个1 + 0            4、 3n个1 + 1
           0                            1                             3                                3n+1
如果我们把上面的比特位都进行 %3 操作的话，得到的就是：0  1  0  1 -> 和只出现一次的数字一样
那么我们就可以把只出现一次的数字的对应比特位全部算出来。

总结下来，就是去遍历数组计算出，某一位的比特位之和，然后再 %3 算出只出现一次的数字所对应的比特位，将这个比特位对应的值添加到只出现一次的数字变量中，接着继续重复上述步骤，计算出下一个比特位的值。

代码实现：

1、哈希暴力统计版：

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> hash = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            hash.put(nums[i], hash.getOrDefault(nums[i], 0)+1);
        }
        for (int i = 0; i < nums.length; i++) {
            if (hash.get(nums[i]) == 1) {
                return nums[i];
            }
        }
        return -1;
    }
}

2、巧妙借助"位运算"：

class Solution {
    public int singleNumber(int[] nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            // 计算某一个比特位上的和
            int sum = 0;
            for (int j = 0; j < nums.length; j++) {
                sum += ((nums[j] >> i) & 1);
            }
            // 求出只出现一次所对应的比特位
            sum %= 3;
            // 设置对应位置的比特位
            ret |= (sum << i); 
        }
        return ret;
    }
}

 拓展：当数组中一个数字出现一次，另外的数字出现 n 次时，也可以使用上述的思路。

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

题目：

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

以任意顺序返回这两个数字均可。

示例 1:

输入: [1]
输出: [2,3]

示例 2:

输入: [2,3]
输出: [1,4]

提示：

• nums.length <= 30000

思路：题目让我们找丢失的元素，我们可以通过暴力哈希的方法，找到没有出现的元素。但是这个是不符合题目的要求的。其实看到这个题目，我们就应该想到 "只出现一次的数字III"的思路，那个题目只是把两个数字丢到数组中了，而这个题目是把数字给丢掉了。但是我们可以看成是在数组中，那么我们的做法和那一题差不多，先把nums数组遍历 ^ 一遍，再把 [1, n+2] 之间的数字再 ^ 一遍，这样剩下的数字就是丢到的两个数字的 ^ 结果，而我们只需要找出最右边的 1，再去进行分组 ^ ，这样可以分别得到丢失的数。

代码实现：

1、哈希暴力：

class Solution {
    public int[] missingTwo(int[] nums) {
        // 哈希表遍历统计
        int n = nums.length;
        int[] hash = new int[n+3]; // 0+缺失的两个空间
        int[] ret = new int[2];
        for (int x : nums) {
            hash[x]++;
        }
        int j = 0;
        for (int i = 1; i < n+3; i++) {
            if (hash[i] == 0) {
                ret[j++] = i;
            }
        }
        return ret;
    }
}

2、巧妙运用"位运算"： 

class Solution {
    public static int[] missingTwo(int[] nums) {
        // 先找到分组的依据
        int n = nums.length;
        int sum = 0;
        for (int i = 1; i < n+3; i++) {
            sum ^= i;
        }
        for (int i = 0; i < n; i++) {
            sum ^= nums[i];
        }
        // 找到最右边的1，作为分组的依据
        int mask = sum & (-sum);
        // 将 mask 作为分组的依据
        int[] ret = new int[2];
        for (int i = 1; i < n+3; i++) {
            if ((mask & i) != 0) { // 这里不一定是1
                ret[0] ^= i;
            } else {
                ret[1] ^= i;
            }
        }
        for (int i = 0; i < n; i++) {
            if ((nums[i] & mask) != 0) { // 这里不一定是1
                ret[0] ^= nums[i];
            } else {
                ret[1] ^= nums[i];
            }
        }
        return ret;
    }
}

以上就是位运算的全部应用场景，主要是利用 推导的公式 和 ^ 来解题。 而且从上面的解题结果来看，只要能用位运算解决的，基本上可以用别的方法写出来。但是位运算会很巧妙。

好啦！本期  一文详解“位运算“在算法中的应用  的学习之旅就到此结束啦！我们下一期再一起学习吧！