offer_56

//面试题56：数组中数字出现的次数
//题目1：数组中只出现一次的两个数字
void FindNumsApperOnce(int data[],int length,int* num1,int* num2)
{
  if(data==nullptr || length<2)
    return;
  
  int resultExclusiveOR=0;
  for(int i=0;i<length;++i)
    resultExclusiveOR^=data[i];
    
   unsigned int indexOf1=FindFirBitIs1(resultExclusiveOR);
   
   *num1=*num2=0;
   for(int j=0;j<length;++j){
    if(IsBit1([data],indexOf1))
      *num1^=data[j];
    else
      *num2^=data[j];
   }
}

unsigned int FindFirstBitIs1(int num)
{
  int indexBit=0;
  while(((num&1==0)&&(indexBit<8*sizeof(int))){
    num=num>>1;
    ++indexBit;
  }
  return indexBit;
}

bool IsBit1(int num.unsigned int indexBit)
{
  num=num>>indexBit;
  return (num&1);
}

//题目2：数组中只出现一次的数字
int FindNumberApperingOnce(int numbers[],int length)
{
  if(numbers==nullptr || length<=0)
    throw new std::exception("Invalid input");
    
  int bitSum[32]={0};
  for(int i=0;i<length;++i){
    int bitMask=1;
    for(int j=31;j>=0;--j){
      int bit=numbers[i]&bitMask;
      if(bit!=0)
        ++bitSum[j];
      bitMask=bitMask<<1;
    }
  }
  
  int result=0;
  for(int i=0;i<32;++i){
    result=result<<1;
    result+=bitSum[i]%3;
  }
  return result;
}