谈谈面试中的那些异或操作

最近一直在面试，也做了各种各样的手写算法题，大部分时候面试官想要考察的只是候选人对常见算法的了解程度。有些题很难，通过一些骚操作可以达到更高的性能，比如最长回文子串问题的最优解是马拉车算法，但是那些算法太偏门了，需要深厚的理论基础，我们不是专门做算法的，可能面试官自己也都不会，他出这道题一般是想你用动态规划来解。（当然了，你就用马拉车算法来做肯定会让面试官眼前一亮，留下深刻的印象）还有一种情况就是题目很简单，简单的一两个加减乘除都能做出来，这时候面试官想考察的肯定不是你会不会做算术，这时候一般都是考察候选人位运算玩的溜不溜。

我这两天就遇到这样的问题，今天就主要来谈谈异或运算在面试中的考察方式。

首先来看一道题：在一个非空整数数组中，除了一个数其它数都出现了两次，找出这个数。找出某个元素出现的次数，这个概念我们很熟悉呀，用哈希表就行了嘛！做一个循环，第一次遇到一个数的时候把它添加进哈希表，第二次遇到的时候移除，最后表里剩下来的那个就是我们要找的数。但是这样时间复杂度跟空间复杂度都在O(n)，而且这么做太简单了，怎么办，还有没有其它解法？

我们回想一下异或运算符的特性，两个操作数相同的话为0，任何数与0做异或的结果还是那个数。这样我们可以对数组里面的所有元素做异或操作，相同的两个数都会变成0，剩下的那个数跟0做异或结果还是那个数，最后我们就能得到我们的结果啦：

public static int findSingleNumber(int[] arr) {
        int num = 0;
        for (int i = 0; i < arr.length; i++) {
            num = num ^ arr[i];
        }
        return num;
    }

这时候时间复杂度还是O(n)，但是空间复杂度已经达到O(1)喽。

现在我们把难度升级一下，数组里存在两个唯一的数，我们该怎么把它找出来呢？还是按照之前的方法的话，我们只能得到n1^n2，拿不到独立的数的呀？难道还是哈希表大法好？

别急，我们知道n1跟n2是不同的数，那么在它们二进制的表示上，至少有一位是不一样的，那我们可以跟这一位上是1还是0把数组里的数分成两拨，这两个数肯定就在各自的分组里，然后相同的数也肯定在同一个分组里，再让这两拨数做异或运算，最后各自剩下来的不就是我们要的两个数了吗？

那么怎么找到这不一样的位置呢？还记得位运算的特性，0跟1做运算下来还是1，我们从右向左依次跟1做与运算，就能找到它了。

public static int[] findSingleNumbers(int[] nums) {
        // 得到做完异或操作之后的结果
        int n1xn2 = 0;
        for (int num : nums) {
            n1xn2 ^= num;
        }

        // 得到从右往左第一个是1的位
        int rightmostSetBit = 1;
        while ((rightmostSetBit & n1xn2) == 0) {
            rightmostSetBit = rightmostSetBit << 1;
        }
        int num1 = 0, num2 = 0;
        for (int num : nums) {
            if ((num & rightmostSetBit) != 0) // 一拨
                num1 ^= num;
            else // 另一拨
                num2 ^= num;
        }
        return new int[]{num1, num2};
    }

通过与运算，我们成功把数组分为两拨，然后再通过异或操作，得到我们的结果。

最后再来看看我遇到的这道题：每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101"，11 可以用二进制 "1011" 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。给你一个十进制数 N，请你返回其二进制表示的反码所对应的十进制整数。

我们再来回顾一下异或运算的特性：

1. 1⁰⁼⁰1=1
2. 0⁰⁼¹1=0
3. 任何数跟0异或都不变

从第一点我们可以知道一个数跟它的反码异或会得到一个各位都是1的数。我们就可以写出下面的公式：

number ^ complement = all_bits_set

那么：

number ^ number ^ complement = number ^ all_bits_set

然后：

0 ^ complement = number ^ all_bits_set

最终：

complement = number ^ all_bits_set

我们可以基于这条公式去求我们想要的结果了。现在的任务就变成如何获取这个all_bits_set了，也很简单，知道这个数占几位就好了。

public static int bitwiseComplement(int num) {
        // 计算位数
        int bitCount = 0;
        int n = num;
        while (n > 0) {
            bitCount++;
            n = n >> 1;
        }
        int all_bits_set = (int) Math.pow(2, bitCount) - 1;
        // 根据我们之前推导的公式
        return num ^ all_bits_set;
    }

时间复杂度根据位数决定，空间复杂度维持在O(1)。

总而言之，这类的题型其实很固定，一堆数里找特定的数啊，一个数的特定变形啊，我们只要关注异或运算那三种特性，那解题就没有太大障碍了。

关注我，一起讨论算法吧