LeetCode260-只出现一次的数字III-位运算-数学

原题链接

把所有的数异或起来，两个相同的异或完就成0了，那么最终得到的就是a ^ b

他俩不一样，所以他俩异或完肯定不是0，那么随便找一位不为0的位置，就是说明这两个数这一位是不一样的，一个是0 一个是1

再把原来的数组，按照这一位是0或者1分开成两部分，a 和 b就分别在这两部分里面了

那么对每部分全部进行一次异或操作，就可以分别知道a 和 b 的值了

不可能说其他的数被分到两个不同的区间了，数要一样，那这一位是1都是1，是0都是0

class Solution {
public:
    int get(vector& nums, int k, int t){
        int res = 0;
        for(auto x: nums)
            if( (x >> k & 1) == t)
                res ^= x;
        return res;
    }

    vector singleNumber(vector& nums) {
        int ab = 0;
        for(auto x: nums)   ab ^= x;
        int k = 0;
        while((ab >> k & 1) == 0)   k ++;
        return {get(nums, k, 0), get(nums, k, 1)};
    }
};