数组中只出现一次的数字
C++，位运算，按位异或和按位与。
首先就是要知道，一个数a和初始为0的数b一次异或(b = a ^ b)，会得到b = a，两次异或，则b = 0。所以如果一个序列中，只有一个元素a出现次数为奇数，其他序列出现次数为偶数，将数b = 0与序列中所有值进行异或运算，则最终b = a。
这道题中给的序列中有两个出现了一次的元素a、b，其他都出现了两次。我们可以把这个序列分成两个子序列，每个子序列中包含一个出现一次的元素a和，其他都是出现了2次，这样分别异或运算就能得到答案了。
如何给序列分割呢？
- 首先定义一个变量a_b = 0，与序列中所有元素都进行异或
^运算； - 最后得到的a_b一定是等于a ^ b；
- 然后再找到a_b的二进制中第一个为1的位，假设这个位为i，这个位对于整个序列具有如下特点：
- 如果a的i位为1，则b的i为一定为0，反之也成立，因为这个1是a和b异或的结果；
- 相同的数的i位一定是相同的；
- 基于上述特点，可以用按位与将序列分成两个子序列，且这两个子序列中一定是符合“只有一个元素出现了1次，其他元素都出现了2次”的特征。
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
int a_b = 0;
for (int &it : data) a_b ^= it;
int i = 1;
for (; !(i & a_b); i <<= 1) ;
vector<int> v1, v2;
for (int &it : data) {
if (i & it)
v1.push_back(it);
else
v2.push_back(it);
}
a_b = 0;
for (int &it : v1) a_b ^= it;
*num1 = a_b;
a_b = 0;
for (int &it : v2) a_b ^= it;
*num2 = a_b;
}
};
