【位运算，异或】“只出现一次的数字” 的一类问题解决方法

问题的题目全部来自leetcode,题号已给出

异或的性质

两个数字异或的结果a^b是将 a 和 b 的二进制每一位进行运算，得出的数字。 运算的逻辑是如果同一位的数字相同则为 0，不同则为 1

异或的规律

1.任何数和本身异或则为0

2.任何数和 0 异或是本身

3.异或满足交换律。 即 a ^ b ^ c ，等价于 a ^ c ^ b

注意交换律

136. 只出现一次的数字

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int i = 0 ;i<nums.length;i++){
            res ^= nums[i];
        }
        return res;
    }
}

举例解释：

17 ^ 19 ^ 17  =  17 ^ 17 ^ 19  = 19

137. 只出现一次的数字 II

题解：暂时没看懂，放在这
https://leetcode-cn.com/problems/single-number-ii/solution/zhi-chu-xian-yi-ci-de-shu-zi-ii-by-leetcode/

面试题56 - I. 数组中数字出现的次数

由于数组中存在着两个数字不重复的情况，我们将所有的数字异或操作起来，最终得到的结果是这两个数字的异或结果：(相同的两个数字相互异或，值为0)) 最后结果一定不为0，因为有两个数字不重复。

演示：

4 ^ 1 ^ 4 ^ 6 => 1 ^ 6

6 对应的二进制： 110
1 对应的二进制： 001
1 ^ 6  二进制： 111

此时我们无法通过111（二进制），去获得110 和001。
那么当我们可以把数组分为两组进行异或，那么就可以知道是哪两个数字不同了。
我们可以想一下如何分组：

重复的数字进行分组，很简单，只需要有一个统一的规则，就可以把相同的数字分到同一组了。例如：奇偶分组。因为重复的数字，数值都是一样的，所以一定会分到同一组！

此时的难点在于，对两个不同数字的分组。

此时我们要找到一个操作，让两个数字进行这个操作后，分为两组。
我们最容易想到的就是 & 1操作， 当我们对奇偶分组时，容易地想到& 1，即用于判断最后一位二进制是否为1。来辨别奇偶。
你看，通过 &运算来判断一位数字不同即可分为两组，那么我们随便两个不同的数字至少也有一位不同吧！
我们只需要找出那位不同的数字mask，即可完成分组（ & mask）操作。

为了操作方便，我们只去找最低位的mask: (mask就是上面演示的k)

num1: 101110    110     1111
num2: 111110    001     1001
mask: 010000    001     0010

由于两个数异或的结果就是两个数数位不同结果的直观表现，所以我们可以通过异或后的结果去找最低位的mask！
通过mask的最低为将两个不同的数字分类到两个不同的组，对这两个组分别异或运算，得到每个组中只出现1次的数字

class Solution {
    public int[] singleNumbers(int[] nums) {
        //用于将所有的数异或起来
        int k = 0;
        
        for(int num: nums) {
            k ^= num;
        }
        
        //获得k中最低位的1
        int mask = 1;

        while((k & mask) == 0) {
            mask <<= 1;
        }
        
        int a = 0;
        int b = 0;
        
        for(int num: nums) {
            if((num & mask) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        
        return new int[]{a, b};
    }
}

练习：

面试题56 - II. 数组中数字出现的次数 II

645. 错误的集合