盘点：这 7 道位运算面试题，哪一题你能做对？

使用hashmap来求解的方式，实在是没什么可说的。

 1func singleNumber(nums []int) int {
 2    m := make(map[int]int)
 3    for _, k := range nums {
 4        //如果是其他语言，请注意对应的判空操作！
 5        m[k]++
 6    }
 7    for k, v := range m {
 8        if v == 1 {
 9            return k
10        }
11    }
12    return 0
13}

当然，这里还有一种数学解法：

原理：[A,A,A,B,B,B,C,C,C] 和 [A,A,A,B,B,B,C]，差了两个C。

也就是说，如果把原数组去重、再乘以3得到的值，刚好就是要找的元素的2倍。举个例子：

利用这个性质，进行求解：（python代码如下，这里要注意的是，使用int可能会因为超出界限报错）

1class Solution:2    def singleNumber(self, nums: List[int]) -> int:3        return int((sum(set(nums)) * 3 - sum(nums)) / 2)

效果不错，但是仍然使用了额外空间。所以我们还是得使用位运算。对于“每个其余元素，均出现了二次”之所以可以使用“异或”进行求解，原因是因为“异或”操作可以让两数相同归 0。那对于其余元素出现三次的，是不是只要可以让其三者相同归 0，就能达到我们的目的呢？

这个思想可能比较简单，但是要让大家理解，还是有一定难度。如果大家准备好了，可以开始往下看。我看过leetcode上的题解，很多都是直接扔出来一个公式，其实讲的我认为并不是特别的清楚。所以我打算先把本题退化到“每个其余元素，均出现二次”的case来进行分析一下。

假如我们有 [21,21,26] 三个数，是下面这样：

回想一下，之所以能用“异或”，其实我们是完成了一个 同一位上有2个1清零 的过程。上面的图看起来可能容易，如果是这样：

那对于“每个其余元素，均出现了三次”也是一样，如果我们可以完成 一个同一位上的三个1清零的过程，也就是 a ？a ？a = 0，问题则迎刃冰解。那因为各语言中都没有这样一个现成的方法可以使用，所以我们需要构造一个。（想象一下，位运算也是造出来的对不对？）

如何构造，这里先说第一种方法（注意，到这里我们的问题已经转化成了定义一种 a ? a ? a = 0 的运算），观察一下“异或”运算：

1^1=0

1^0=1

0^1=1

是不是可以理解为，其实就是二进制的加法，然后砍掉进位呢？

砍掉进位的过程，是不是又可以理解为对 2 进行取模，也就是取余。到了这里，问题已经非常非常明确了。那我们要完成一个 a ? a ? a = 0 的运算，是不是其实就是让其二进制的每一位数都相加，最后再对 3 进行一个取模的过程呢？（一样，如果要定义一个 a ? a ? a ? a = 0 的运算，那就最后对 4 进行取模就可以了）

 1//go
 2func singleNumber(nums []int) int {
 3    number, res := 0, 0
 4    for i := 0; i < 64; i++ {
 5        //初始化每一位1的个数为0
 6        number = 0
 7        for _, k := range nums {
 8            //通过右移i位的方式，计算每一位1的个数
 9            number += (k >> i) & 1
10        }
11        //最终将抵消后剩余的1放到对应的位数上
12        res |= (number) % 3 << i
13    }
14    return res
15}

如果对上面的代码不能理解，可以看看这个图，假设只有一个数 [21]，我们通过不断右移的方式，获取其每一位上的1。当然，这里因为余数都是1，所以肯定都保留了下来，然后与 1 进行 “与”运算，最终再将其放入到对应的位数上。

（还不错）

在上面的代码中，我们通过一个number，来记录每一位数出现的次数。但是缺点是，我们记录了64位（Go语言中，int为32位以上）

（官方文档）

那如果我们可以同时对所有位进行计数，是不是就可以简化过程。因为我们的目的是把每一位与3取模进行运算，是不是就可以理解为其实是一个三进制。如果大家听不懂三进制的话，可以简单理解为3次一循环，也就是 00 – 01 – 10 – 11。但是又因为对于 11 这种情况，我们需要砍掉（上面已经说过了，相当于 11 – 00 的转化），所以我们就只有3个状态，00 – 01 – 10，所以我们采用 a 和 b 来记录状态。其中的状态转移过程如下：

这里 a` 和 b` 的意思代表着 a 和 b 下一次的状态。next 代表着下一个 bit 位对应的值。然后这是什么，不就是状态机嘛。。。我们通过 a 和 b 的状态变化，来完成次数统计。

然后因为此图复杂，将其分别简化成 a 和 b 的卡诺图（卡诺图是逻辑函数的一种图形表示。两逻辑相邻项，合并为一项，保留相同变量，消去不同变量。）

然后我们根据卡诺图（这个卡诺图其实并不难看。。如果学习一下话，还是挺简单的。。）写出关系式：

a` = (a &~ next) | (b & next)

b` = (~a & ~b & next) | (b & ~next)

然后就是套公式：（Java代码，注意Go语言中是不天然支持 ~ 这种运算的）

 1class Solution {
 2    public int singleNumber(int[] nums) {
 3        int a = 0, b = 0, tmp = 0;
 4        for (int next : nums) {
 5            tmp = (a & ~next) | (b & next);
 6            b = (~a & ~b & next) | (b & ~next);
 7            a = tmp;
 8        }
 9        return b;
10    }
11}

当然，其实题解还可以再近一步优化，其实就是化简上一步中的公式：

 1class Solution {
 2    public int singleNumber(int[] nums) {
 3        int a = 0, b = 0;
 4        for (int next : nums) {
 5            b = (b ^ next) & ~a;
 6            a = (a ^ next) & ~b;
 7        }
 8        return b;
 9    }
10}

当然，这个解法就相当牛皮了。如果实在看不懂也没关系，请把上面的两种解法掌握。

08

PART

啰嗦一下

位运算的常考点上面的题目基本上都覆盖了，还是希望大家下去自己练习一番。