算法实战：消失的两个数字 - 位运算解法

问题描述

给定一个包含 n 个整数的数组 nums，其中包含了从 1 到 n+2 的所有整数，但恰好缺失了两个。请找出这两个缺失的数字。

核心思路

这道题是经典的「只出现一次的数字」问题的变种。利用异或（XOR）运算的特性：

• 任何数与自身异或结果为 0（a ^ a = 0）
• 任何数与 0 异或结果为其本身（a ^ 0 = a）
• 异或满足交换律和结合律

如果我们把数组中的所有元素与 1 到 n+2 的所有整数进行异或，成对出现的数字都会抵消为 0，最终剩下的结果就是那两个缺失数字的异或值（记为 ret = a ^ b）。

既然 a != b，那么 ret 一定不为 0，这意味着 a 和 b 在二进制表示上至少有一位是不同的。我们可以找到这个不同的位，将原数组和 1 到 n+2 的序列根据该位是 0 还是 1 分成两组。这样，a 和 b 必然被分到了不同的组中，而相同的数字依然会在同一组内成对出现。分别对两组数据进行异或，即可得到 a 和 b。

实现方案

方案一：通用分组法

通过循环查找 ret 中任意一个为 1 的二进制位，以此作为区分标准。

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int ret = 0;
        // 1. 计算所有数字与 1~n+2 的异或和
        for (auto x : nums) ret ^= x;
        for (int i = 1; i <= nums.size() + 2; ++i) ret ^= i;
        
        // 2. 找到 ret 中任意一个为 1 的位（即 a 和 b 不同的位）
        int differ = 0;
        while (!((ret >> differ) & 1)) differ++;
        
        // 3. 根据该位将数字分为两组分别异或
        int a = 0, b = 0;
         ( x : nums) {
             ((x >> differ) & ) b ^= x;
             a ^= x;
        }
         ( i = ; i <= nums.() + ; ++i) {
             ((i >> differ) & ) b ^= i;
             a ^= i;
        }
         {a, b};
    }
};