算法实战：位运算解决整数求和与缺失数字问题

36. 只出现一次的数字 II

题目描述

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

示例

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

核心思路：比特位计数

既然其他数字都出现了三次，那么对于任意一个二进制位（bit），如果该位上的 1 被统计起来，其总和一定是 3 的倍数加上那个唯一数字在该位上的值（0 或 1）。

因此，我们只需要遍历所有数字的每一个二进制位，统计该位上 1 出现的总次数。对 3 取余，剩下的就是目标数字在该位上的值。通过这种方式还原出每一位，就能拼凑出完整的数字。

代码实现

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        // 遍历 32 位整数的每一位
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            // 统计当前位上 1 的个数
            for (int x : nums) {
                sum += ((x >> i) & 1);
            }
            // 如果某一位的 1 的个数不是 3 的倍数，说明目标数字在这一位上是 1
            if (sum % 3 != 0) {
                ret |= (1 << i);
            }
        }
        return ret;
    }
};

流程解析

38. 消失的两个数字

题目描述

给定一个包含从 0 到 n 的所有整数中缺失了两个数字的数组，找出这两个缺失的数字。

示例

输入：nums = [1, 0] 输出：[2, 3] (顺序不限)

核心思路：分组异或

这个问题可以看作是'丢失的数字'和'只出现一次的数字 III'的结合版。

1. 整体异或：将数组中的所有数与 [1, n+2] 范围内的所有数进行异或。由于成对的数会抵消，最后得到的结果 ret 等于两个缺失数字的异或值（a ^ b）。
2. 区分两组：因为 a 和 b 不同，所以 ret 中至少有一位是 1。找到这个最右侧的 1 所在的位 x。
3. 分组异或：根据第 x 位是 0 还是 1，将所有数字分成两组。这样 a 和 b 必然会被分到不同的组中，而其他成对的数会在同一组内互相抵消。分别对两组进行异或，即可得到 a 和 b。

代码实现

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int ret = 0;
        // 第一步：计算所有数字与完整序列的异或结果
        for (int num : nums) {
            ret ^= num;
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            ret ^= i;
        }
        // 此时 ret = a ^ b
        
        // 第二步：找到 ret 中最右侧为 1 的位
        int diffBit = 0;
        while (((ret >> diffBit) & 1) == 0) {
            diffBit++;
        }
        
        int a = 0, b = 0;
        // 第三步：根据该位分组异或
        for (int num : nums) {
            if ((num >> diffBit) & 1) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            if ((i >> diffBit) & 1) {
                a ^= i;
            } else {
                b ^= i;
            }
        }
        
        return {a, b};
    }
};

流程解析