比如:{1,3,4,2,7,3,1,2}
第一步,全部异或的结果也就是4异或7的结果,记作s,0100^0111=0011。
原理1:相同的数异或结果为0,两个不同的数异或结果不为0,那么必有某个位为1,找出最低位的1.
第二步:上一步的结果s和0001按位与,看最低位是否为1,不是就把1左移一位,再和s相与,即s&0010,s^0100, s^1000,总能找到一个位为1.
原理2:1&1=1;0&0=0,1&0=0,0&1=0;
第三步,根据找到的这个位为0还是1,将原数组分为两类。然后各自全部异或可得到一个只出现一次的数。
这里s的最低位为1,据此将原数组分为{1,3,7,3,1}和{2,4,2}分别全体异或即可得到7和4,再比较大小返回
int* FindNumsAppearOnce(int* array, int arrayLen, int* returnSize ) {
     int n = arrayLen, s = 0, i = 0;
     for(i = 0; i < n; i++)
        s = s ^ array[i];  //结果为只出现一次的两个数的异或结果
    int mask = 1;  //为了确定结果s中哪个位上为1,从最低为开始找
    while((s & mask) == 0)   //按位与结果为0表示s在mask为1的那个位上不是1
        mask = mask << 1;  //从最低位开始验证,没找到1就往高位继续找
    int a = 0, b = 0;  //找到之后分为两组,分别找出那一个只出现一次的
    for(i = 0; i < n; i++){
        if((mask & array[i]) == 0)
           a = a ^ array[i];
        else
           b = b ^ array[i];
    }
    if(a > b)
        array[0] = b, array[1] = a;
    else
        array[0] = a, array[1] = b;
    *returnSize = 2;
    return array;
}