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

题目分析

根据异或性质：

假设要找的两个数为a, b;数组中所有数逐个异或，即x1 ^ x2 ^ y1 ^ y2 ^ …… ^ a ^ b, 最终成对的数根据归零率变成0，再根据恒等率剩下的一定是a ^ b

从a ^ b中可以获得某种信息：因为a != b所以a ^ b一定不为0，它其中某一位为1，根据这一位可以把a和b区分开（因为异或是两个输入不同时为1，相同时为0）

a & (-a)可以找到最右侧的1

(-a) is equal to ~a+1.
a & (~a + 1) is a trick to extract the lowest set bit of a.

根据这位的不同，可以将所有数字分为两组，每组分别异或可得答案

代码实现

import java.util.*;
public class Solution {

    public int[] FindNumsAppearOnce (int[] array) {
        int eor = 0;

        // 设这两个数是a, b   （其中a < b）
        // 异或消掉出现两次的数，得到eor = a ^ b
        for(int num : array) {
            eor ^= num;
        }

        // 找到a ^ b的任意一个1，用来区分a和b
        // 找到最右边的1
        int rightOne = eor & (~eor + 1); 
        //int rightOne = eor & (-eor);
        int a_b = 0;

        // 根据最右边的1将数组分为两组，a b一定在不同的组别
        // 其中一组异或可以得到a或b中的一个
        for(int num : array) {
            if((num & rightOne) == 0) {
                a_b ^= num; // a_b可能是a也可能是b
            }
        }

        int a = a_b < (a_b ^ eor) ? a_b : (a_b ^ eor); // 小的是a
        int b = a ^ eor; // 根据确定下来的a得到剩下的a ^ (a ^ b) = b

        return new int[]{a, b};
    }
}