找出n个数中出现了奇数次的两个数

如果是找只出现了奇数次的一个数，那么我们从头异或一遍就可以。那么如何找出现了奇数次的两个数呢？

首先我们还是从头异或一遍，然后结果肯定不为0，对于异或出来的结果，如果这个数的某一位是1，说明出现了奇数次的那两个数在这一位上一个为0，一个为1。所以我们可以根据这个条件将原数组分为两个数组分别异或。

 #include<bits/stdc++.h>

 using namespace std;

 #define pb(x) push_back(x)

 #define ll long long

 #define mk(x, y) make_pair(x, y)

 #define lson l, m, rt<<1

 #define mem(a) memset(a, 0, sizeof(a))

 #define rson m+1, r, rt<<1|1

 #define mem1(a) memset(a, -1, sizeof(a))

 #define mem2(a) memset(a, 0x3f, sizeof(a))

 #define rep(i, a, n) for(int i = a; i<n; i++)

 #define ull unsigned long long

 typedef pair<int, int> pll;

 const double PI = acos(-1.0);

 const double eps = 1e-;

 const int mod = 1e9+;

 const int inf = ;

 const int dir[][] = { {-, }, {, }, {, -}, {, } };

 int a[];

 int main()

 {

     int n;

     while(~scanf("%d", &n)) {

         int tmp = ;

         for(int i = ; i<n; i++) {

             scanf("%d", &a[i]);

             tmp^=a[i];

         }

         int pos = -;

         for(int i = ; ; i++) {

             if(tmp&(<<i)) {

                 pos = i;

                 break;

             }

         }

         int ans1 = , ans2 = ;

         for(int i = ; i<n; i++) {

             if(a[i]&(<<pos))

                 ans1^=a[i];

             else

                 ans2^=a[i];

         }

         printf("%d %d\n", ans1, ans2);

     }

     return ;

 }