【位运算】出现次数为1的数

题目链接（出现次数为1的数）

解题思路

已知有规律：x^y^y=x，可将所有元素异或到一起得到两出现一次的元素的异或结果(分别记为a和b，则异或结果为a^b)

由异或的规律可知：a^b二进制位值为1的位置，就是二者不同的位置

因此将数组分为两个子集：异或a^b是0的和异或a^b是1的

对于每个子集，都有a和b中各自一个和其他出现次数为2的元素，各自异或即为两个出现次数为1的元素

代码

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long long ab=0;
        for(int i=0;i<nums.size();i++)ab^=nums[i];

        long long a=0;
        long long b=0;
        long long dif= ab&(-ab);

    for(int i=0;i<nums.size();i++){
        if(nums[i]&dif)b^=nums[i];
        else a^=nums[i];
    }
    return {(int)b,(int)a};
    }
};