LeetCode56-Ⅰ，数组中数字出现的次数

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

示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
限制：

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof

题目分析：如果想要通过，用一个哈希表就行了，但这一题要求时间复杂度是O(n)，空间复杂度是O(1)，所以考察的地方绝对不是使用哈希表，这一题考察的是位运算中异或运算的相关性质。所以在这里记录一下：

• 1. A ^ A = 0, A ^ 0 = A .
• 2. 交换律: A ^ B = B ^ A;
• 3. 结合律: (A ^ B) ^ C = A ^ ( B ^ C) = ...
• 4.A ^ B = C <=> C ^ B = A
• 5. A^ -A 得到该数最低位的1
     根据以上性质，我们就可以按要求解决上面的问题了：

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        //vector<int> ans;
        int n = nums.size();
        
        //性质1
        int t = 0;
        for(auto&x: nums) t^=x;    //循环结束后 t = A ^ B（A,B是答案）
        
        //按最后一个1的位置对原数组分类，性质5
        int ans = 0;
        int flag = t&(-t);
        
        for(auto &x:nums){
            if(x&flag) ans ^= x;  //性质1
        }
        return {ans,ans^t};  //性质4
    }
};