题解 | #数组中只出现一次的两个数字#

两个相同的数字异或结果会抵消，0与任何数异或都等于该数本身。

如何将两个数异或的结果拆分成原来的两个数：找出两数某一个不同位，然后将原序列与其位相与，分出不同的两组

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindNumsAppearOnce(vector<int>& array) {
      int tmp = 0;
      int bit = 1;
      std::vector<int> res(2, 0);
      
      //  重点在于将两个数分开
      
      //  这里得到两个只出现一次的数异或出来的结果
      //  因为两个数不相同必定有一位是异或结果为1的
      for (int i = 0; i < array.size(); ++i) {
        tmp ^= array[i];
      }
      
      //  找出tmp即异或结果为1的那一位，就是两个数对应位取值不同的那一位
      while ((bit & tmp) == 0) {
        bit <<= 1;
      }
      
      //  因为两个数相应位不一样，而筛选是通过该位筛选，故两个数被分到不同的组别
      for (int i = 0; i < array.size(); ++i) {
        if ((bit & array[i]) == 0) {
          //  至于出现两次的数字，必定被分到同一组。所以抵消后就各自剩下出现一次的数字
          res[0] ^= array[i];
        } else {
          res[1] ^= array[i];
        }
      }
      
      if (res[0] < res[1]) {
        return res;
      } else {
        return {res[1], res[0]};
      }
    }
};