【位运算】消失的两个数字

输入: [1]
输出: [2,3]

输入: [2,3]
输出: [1,4]

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        // 1. 假设丢失的是a和b，那么先异或上全部元素，得到的结果就是a^b
        int n = 0;
        for(int i = 0; i < nums.size(); ++i)
            n ^= nums[i];
        for(int i = 1; i <= nums.size() + 2; ++i)
            n ^= i;
        
        // 2. 找到a和b比特位中为1的其中一个位置（a和b是不同的，所以一定存在这个比特位为1）
        int pos = 0;
        while(true)
        {
            if((n >> pos) & 1)
                break;
            pos++;
        }

        // 3. 根据这个相异的比特位就能划分成两个集合seta和setb
        int seta = 0, setb = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            if((nums[i] >> pos) & 1)
                seta ^= nums[i];
            else
                setb ^= nums[i];
        }

        // 4. 此时就是分别在seta和setb中找只存在一次的数，也就是a和b，那么只需要再遍历异或一遍所有整数即可
        for(int i = 1; i <= nums.size() + 2; ++i)
        {
            if((i >> pos) & 1)
                seta ^= i;
            else
                setb ^= i;
        }
        return { seta, setb };
    }
};