找到奇数次的两个数

实现思路

异或理解：无进制位相加，那么便可以推导出其特性

1. 把数组异或一遍，假设奇数次的两个数分别为a、b，那么该流程完毕后，结果位a^b
2. 计算得出a^b这个结果第一位为1的位置，具体算法为：对a^b取反在加1，看如下示例说明：

// eor = a ^ b; 8 ^ 4
// eor != 0;
// eor必然有一位为1，找到最右边为1的数字
//  8     -> 0 0 0 0 1 0 0 0
//  4     -> 0 0 0 0 0 1 0 0
//  8 ^ 4 -> 0 0 0 0 1 1 0 0
/*
 * eor = 0 0 0 0 1 1 0 0
 * 则right one = eor & （~eor + 1）
 * 即
 * eor        ：      0 0 0 0 1 1 0 0
 * ~eor       ：      1 1 1 1 0 0 1 1
 * ~eor + 1   ：      1 1 1 1 0 1 0 0
 * right_one  :       0 0 0 0 0 1 0 0
 */

3. 此时遍历数组，对rightOne做与运算，其等于0的数字即为那一位不为1的数，这些数中包括那一位不为1的奇数次数字和其他那一位不为1的偶数次数字
4. 针对符合第三步的数字均作异或运算，那么最终只会得到其中一个奇数次数字，偶数次的异或之后都为0了
5. 另外一个奇数次显而易见了，用第一步的数字异或第四步的数字就是另外一个奇数次数

TALK IS CHEAP

@Test
public void printOddTimesNum2() {
    int[] arr = {1, 1, 2, 2, 8, 8, 8, 4, 4, 4};

    int eor = 0;

    for (int k : arr) {
        eor ^= k;
    }

    // eor = a ^ b; 8 ^ 4
    // eor != 0;
    // eor必然有一位为1，找到最右边为1的数字
    //  8     -> 0 0 0 0 1 0 0 0
    //  4     -> 0 0 0 0 0 1 0 0
    //  8 ^ 4 -> 0 0 0 0 1 1 0 0
    /*
	* eor = 0 0 0 0 1 1 0 0
	* 则right one = eor & （~eor + 1）
	* 即
	* eor        ：      0 0 0 0 1 1 0 0
	* ~eor       ：      1 1 1 1 0 0 1 1
	* ~eor + 1   ：      1 1 1 1 0 1 0 0
	* right_one  :       0 0 0 0 0 1 0 0
	*/
    int rightOne = eor & (~eor + 1);
    // 此时遍历数组，arr[i] & right_one == 0 则可以筛选出所有那一位不是1的数，其中包括该位置【不为】1的偶数次的数字和奇数次数的其中一个数字
    int result = 0;
    for (int j : arr) {
        if ((j & rightOne) == 0) { // 此处也可& rightOne，则筛选出该位置【为】1的偶数次的数字和奇数次数的其中一个数字
            result ^= j; // 偶数次的异或之后为0，所以只会剩下筛选出一侧的奇数次的数
        }
    }
    System.out.println("结果为：a = " + result + " b = " + (eor ^ result));
}