只出现一次的数

题目: 一个数组中, 有两个不同的数出现了一次, 其他的数都恰好出现了两次, 找出这两个数.

原题链接: 260. 只出现一次的数字 III - 力扣（Leetcode）

使用位运算解题需要几点前置知识:

首先, 第一点, 对于任意一个数N, 一定满足: N ^ N == 0, 0 ^ N == N;

第二, 位运算异或满足交换律和结合律;

根据第一第二就能推出, 位运算异或具有复原性, 即对于任意两个数M和N一定满足: M^N^N == M;

那么, 若定义一个变量eor对数组中的每一个值, 依次进行异或运算, (假设两个不同的数分别为a和b)则eor的值一定等于a^b

现在有了a ^ b的值eor, 怎么求出具体a和b的值分别是多少呢?

先分析eor的值有什么特点, 因为a与b不等, 所以eor一定不为0 ,

所以其二进制一定有一位为1, 在那一位上, 一个为0, 一个为1(这很重要)

例: 比如 a=1011, b=0101, eor=a^b= 1110

可以发现, eor为1的位上, a和b都是一个为0一个为1

为什么要找那一位1?

找到那一位1, 假设为rightOne, 那么一定有rightOne & a == 0 和 rightOne & b != 0, 这样便可以找出两个数的其中一个.

假设找到的是a, 那么b 可以通过 a ^ eor获得. (为什么? 因为eor==a^b 所以 a^eor等于 a^a^b , 两个a消掉, 就等于b了)

找到最低位rightOne = 0010,可以得到 0010 & a !=0, 那么用0再对a异或就可以得到a了

(虽然数组中可能会有很多数, 但是其他数都是只有两个, 经过两次异或运算还是原数, 并不影响, 所以可以想象数组中只有两个数, a和b)

怎么找到那一位1呢?

通常使用eor & (~eor + 1)找出最低位1 (因为找最低位最方便, 并不是一定要最低位)

一个数的负数的二进制, 等于其反码加一(这就像1+1==2一样), 所以eor & (~eor + 1)也可写为eor & -eor

看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] singleNumber(int[] nums) {
    int eor = 0;
    for (int num : nums) {
        eor ^= num;
    }
    // 两个数不相同, 所以a^b !== 0, 即其二进制必定有一位 是 1
    int rightOne = eor & -eor;  // 提取最低位的 1
    int onlyOne = 0;
    for (int num : nums) {
        // 条件也可写为 (num & rightOne) != 0
        if ((num & rightOne) == 0) {
            onlyOne ^= num;
        }
    }
    // 与eor异或, 找到另外一个数
    return new int[]{onlyOne, eor ^ onlyOne};
}