算法实战：位运算解决三题（两数之和、唯一数字、消失数字）

38. 消失的两个数字

题目描述

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

解题思路与实现

本题相当于就是'丢失的数字' + '只出现一次的数字 III'组合起来的题。

核心思路是将数组中的数和**【1，n+2】区间内的所有数**【异或】在一起。问题就变成了：有两个数出现了【一次】，其余所有的数出现了【两次】。

进而变成了经典的'只出现一次的数字 III'问题。具体步骤如下：

1. 先将数组 nums 所有数以及 1~N+2 区间所有数全部异或一遍，得到消失两数的异或值 ret。
2. 由于 a 和 b 一定不同，ret 的二进制表示中至少有一位是 1。找到那一位，可以将所有数分为两类：该位为 0 的和该位为 1 的。
3. 这样两个消失数就会被分开，通过再次异或，在数组以及区间都出现的数就会抵消，最终剩下的就是那两个消失数。

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        // 位运算
        // 先将数组 nums 所有数以及 1~N+2 区间所有数全部异或一遍，得到消失两数的异或
        int ret = 0;
        int a = 0;
        int b = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            ret ^= nums[i];
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            ret ^= i;
        }
        
        // 此时 ret = a ^ b
        // 获取到 ret 最右侧出现 1 的比特位位置
        int x = 0;
        while (1) {
            if (((ret >> x) & 1) == 1) {
                break;
            }
            x++;
        }
        
        // 将数组 nums 所有数以及 (1~N+2) 区间所有数分成两类
        // 一类就是第 x 位比特位值为 0，一类就是第 x 位比特位值为 1
        for (int i = 0; i < nums.size(); i++) {
            if (((nums[i] >> x) & 1) == 0) {
                a ^= nums[i];
            } else {
                b ^= nums[i];
            }
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            if (((i >> x) & 1) == 0) {
                a ^= i;
            } else {
                b ^= i;
            }
        }
        
        return {a, b};
    }
};

这三道题展示了位运算在算法设计中的强大之处。掌握这些技巧，能让你在处理数据流、内存受限等场景下游刃有余。