LeetCode 260. 只出现一次的数字 III（异或运算）

1.题目

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5]
输出: [3,5]
注意：

结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.题解

因为异或运算规则为：两数相同的结果为0，不同的结果为1。
所以异或整个数组，由于数组中所有相同的数值在异或运算中都变为0，
导致结果只剩下两个不同的数值的异或：
例如：nums = [4, 1, 4, 6]，4¹4⁶⁼⁴4¹6=1^6=0x0111，此时全数组数值的异或为那两个不同数值的异或；
例如：nums = [1, 2, 10, 4, 1, 4, 3, 3]，循环异或后值为2^10=0x1000。

之后的操作只需将这两个数分出来即可
以nums = [4, 1, 4, 6]为例：
nums异或一遍后为0x0111，要想将不同的两数分离，只需在异或时选择一位与1的对应位相同，并且与6的对应位不同即可，
那异或结果都是0x0111，说明这两个不同的数值的不同位为0x0100,0x0010,0x0001，所以选择最低位异或即可将其分出。
例：div选择0x0001: 0x0001与nums = [4, 1, 4, 6]所有数值异或，会得到两组数组，最后一位=1的数为1，最后一位=0的数为4,4,6。
两组数分别异或得最终不同的两数：1，4^ 4^ 6=6，即1和6找到。

class Solution
{
public:
    vector<int> singleNumber(vector<int>& nums)
    {

        int ret = 0;
        //异或整个数组
        for (int n : nums)
            ret ^= n;
        int div = 1;
        //div选择那两个不同数字的最低不同位
        //官方题解还要注意==的优先级大于&加括号
        //while ((div & ret) == 0)
        //	div <<= 1;
        //这里与官方题解不同，直接-1取反与运算，不用循环
        div = ret & (~(ret - 1));

        int a = 0, b = 0;
        //有了分辨两不同数字不同位的div，可以把两个不同数字分开成两组
        //两组分别取异或，那在数组中相同的数字就被除去了
        for (int n : nums)
            if (div & n)
                a ^= n;
            else
                b ^= n;
        return vector<int> {a, b};
    }
};

链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/zong-he-guan-fang-jie-shi-he-ge-wei-da-lao-jie-shi/