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

算法思路

既然其他数字都出现了三次，而目标数字只出现了一次，我们可以从二进制的角度思考。对于任意一个比特位（bit），如果统计数组中所有数字在该位上为 1 的总次数，那么这个总数对 3 取余，剩下的余数就是目标数字在该位上的值（0 或 1）。

通过遍历 32 个比特位，依次确定目标数字每一位的值，即可还原出整个数字。

C++ 算法代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        // 遍历整数的 32 个比特位
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            // 统计所有数字在第 i 位上为 1 的次数
            for (int x : nums) {
                sum += ((x >> i) & 1);
            }
            // 模 3 后还原到 ret 对应的位置
            ret |= ((sum % 3) << i);
        }
        return ret;
    }
};

消失的两个数字

题目链接：

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

题目描述：

给定一个包含从 0 到 n+1 的整数数组，其中有两个数字消失了，请找出这两个消失的数字。

题目示例：

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

解法（位运算）：

算法思路

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

1. 整体异或：将数组中的所有数与区间 [1, n+2] 的所有数进行异或。由于除了消失的两个数外，其他数都出现了两次（一次在数组，一次在区间），它们会相互抵消。最终得到的结果 ret 等于那两个消失数字的异或值（a ^ b）。
2. 分组策略：因为 a 和 b 不同，它们的异或结果 ret 中至少有一位是 1。找到这个最右侧为 1 的比特位，根据这一位是 0 还是 1，可以将所有数字分成两组。
3. 分别求解：消失的两个数必然分属不同的组。对每一组分别进行异或操作，即可分别得到 a 和 b。

C++ 算法代码

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++;
        }
        
        // 第三步：根据该位分组异或
        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};
    }
};

以上三道题目展示了位运算在处理数值关系时的强大能力。掌握异或消去、进位模拟以及比特位统计的技巧，能帮助你在线性时间复杂度内解决许多看似复杂的数组问题。