数组中有两个数字出现了奇数次

思路

1）首先，数组元素为32位的整型，限制了不能开1<<31-1那么大的数组进行hash
2）所以只能考虑，利用位运算中，异或运算的性质

异或的特性：0 ^ X = X，X ^ X = 0

（正好和 奇，偶，对上了）
1）先将所有数组中的所有数字进行异或，则最后的结果bitsum为两个出现奇数次的数的异或。
2）然后用“比特探针（随便取的名字）”探测到bitsum第一个为1的位置。
3）将探测结果，以这位是否为1可以将数组的元素分为两部分
显然，两个奇数分别分布在这两部分。
4）分别对两部分依次异或
5）由于，无法单单的经过探测结果，区分结果大小，所以最后还要比大小

代码

#include<bits/stdc++.h>
using namespace std;

const int maxn=100000+5;
int test[maxn]={0};

int main()
{
    int n;
    while(cin>>n)
    {
        int bitsum=0;//所有元素的异或
        for(int i=0;i<n;++i)
        {
            cin>>test[i];
            bitsum^=test[i];
        }

        //比特探针，随便取的名字,获取bitsum右边第一个比特为1的位置
        int tag=1;
        while(0==(bitsum&tag))
        {
            tag<<=1;
        }

        //存放各自两部分进行异或得到出现奇数次的两个数
        int left=0,right=0;
        for(int i=0;i<n;++i)
        {
            if(tag&test[i])
            {
                left^=test[i];
            }
            else
            {
                right^=test[i];
            }
        }

        //位运算交换
        if(left>right)
        {
            left^=right;
            right^=left;
            left^=right;
        }

        cout<<left<<" "<<right<<endl;

    }

    return 0;    
}