题目描写叙述：

一个整型数组里除了两个数字之外，其它的数字都出现了两次。

编敲代码找出这个两个仅仅出现一次的数字。要求时间复杂度O(n)，空间复杂度O(1).

如 {2,4,3,6,3,2,5,5}，输出{4,6}

---

解析：

空间复杂度为O(1)断绝了用hash-table的思路，时间复杂度O(n)断绝排序的思路。

怎样推断一个数字出现2次呢？

• 计数
• 异或：假设出现2次。随意数字和自己异或都为0

异或的性质：

不论什么数字和 0 异或。都为它本身。

随意数字和自己异或都为0。

由于成对出现的元素异或结果为 0，那么整个数组的异或结果为仅仅出现 一次 的元素的异或结果。

由于存在2个出现一次的元素。所以终于结果是2者的异或结果。那么怎样分离出这2个元素？

这2个出现一次的元素。不相等，那么异或的结果不等0。即2进制表示肯定有1位是不为 0 的（都为0，说明相等），等价于这2个元素的此位是不相等的，我们依据该位，能够将整个数组分为2部分，该位为 1 的分为 1部分，为 0 的一部分。

此时，2个仅仅出现一次的元素被分离开，而成对出现的元素每一位都相等，因此它们也是成对的分布在2个部分数组中。然后我们分别对这2部分计算异或的结果，就可以得到 2 个仅仅出现一次的数字。

注意： &, |, ~ 的优先级小于 ==，>, < ，注意加括号。

#include 
      
       using namespace std;int FindBitIndexofOne(int number) {    unsigned int index = 0;    // 如 0x0010 返回 1, 注意 & 的优先级小于 ==，必须有（）    while ((number & 0x01) == 0 && index < 8 * sizeof(int)) {        number = number >> 1;        index++;    }    return index;}bool IsOneBit(int number, unsigned int index) {    while (index) {        number = number >> 1;        index--;    }    if (number & 0x01)        return true;    else        return false;}bool FindNumApperOnce(int nums[], int length, int &result1, int &result2) {    if (nums == NULL || length < 2)        return false;    int XORResult = 0;    for (int i = 0; i < length; i++)        XORResult ^= nums[i];    unsigned int oneBitIndex = FindBitIndexofOne(XORResult);    result1 = 0, result2 = 0;    for (int i = 0; i < length; i++) {        if (IsOneBit(nums[i], oneBitIndex))            result1 ^= nums[i]; // 标志位是 1 的数组        else            result2 ^= nums[i];// 标志位是 0 的数组    }    return true;}int main() {    int nums[] = { 1,3,2,4,6,42,4,42,1,3 };    int result1, result2;    if (FindNumApperOnce(nums, sizeof(nums) / sizeof(nums[0]), result1, result2))        cout << result1 << " " << result2 << endl;}