又是这种完全不能按照算法课设计思路的题目，必须要找到一个操作的方法。之前已经遇到过类似的题目，一个数字出现1次而其他所有数字出现2次的时候，使用异或来消去其他数字。所以很自然的，我就想到有没有一种方法能够3次消掉，1次保留呢？
不过花了好长时间没有想出来，于是乎看了下讨论区Oxford大神的解答，思路跟我一样。不过我想的方向不太对。
大神的解法是，对每一个比特，使用两个比特（分别称a和b），像加法一样记录次数。但是记录到3的时候归0，就是00->01->10->00的转换。
看上去没什么问题，但是出来的代码却让我“虎躯一震”：
int singleNumber(vector<int>& nums) {
int a = 0, b = 0;
for (auto x : nums) {
b = (b ^ x) & ~a;
a = (a ^ x) & ~b;
}
return b;
}
啥？这异或与非怎么来的？怎么就这么简洁？
推导尝试
我用笨办法，先把真值表写出来。ab是我们记录次数的二进制数，而x则是对应位上的比特。
| a | b | x | a’ | b’ |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
a与b为1,1的情况是不会出现的，所以暂时没有画出来。
使用最简单的构造法，把所有结果为1情况用或运算连起来，能得到
a' = (a & ~b & ~x) | (~a & b & x)
b' = (~a & b & ~x) | (~a & ~b & x)
比较下，结果不太对，也不太简洁。不过观察发现，b’的计算中，~a是两个情况都出现的，于是乎可以拿出来，得到
b' = ~a & ((b & ~x) | (~b & x))
再看看，后面的或运算，是两个值相反的时候为真，不就是异或运算吗？所以，式子就简化为
b' = ~a & (b ^ x)
就与大神的结果一样了。但是a’的计算还是很复杂，并且里面没有可以提取的东西，所以是怎么推导的呢？
再看看代码，发现代码先计算的b，然后再计算a，并且a的式子里面有b在，也就是a的式子实际上输入是b’而不是b。
我们再试试看，将不用b那一列，而是用b’
a' = (a & ~b' & ~x) | (~a & ~b' & x) // 真值表得到
= ~b' & ((a & ~x) | (~a & x)) // 提取~b
= ~b' & (a ^ x) // 改为异或运算
所以是这么来的。
总结
如果后面再次遇到这样使用位操作的题目的话，也可以再次尝试这个方法，写出真值表，写出布尔表达式，尝试简化。简化的过程可以尝试使用前面的结果，可能会得到更加简洁的表达，但是要注意区分结果，不要出现a当成a’这种情况。
这道题还有一个特殊的地方在于，ab是不可能是11，但是为了简化的需要，我们可以尝试加入a和b为11进去，然后规定一个结果，但是需要简化布尔式。不过没有成功，于是就只是上面那么做了。
