By

文章目录

//这样的数组：只有两个数字只出现一次，其他数字出现两次。输出只出现一次的数字
//如果是只出现一次的数字有一个，那么异或整个数组元素，得到的结果恰好就是那个单独的元素
//所以把原始数组分成两个子数组。每个子数组只包含一个只出现一次的数字。
//先异或整个数组元素，得到不是0的结果，化成二进制，找到第一个1的位置index，然后把原数组按照这个index是不是1来分开。

#include <iostream>

using namespace std;

//最右边1的位置
unsigned int FindFirst1Bit(int num);
//从右边数起的indexBit位是不是1
bool IsBit1(int num,unsigned int indexBit);
//主要实现
void FindNumberAppearOnce(int *data,int length){
    if(data==NULL || length<2)//,int &num1,int &num2
        return ;
    int resExclusiveOr=0;
    for(int i=0;i<length;i++){
        resExclusiveOr^=data[i];
    }
    unsigned int indexOf1=FindFirst1Bit(resExclusiveOr);//根据异或结果找到右边起第一个1
    int num[2]={0};
   // num1=num2=0;//两个只出现一次的数字
    for(int j=0;j<length;j++){
        if(IsBit1(data[j],indexOf1))
            num[0]^=data[j];
        else
            num[1]^=data[j];
    }
    for(int i=0;i<2;i++)
        cout<< num[i]<<" ";
}
//找到最右边第一个1的位置
unsigned int FindFirst1Bit(int num){
    int indexBit=0;
    while(((num&1)==0) && (indexBit<8 * sizeof(int))){
        num=num>>1;
        ++indexBit;
    }
    return  indexBit;
}
//从右边起indexBit位是不是1
bool IsBit1(int num,unsigned int indexBit){
    num=num>>indexBit;
    return (num&1);
}
int main()
{
    int data[]={2,4,3,6,3,2,5,5};
   // int a,b;
    FindNumberAppearOnce(data,8);
  //  cout<<a<<" "<<b;
    return 0;
}
文章目录