算法实战：位运算解决两数之和、唯一数字与缺失数字

流程解析

36. 只出现一次的数字 II

题目链接

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

题目描述

题目示例

解法（比特位计数）

核心思路

这道题要求找出数组中只出现一次的数字，其余数字都出现了三次。

我们可以从二进制的角度思考：对于任意一个比特位，如果所有数字在该位上为 1 的总次数能被 3 整除，说明目标数字在该位上是 0；否则，目标数字在该位上是 1。

通过遍历 32 个比特位，统计每一位上 1 出现的次数并对 3 取模，就能还原出目标数字的二进制表示。

参考代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0; // 作为位图，存储最终结果
        for (int i = 0; i < 32; i++) { // 依次检查每一个比特位
            int sum = 0;
            for (int x : nums) {
                // 累加当前位上的值
                sum += ((nums[x] >> i) & 1);
            }
            // 如果该位 1 的个数不是 3 的倍数，则目标数字该位为 1
            ret |= ((sum % 3) << i);
        }
        return ret;
    }
};

流程解析

38. 消失的两个数字

题目链接

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

题目描述

题目示例

解法（位运算）

核心思路

这道题可以看作是'丢失的数字'与'只出现一次的数字 III'的结合体。

1. 整体异或：将数组中的所有数，与区间 [1, n+2] 内的所有数进行异或。因为除了两个消失的数字外，其他数字都出现了两次（一次在数组，一次在区间），异或后都会抵消为 0。剩下的结果就是两个消失数字的异或值 ret = a ^ b。
2. 分组策略：由于 a 不等于 b，ret 中至少有一位是 1。找到这个最右侧的 1，它意味着 a 和 b 在这一位上不同（一个为 0，一个为 1）。
3. 分别求解：根据这一位是 0 还是 1，将所有数字分成两组。分别对两组进行异或，每一组中都会剩下一个消失的数字。

参考代码

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int ret = 0;
        int a = 0;
        int b = 0;

        // 第一步：计算两个消失数字的异或值
        for (int num : nums) {
            ret ^= num;
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            ret ^= i;
        }

        // 第二步：找到 ret 中最右侧为 1 的比特位
        int x = 0;
        while (((ret >> x) & 1) == 0) {
            x++;
        }

        // 第三步：根据第 x 位分组异或
        for (int num : nums) {
            if (((num >> x) & 1) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            if (((i >> x) & 1) == 0) {
                a ^= i;
            } else {
                b ^= i;
            }
        }

        return {a, b};
    }
};

流程解析