算法实战：位运算解法详解（两数之和、唯一数字、消失数字）

36. 只出现一次的数字 II

题目来源：LeetCode 137

题目描述

题目示例

解题思路

这道题的难点在于要求线性时间复杂度且不使用额外空间。既然除了一个数字外，其他都出现了三次，那我们可以从二进制位的角度思考。

假设我们要找的数是 ret。对于任意一个比特位，如果该位上所有数字的和能被 3 整除，说明那个单独的数字在该位上是 0；否则余数为 1，说明该位是 1。通过遍历 32 个比特位，我们就能还原出整个数字。

代码实现

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // 方法一：排序 (时间复杂度较大:O(NlogN)，但容易想到)
        // sort(nums.begin(), nums.end());
        // for(int i = 0; i < nums.size() - 1; i += 3) {
        //     if(nums[i] != nums[i + 1]) {
        //         return nums[i];
        //     }
        // }
        // return nums.back();

        // 方法二：位运算 (为线性时间复杂度:O(32N)，但非常巧妙比较难想)
        int ret = 0; // 作为位图
        for(int i = 0; i < 32; i++) { // 一个数二进制位的长度，依次修改 ret 的每一位
            int sum = 0;
            for(int x = 0; x < nums.size(); x++) { // 计算 nums 中所有数的二进制第 i 位的和
                sum += ((nums[x] >> i) & 1);
            }
            ret |= ((sum % 3) << i); // 求和结果余 3 后修改到 ret 对应第 i 位的位置
        }
        return ret;
    }
};

流程图解

38. 消失的两个数字

题目来源：LeetCode 面试题 17.19

题目描述

题目示例

解题思路

这题其实是前面两道题的组合拳。相当于在数组里找两个缺失的数，其余数都出现了两次。

核心策略是先整体异或：将数组中的数和区间 [1, n+2] 内的所有数全部异或一遍。根据异或性质，成对出现的数会抵消，最后剩下的结果就是那两个消失数字的异或值（a ^ b）。

因为 a 和 b 不同，它们的异或结果中至少有一位是 1。找到这一位，就可以把数组里的数和区间数分成两组：一组该位为 0，一组该位为 1。这样 a 和 b 就被分开了，分别对这两组数据进行异或，就能还原出这两个消失的数字。

代码实现

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        // 位运算
        // 先将数组 nums 所有数以及 1~N+2 区间所有数全部异或一遍，得到消失两数的异或
        int ret = 0;
        int a = 0;
        int b = 0;
        // 分别表示两个消失的数

        for(int i = 0; i < nums.size(); i++) {
            ret ^= nums[i];
        }
        for(int i = 1; i <= nums.size() + 2; i++) {
            ret ^= i;
        }
        // 此时 ret = a ^ b
        // 由于 a 和 b 一定不同，所以一定会存在某一位比特位一个是 0 一个是 1
        // 两者异或后对应的那一位就一定是 1，所以我们需要找到那一位

        // 获取到 ret 最右侧出现 1 的比特位位置
        int x = 0;
        while(1) {
            if(((ret >> x) & 1) == 1) {
                break;
            }
            x++;
        }

        // 将数组 nums 所有数以及 (1~N+2) 区间所有数分成两类：
        // 一类就是第 x 位比特位值为 0，一类就是第 x 位比特位值为 1
        // 这样两个消失数就会被分开，通过异或，在数组以及 (1~N+2) 区间都出现的数就会抵消
        // a 和 b 也就分别是这两个消失数了

        for(int i = 0; i < nums.size(); i++) {
            if(((nums[i] >> x) & 1) == 0) { // 假设 a 是第 x 位比特位为 0 的消失数
                a ^= nums[i];
            } else { // 假设 b 就是第 x 位比特位为 1 的消失数
                b ^= nums[i];
            }
        }
        for(int i = 1; i <= nums.size() + 2; i++) {
            if(((i >> x) & 1) == 0) {
                a ^= i;
            } else {
                b ^= i;
            }
        }
        // 两次循环则数组中存在的数异或了两次被抵消，a 和 b 就分别是两个消失数
        return {a, b};
    }
};

流程图解