找出数组中两个只出现一次的数字

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

2,分析:
(1)各个元素依次异或,得到两个数字异或的结果 val.
(2)找到val的一个bit为1的位.
(3)根据上述比特位1或0将原来的数组分成两组.
(4)每组异或,即可得到要求的数.

3,实例代码:

#include <iostream>
#include <cstring>
using namespace std;


void findOnce(int data[], int n, int &num1, int &num2)
{
    if (n < 5)
        return;
    int r1 = 0;
    for (int i = 0; i < n; i++)
        r1 ^= data[i];
    int bitNum = 0;
    while ( !(r1 & 0x1))
    {
        r1 >>= 1;
        ++bitNum;
    }

    int  flag = (1 << bitNum);
    num1 = 0;
    num2 = 0;
    for (int i = 0; i < n; i++)
    {
        if ( data[i] & flag)
            num1 ^= data[i];
        else
            num2 ^= data[i];
    }
}

int main()
{
    int data[] = {1,1,2,3,3,4,5,5};
    int num1, num2;
    findOnce(data, sizeof(data)/sizeof(data[0]), num1, num2);
    cout << num1 <<" " << num2 << endl;
    return 0;
}