数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

思路

整个数组的的数组异或结果就是那两个只出现一次的两个数的异或结果。记这个结果为sum,只出现一次的两个数分别为x,y。如果sum的某一二进制位为1，记为sum_i，说明x,y的相应二进制位不同，以这个二进制位为标准划分数组，和sum_i相同的划到一组，不同的划到另一组。那么x,y不同组，并且x组里其他数字必是俩俩相同的，y组里也一样。

代码

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int sum = 0;
        for(int num: nums) {
            sum ^= num;
        }
        int dif = 1;
        while((sum&dif) == 0) {
            dif = dif << 1;
        }
        int a = 0,b = 0;
        for(int num: nums) {
            if(dif&num){
                a ^= num;
            }
            else {
                b ^= num;
            }
        }
        return {a,b};
    }
};