算法题讲解：位运算应用（两数之和、只出现一次的数字、消失的两个数字）

36. 只出现一次的数字 II

题目链接

137. 只出现一次的数字 II - 力扣（LeetCode）

题目描述

题目示例

解法（比特位计数）

算法思路

设要找的数为 ret。 由于整个数组中，需要找的元素只出现了【一次】，其余的数都出现【三次】，因此我们可以用根据所有数的【某一个比特位】的总和 %3 的结果，快速定位到 ret 上的【一个比特位上】的值 是 0 还是 1。 这样我们通过 ret 的每一个比特位上的值，就可以将 ret 还原出来。

C++ 算法代码

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. 消失的两个数字

题目链接

面试题 17.19. 消失的两个数字 - 力扣（LeetCode）

题目描述

题目示例

解法（位运算）

算法思路

本题相当于就是 268.丢失的数字 + 260.只出现一次的数字||| 组合起来的题。 先将数组中的数和【1，n+2】区间内的所有数【异或】在一起，问题就变成了：有两个数出现了【一次】，其余所有的数出现了【两次】。进而变成了 260.只出现了一次的数字||| 这道题。

C++ 算法代码

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};
    }
};

算法总结及流程解析

结语

至此，三道算法题讲解完毕。第 35 题通过异或和按位与操作实现无进位加法，循环处理进位直至为零，高效求解两数之和；第 36 题利用比特位计数技术，统计所有数字各二进制位出现次数，模 3 结果定位唯一出现一次的数字；第 38 题通过位运算巧妙解决。首先将数组与 [1,n+2] 区间所有数异或，转化为两个数出现一次的问题。核心思路借鉴了 260 题《只出现一次的数字 III》，通过提取不同比特位将数分组异或，最终找到缺失的两个数。