首页 > 代码库 > 一串数字中有两个只出现一次的数字其余都是成对相同,求这两个数

一串数字中有两个只出现一次的数字其余都是成对相同,求这两个数

当然如果这个问题是只有一个不同的数,其他数字成对相同,那么就是把所有数字异或就得出这个数了

这次是有两个只出现一次的数字,其他数字都成对相同

1)先把所有数都异或得到数t

2)算出t的二进制第一个1的位置flag

3)将所有数根据二进制flag位置是否为1分成两组b1[],b2[] (此时每组数字的个数一定是奇数)

4)将b1组异或得到ans1,将b2组异或得到ans2

#include<iostream>
#include<stdio.h>
using namespace std;
#define isset(a,n) a&(1<<(n))
#define N 1000
int main(){
    int t,c,i,b[N],b1[N],b2[N],flag,cou1,cou2,ans1,ans2;
    while(cin>>c,c){
        if(c%2!=0){
            cout<<"c必须为偶数"<<endl;
            continue;
        }
        cin>>b[0];
        t=b[0];
        for(i=1;i<c;i++){
            cin>>b[i];
            t^=b[i];
        }
        flag=0;
        for(i=0;i<32;i++)
            if(isset(t,i)){
                flag=i;
                break;
            }
        cou1=cou2=0;
        for(int i=0;i<c;i++){
            if(isset(b[i],flag))
                b1[cou1++]=b[i];
            else
                b2[cou2++]=b[i];
        }
        ans1=b1[0];
        ans2=b2[0];
        for(i=1;i<cou1;i++)
            ans1^=b1[i];
        for(i=1;i<cou2;i++)
            ans2^=b2[i];
        cout<<ans1<<" "<<ans2<<endl;

    }

}