LeetCode260.只出现一次的数字 III（位运算）
题目传送门
一、题目解析
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
题意很简单不再赘述，比较容易想到的一种方法是用哈希表来存储每个数字出现的次数，然后遍历一边哈希表找到两个只出现一次的即可，但是本题还要求仅使用常数空间复杂度来实现，此时就需要用到另一种方法——位运算。
二、位运算
首先我们观察数组，除了两个仅出现一次的元素外，其他所有元素都是出现两次的，我们可以想到异或运算的性质——两个相同的数异或结果为0，且任何数和0异或都不变，那么我们可以将数组全部元素异或起来，得到的最终结果即为两个仅出现一次的元素的异或记为x。
得到两元素的异或后，我们进一步考虑，因为两元素不同，那么x肯定不会为0，至少有一位是为1，根据异或运算的性质，只有当两数不同时异或结果才会为1，我们可以通过x&-x求得x中最低位的1（求解原理在文章最后）记为y。
至此，我们可以得知要求的两个数在第y位上数字不同，一个为0，一个为1。我们可以将原数组分成两部分，分别是第y位上数字为0，和第y位上数字为1，此时这两部分分别包含两解，以及若干个两两相同的数。将这两部分分别异或，即可求得两解。
三、代码
注意溢出问题
class Solution
{
public:
vector<int> singleNumber(vector<int> &nums)
{
int x = 0;
for (int i : nums)
{
x ^= i;
}
int y = x & -x;
int a = 0, b = 0;
for (int i : nums)
{
if (i & y)
a ^= i;
else
b ^= i;
}
vector<int>ret;
ret.push_back(a);
ret.push_back(b);
return ret;
}
};
关于x&-x的结果为何是最低位1，可参考如下博客
https://blog.csdn.net/oyoung_2012/article/details/79932394
