问

给定整数数组，一个数出现一次，其他每个数都出现两次。
 两个数出现一次，其他每个数都出现两次。要求时间复杂度位O(n),空间复杂度位O(1)。
两个相同的整数异或会抵消，不同的整数会根据二进制0，1获得新的整数。
如果只有一个数出现一次，数组所有数异或运算最终剩下的即为出现一次的。
如果有两个数只出现一次，最终剩下的整数为这两个数异或产生的整数，（int类型长度32位，long长度64）在其范围内，
二进制中至少有一个位异或的结果为1，获其下标，判断整数在此下标的二进制是为1还是0，便分出两组数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

private int[] singleNumber(int[] nums) {
        int[] res = new int[2];

        int num = 0;
        for (int i : nums) {
            num ^= i;
        }
//        如果只有一个不同
//        res[0] = num;

        //如果两个不同
        int index = bit1(num);
        for (int i : nums) {
            if (isBit1(index, i)) {
                res[0] ^= i;
            } else {
                res[1] ^= i;
            }
        }

        return res;
    }

    private boolean isBit1(int index, int i) {
        i >>>= index;
        return (i & 1) == 1;
    }
    private int bit1(int num) {
        int index = 0;
        while ((num & 1) == 0 && index < 32) {
            num >>>= 1;
            index++;
        }
        return index;
    }

位操作符

与运算 都为1才位1
1&1 = 1
1&0 = 0
0&0 = 0
或运算 都为0才位0
1|1 = 1
1|0 = 1
0|0 = 0
非运算 相同都为0
1^1 = 0
1^0 = 1
0^0 = 0