Single Number这三道题是一类非常精妙的位运算操作类型的题目，在此一并进行一下总结分析。
Single Number I
第一个问题非常简单，一个数组中除了一个数字之外，其他数字都出现了两次，求这个数字。这里用到了异或运算的三个性质：x ^ x = 0；x ^ 0 = x；以及运算顺序的可交换性。我们只需要把数组中的所有数字都求一遍异或，数组中出现两次的数字自己跟自己异或就等于零，而唯一出现一次的那个数字，跟零求异或的结果自然就是那个数字本身了。所以超级简单的答案代码如下：
:::C++
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for (auto &i: nums) {
res ^= i;
}
return res;
}
};
Single Number II
第二问给出一个数组，除了一个数字只出现一次之外，所有数字都出现三次，同样是求这个特殊的数字。那么这个问题实际上是对第一道题目的推广。在第一个问题中，如果我们将每一个数字看做是二进制序列，把每个bit上面1出现的次数累加到一起后模2，那么得到的这个bit pattern就是那个单独的数字。同样的道理，在这个问题中，把模2换成模3，得到的就是我们想要的答案——那个单独的数字了。这是因为对于其他所有重复出现三次的数字，每个bit上面1出现的次数必然能够被3整除，那么多出来的，自然就是那个单独的家伙。由此我们得到一个比较糙快猛的解法如下：
:::C++
class Solution {
public:
int singleNumber(vector<int> &nums) {
const int bits = sizeof(int) * 8;
int nn[bits];
memset(nn, 0, sizeof(nn));
int res = 0;
for (auto &n: nums) {
for (int i = 0; i < bits; i++) {
if ((n >> i) & 1) {
nn[i]++;
}
}
}
for (int i = 0; i < bits; i++) {
nn[i] %= 3;
if (nn[i]) {
res |= (1 << i);
}
}
return res;
}
};
这个答案其实还有进一步的常数空间压缩优化。在这个问题中，我们并不需要完全记录下每个bit上面1到底出现了多少次——事实上，我们只需要记录他们模3之后的答案即可，也就是哪些bit上模3等于1，哪些模3等于2，等等……因此，通过应用这样一种状态转移的思想，我们可以给出一种简短的基于位运算的优化算法，下面是我的较为丑陋的实现（LeetCode论坛里面有种漂亮得多的实现）：
:::C++
class Solution {
public:
int singleNumber(vector<int> &nums) {
int ones = 0, twos = 0, threes = 0;
for (auto &n: nums) {
int old_ones = ones;
ones = (n & (~((n & twos) | (n & old_ones)))) | ((n ^ old_ones) & old_ones) | (threes & n);
threes = twos & n;
twos = (old_ones & n & (~threes)) | ((twos ^ n) & twos);
}
return ones;
}
};
Single Number III
第三问给出一个数组，里面除了两个数字出现一次以外，其他都出现两次，求这俩数。朴素地追随第一题的思想，我们显然可以轻易算出两个数字异或的值——但这并没有什么卵用啊。事实上，这是个非常tricky的问题，它的核心思想在于：分组。如果我们能够把这个数组以某种方式分为两组，并且保证把这俩出现一次的值分别分到这两组内，那么，按照第一问的算法，不就能非常简单求出答案了么。所以问题就转化为，如何进行这个分类呢？事实上，这两个"single number"的异或值，恰好就可以用来做这样的分类。把这个异或值看做二进制序列，在所有为1的bit上面，说明两个值在这一位上有差异。那么我们就可以把所有数字在这一bit上面为0或者为1来作为分类判据，这个判据显然可见是完备的，于是就能够正确地将数组分成两组了。最终得到的代码如下：
:::C++
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
vector<int> res;
int tmp = 0;
for (auto &n: nums) {
tmp ^= n;
}
int pos = -1;
for (int i = 0; i < sizeof(int) * 8; i++) {
if ((tmp >> i) & 1) {
pos = i;
break;
}
}
int res1 = 0, res2 = 0;
for (auto &n: nums) {
if ((n >> pos) & 1) {
res1 ^= n;
} else {
res2 ^= n;
}
}
res.push_back(res1);
res.push_back(res2);
return res;
}
};