수조에서 한 번만 나오는 두 개의 수를 찾아내다

제목: 하나의 정형수조에서 두 개의 숫자를 제외하고 다른 숫자는 모두 두 번 나타났다.프로그램을 써서 이 두 개의 한 번만 나오는 숫자를 찾아내세요.요구 시간의 복잡도는 O(n)이고 공간의 복잡도는 O(1)이다.
분석: 이것은 매우 새로운 비트 연산에 관한 면접 문제다.
우선 우리는 이 문제의 간단한 버전을 고려했다. 한 수조에 한 숫자를 제외하고 다른 숫자는 모두 두 번 나타났다.프로그램을 써서 이 한 번만 나오는 숫자를 찾아내세요.이 문제의 돌파구는 어디에 있습니까?제목은 왜 한 숫자가 한 번, 다른 숫자가 두 번 나오는 것을 강조합니까?우리는 모든 숫자가 다르거나 그 자체가 0과 같다는 것을 생각했다.즉, 만약에 우리가 처음부터 끝까지 순서가 다르거나 수조 중의 모든 숫자를 순서대로 옮긴다면 최종 결과는 딱 한 번만 나오는 숫자이다. 왜냐하면 두 번 나오는 숫자가 모두 틀리거나 중간에서 상쇄되기 때문이다.
위의 간단한 문제 해결 방안이 생긴 후에 우리는 원시적인 문제로 돌아갔다.원수조를 두 자수로 나눌 수 있다면모든 하위 그룹에는 한 번만 나오는 숫자가 포함되어 있고, 다른 숫자는 두 번씩 나타난다.만약 이렇게 원수조를 분할할 수 있다면 앞의 방법에 따라 이 두 개의 한 번만 나오는 숫자를 각각 구하는 것이다.
우리는 여전히 처음부터 끝까지 이차적이거나 수조 중의 모든 숫자를 순서대로 나눈다. 그러면 최종적으로 얻은 결과는 한 번만 나타나는 두 개의 숫자의 이차적이나 결과이다.다른 숫자가 두 번이나 나왔기 때문에 이변에서 모두 상쇄되었다.이 두 숫자가 틀림없이 다르기 때문에 이 이변 또는 결과는 틀림없이 0이 되지 않을 것이다. 즉, 이 결과 숫자의 2진법 표시 중 적어도 한 명은 1이다.우리는 결과 숫자에서 첫 번째 1의 위치를 찾아 N위로 기록했다.현재 우리는 N위가 1인지 아닌지를 기준으로 원수조의 숫자를 두 개의 자수로 나눈다. 첫 번째 자수조의 모든 숫자의 N위는 1이고 두 번째 자수조의 모든 숫자의 N위는 0이다.
현재 우리는 이미 원수조를 두 개의 자수조로 나누었는데, 각 자수조는 한 번만 나오는 숫자를 포함하고, 다른 숫자는 모두 두 번 나타났다.그래서 지금까지 우리는 모든 문제를 해결했다.
코드는 다음과 같습니다.

#include <iostream>
using namespace std;

// Find the index of first bit which is 1 in num (assuming not 0)
unsigned int FindFirstBitIs1(int num)
{
 int indexBit = 0;
 while (((num & 1) == 0) && (indexBit < 32))
 {
   num = num >> 1;
   ++ indexBit;
 }
 return indexBit;
}

// Is the indexBit bit of num 1?
bool IsBit1(int num, unsigned int indexBit)
{
 num = num >> indexBit;
 trturn (num & 1); 
}

// Find two numbers which only appear once in an array
// Input: data - an array contains two number appearing exactly once,
void FindNumsAppearOnce(int data[], int length, int &num1, int &num2)
{
      if (length < 2)    return;
      // get num1 ^ num2
      int resultExclusiveOR = 0;
      for (int i = 0; i < length; ++ i)
            resultExclusiveOR ^= data[i];
 
      // get index of the first bit, which is 1 in resultExclusiveOR
      unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR); 
      num1 = num2 = 0;
      for (int j = 0; j < length; ++ j)
      {
            // divide the numbers in data into two groups,
            // the indexOf1 bit of numbers in the first group is 1,
            // while in the second group is 0
            if(IsBit1(data[j], indexOf1))
                  num1 ^= data[j];
            else
                  num2 ^= data[j];
      }
}

int main()
{
  int a[8] = {2,3,6,8,3,2,7,7};
  int x,y;
  FindNumsAppearOnce(a,8,x,y);
  cout<<x<<"\t"<<y<<endl;
  return 0;
}