面试题解析：消失的两个数字（位运算解法）

面试题：消失的两个数字

题目描述

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

解题思路

这道题是经典位运算问题的组合变体。核心在于利用异或（XOR）运算的特性：

• 任何数与自身异或结果为 0。
• 任何数与 0 异或结果为其本身。
• 异或运算满足交换律和结合律。

如果我们把数组中的所有元素，以及区间 [1, n+2] 中的所有数字全部进行异或，那么出现两次的数字都会抵消为 0，最终剩下的结果就是那两个缺失数字的异或值（记为 temp = a ^ b）。

既然 a != b，那么 temp 一定不为 0，这意味着在二进制表示中至少有一位是 1。我们可以找到这个差异位，根据这一位的不同将原数组和区间数分为两组。每一组中都只包含一个缺失数字（其余数字均成对出现），分别对两组进行异或即可得到 a 和 b。

C++ 实现

这里提供两种常见的实现方式，本质逻辑一致，区别在于寻找差异位的方法略有不同。

方法一：提取最右边的 1

利用 x & (-x) 可以快速提取出二进制中最右侧的 1，这是补码运算的特性。

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int temp = 0;
        // 1. 异或所有数组元素
        for (auto& x : nums) temp ^= x;
        // 2. 异或所有区间 [1, n+2] 的数字
        for (int i = 1; i <= nums.size() + 2; i++) temp ^= i;
        
        // 此时 temp = a ^ b，且至少有一位为 1
        // 提取最右边的 1 作为分组依据
        int ls = temp & (-temp);
        
        int a = 0, b = 0;
        // 3. 根据 ls 位分组异或
        for (auto& x : nums) {
            if (x & ls) a ^= x;
            else b ^= x;
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            if (i & ls) a ^= i;
            else b ^= i;
        }
        return {a, b};
    }
};

方法二：循环查找差异位

如果不熟悉位运算技巧，也可以通过循环移位找到第一个不同的比特位。

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        // 1. 计算两个缺失数的异或值
        int tmp = 0;
        for (auto x : nums) tmp ^= x;
        for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;
        
        // 2. 找出 tmp 中任意一个为 1 的位（例如最低位）
        int diff = 0;
        while (!((tmp >> diff) & 1)) diff++;
        
        // 3. 根据 diff 位将数字分为两类并分别异或
        int a = 0, b = 0;
        for (int x : nums) {
            if ((x >> diff) & 1) b ^= x;
            else a ^= x;
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            if ((i >> diff) & 1) b ^= i;
            else a ^= i;
        }
        return {a, b};
    }
};

总结

这两种写法的时间复杂度均为 O(n)，空间复杂度为 O(1)。在实际面试中，方法一更体现对位运算底层特性的掌握，代码更简洁；方法二逻辑更直观，易于理解。无论哪种，关键在于理解如何通过异或消除重复项，并利用差异位将问题分解为两个子问题。