程序员面试题精选100题（34）-数组中只出现一次的数字[算法]

            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];

      }

}

 

///////////////////////////////////////////////////////////////////////

// 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;

      }