zrlong 的个人博客

写在前面的位运算知识点

与运算

按位与运算符（&）

参加运算的两个数，按二进制位进行“与”运算。

运算规则：只有两个数的二进制同时为1，结果才为1，否则为0。（负数按补码形式参加按位与运算）

即 0 & 0= 0 ，0 & 1= 0，1 & 0= 0， 1 & 1= 1。

例：3 &5 即 00000011 & 00000101 = 00000001 ，所以 3 & 5的值为1。

或运算

按位或运算符（|）

参加运算的两个数，按二进制位进行“或”运算。

运算规则：参加运算的两个数只要两个数中的一个为1，结果就为1。

即 0 | 0= 0 , 1 | 0= 1 ， 0 | 1= 1 , 1 | 1= 1 。

例：2 | 4 即 00000010 | 00000100 = 00000110 ，所以2 | 4的值为 6 。

异或运算

异或运算符（^）

参加运算的两个数，按二进制位进行“异或”运算。

运算规则：参加运算的两个数，如果两个相应位为“异”（值不同），则该位结果为1，否则为0。

即 0 ^ 0=0 ， 0 ^ 1= 1 ， 1 ^ 0= 1 ， 1 ^ 1= 0 。

例： 2 ^ 4 即 00000010 ^ 00000100 =00000110 ，所以 2 ^ 4 的值为6 。

大家都做过这种题吧，在数组每个数都出现两次，但是有一个数出现了一次，让我们去找到这个数。当然我们可以遍历数组计数。但是更简单的是异或运算，我们只需从头到尾遍历数组，全部做异或运算，最后的结果就是我们要找的数。

题目

剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣（LeetCode） (leetcode-cn.com)

今天做到了另一道题，还是跟上述的题目差不多，但是数组中有两个出现了一次的数，我们怎么找到呢？而且题目要求时间复杂度是O(n)，空间复杂度是O(1)。因此我们不能再简单的使用遍历计数，那我们就应该想到位运算。那么问题来了，位运算到最后结果是两个数相异或的结果，我们怎么把他们拆开呢？

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

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

思路

我们无法把111拆分为110和001，我们可以把数组分成两组进行异或，每组的结果就是答案。

• 对重复的数我们进行分组是很简单的，指定一个分组规则就可以把相同的数分为一组。因为数字是重复的，必然会分到一组。
• 难点在于如何将两个不同的数分到不同的组中。异或的特点就是不同为1，在数组异或一遍之后结果就是我们要找的两个数的异或结果，那么这个数中至少存在一位上为1。那么我们就可以根据这个数1上的任意一位1来进行分组。这个操作是什么呢？就是&1。数组中&1结果为0的分为一组，不为0的是另一组，分别异或，我们就能得到结果了。为了方便，我们直接选取最低为的1即可。

代码

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

        //mask = k & (-k) 这种方法也可以得到mask，具体原因百度 哈哈哈哈哈
        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};
    }
}