剑指 Offer 56 - I. 数组中数字出现的次数

剑指 Offer 56 - I. 数组中数字出现的次数

思路：

把所有的数都异或，最后得到的结果就是两个不同的数异或的结果，记为tmp。然后找个分组的条件，即tmp的中哪一位是1(只要找到一个就可以)记为第k位是1(这里指的是二进制的位)，异或是不进位的加法，那么如果这一位是1，说明ab这一位是不同的，而对于其它的数字，由于都出现了两次而且重复的元素也意味着相等，所以不管怎么分组，相同的数字一定分到同一组，所以依据这个思想可以去寻找其中的一个数a，最后的答案就是{a,tmp ^ a}

代码：

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int a  = 0;
        int tmp = 0;
        for(auto x : nums) tmp ^= x;
        int k = 0;
        while(!(tmp >> k & 1)) k++;
        for(auto x : nums){
            if(x >> k & 1) a ^= x;
        }
        return {a,tmp ^ a};
    }
};