文章目录
接着上一篇文章来讲些简单的位操作，这篇侧重的是异或的一些用途，不过其实前一篇文章的后面两道题也都有部分用到异或的内容，可见它的用途还算是挺广泛的。下面来看一些更加贴近异或操作思维的题目。
Problem 136. Single Number
把一个非空数组里只出现一次的数字找出来，剩下的数字保证是出现两次的。这个直接用异或的特性就行了，一个数如果和自身进行按位异或的话，因为每一位都对应相等，所以结果就是一串 0。这样我们把整个数组遍历异或一遍，重复的数字都消掉了，结果就是那个只出现了一次的值，毕竟一个数字和 0 异或之后得到的是它本身：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for (int i : nums) {
ans ^= i;
}
return ans;
}
};
但是提交之后发现运行效率竟然才超过 33% 的代码，在我好奇还有什么更快的解法的时候，去看了下跑得最快的香港记者的代码，发现是完全一样的思路和实现，不过他多加了一行取消 C++ 的 IO 流与 cstdio 同步以及取消绑定 cin 和 cout 的设置，所以运行快了点：
static int fast_io = []() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
return 0;
}();
啊真是骚
不过本来关闭与 cstdio 的流同步和取绑 C++ 自己的 cin、cout 不是什么新奇的操作，就是写算法代码的时候不太会单独再去考虑这个。这段代码不太走寻常路的地方是，这种让填充代码的题目不允许修改 main 函数的内容，所以他用的全局静态变量的方式来保证设置会在一开始被运行，又学到一招，太强大了.jpg。
异或的这个特性还是挺广为人知的，大多数人对按位异或的第一次接触应该都和我一样是刚开始学编程语言中的位操作符的时候，要求不用临时变量来实现两个变量值的交换：
x ^= y; // x_new
y ^= x; // y_new (= y_final)
x ^= y; // x_final
上面各行注释对应接下来两个公式，表示的是左边的那个结果值，不带后缀的表示原始值。把第一行 x 的运算结果代入后面两行代码，展开分别可以得到
感觉是对异或的“一次存储两次清除”（我口胡的简称）特性的完美利用了。
Problem 389. Find the Difference
给定两个小写字母串 s 和 t，t 中除了比 s 多一个字母以外，剩下的内容和 s 相同，但是不保证顺序和多出来的字符的位置。这个题本质上和前面那个从数组里找出只出现一次的数字是完全没区别的，从零开始遍历异或所有的字符就行了：
class Solution {
public:
char findTheDifference(string s, string t) {
char ans = 0;
for (char c : s) ans ^= c;
for (char c : t) ans ^= c;
return ans;
}
};
Problem 461. Hamming Distance
计算两个整数的汉明距离，也就是二进制表达形式各对应位上值不同的总位数。
因为异或操作本身是在比较两个 bit 是否相反，在两个整数按位异或之后得到的值中，每一个 1 都代表它们在这个位上的取值是不同的，于是这个结果的二进制表达中含有的 1 的个数，就是需要求的汉明距离了，1 的个数的简洁和快速求法前两篇文章都提过了所以不赘述。
class Solution {
public:
int hammingDistance(int x, int y) {
int n = x ^ y, ans = 0;
while (n) {
n &= n - 1;
ans++;
}
return ans;
}
};
Problem 693. Binary Number with Alternating Bits
判断一个正整数的二进制形式是不是连续的相反位，即类似 10101... 这样。
虽然最高位一定是一个 1，可以往后一个个按位对比 0 和 1，但是毕竟计算机里面存的整数是长度固定的，会有前导 0 的填充，定位到最高位比较麻烦。我们可以从末尾入手，每次判断最低的两位值是否相反，然后右移一位继续判断，直到碰到相同的两位，这时候可能是右移到了最高位碰到两个 0，也可能是数字中间本来就存在两个连续的位，所以跳出这个循环之后只要值为 0 就能保证它是满足条件的数，反之则不是：
class Solution {
public:
bool hasAlternatingBits(int n) {
while ((n & 1) ^ ((n & 2) >> 1)) n >>= 1;
if (n) return false;
return true;
}
};
末尾的值当然是 n & 1 了，而倒数第二位通过 n & 2 可以拿到，不过为了能和末尾的位进行异或，需要把它的位置也调到最后一位，直接右移一位就行了。
同样需要注意的是这里会导致入参的值被改变，实际用的时候需要确定这个值是不是允许修改。
Problem 137. Single Number II
上面这些都是非常简单的题，所以也没什么好讨论的 xjb 写一段话就可以给代码，接下来的两题相对来说会比较有意思一点。
其实这三部曲我做的顺序是先 Single Number 然后 Single Number III 最后 Single Number II，不过为了不逼死强迫症也就是我自己还是按顺序放吧。
这个相对第一题来说，唯一不同的是除了那个只出现一次的数字以外，其它数字出现的次数都是三次。用异或可以解决偶数次重复的问题，毕竟结果都是 0，可 3 是个奇数，连续异或得到的是自身，会和只出现一次的混在一起，看来并不能仅通过异或来解决。
这道题的解决思路是我高中时一次机缘巧合碰到的，如果之前没有了解过这种方法的话我觉得我肯定想不出来这样的实现，它是从结果值的构造上入手的：首先创建一个为 0 的整数作为初始结果，然后遍历所有数字，统计每一位上含有的 1 的总个数，对三取模作为当前位的值，最后把这个二进制数作为十进制输出：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int pos = sizeof(int) * 8, ans = 0;
while (pos--) {
int cnt = 0;
for (int num : nums) {
cnt += (num >> pos) & 1;
}
ans += (cnt % 3) << pos;
};
return ans;
}
};
我们来一点点分析代码，首先因为 int 所占位数在各个平台上有可能不同，所以不要写死，而是通过 sizeof() 获得它的字节数然后乘以 8 (1 byte = 8 bits) 得到当前环境下的 int 存储位数，接着去计算所有数字在每一位上含有的 1 的总数。
如果重复了三次的数字某个二进制位是 1 的话，3 对 3 取模就为 0 了，那么结果就是那个只出现了一次的数在这个位上的值。如果这个位上是 0 也是一样的，直接就得到仅出现一次的数在本位的值。这样循环结束之后，就相当于提取出了我们需要的结果的每一个二进制位上的值，像是把它一位位构造出来的一样，并且这个方法可以推广到任意的数字而不是仅仅适用于偶数次的重复情况。
这个解法理解起来很容易，不过代码略显复杂和啰嗦，位运算的大部分解法应该都是相当优雅的。
讨论区有个帖子 Challenge me , thx，里面给出了很妙的解法：
public int singleNumber(int[] A) {
int ones = 0, twos = 0;
for(int i = 0; i < A.length; i++){
ones = (ones ^ A[i]) & ~twos;
twos = (twos ^ A[i]) & ~ones;
}
return ones;
}
作者在下面的一条评论给出了简要的解释，前面一个部分的异或和第一题是差不多的想法，就是如果一个数字不在就放进去，在的话就会导致这个数字被从中删掉。不同的操作是后面的对另一个值取非然后和刚刚得到的值按位与，这是为了保证被放进 ones 里面的数是不在 twos 里面的，反之亦然。
也就是说，第一次出现的数会被放进 ones，第二次出现的话就会被从 ones 中删除然后放进 twos，这样第三次出现的数会再和 twos 异或一次被删。最后 ones 里面存的就只有那个只出现一次的数，而 twos 最后的值则是 0。
我们可以用类似数字逻辑里对状态机状态跳转的理解来看待它，先考虑数组里面的数字仅有一位的情况，因为会出现三次所以需要两个比特来表示当前状态，以下用 H 代表高位，L 代表低位，我们的统计状态转换应该是这样的：\(00 \Rightarrow 01 \Rightarrow 10 \Rightarrow 00\)，为了详细一点说明下面给出真值表：
| Status H | Status L | Data | Jump H | Jump L | Occured |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | 1 | Once |
| 0 | 1 | 0 | 0 | 1 | |
| 0 | 1 | 1 | 1 | 0 | Twice |
| 1 | 0 | 0 | 1 | 0 | |
| 1 | 0 | 1 | 0 | 0 | Clear |
然后化简整理一下 Jump H 和 Jump L 的逻辑表达式就可以了，注意下式中所有的取非上划线除了最后一个以外都是只作用在单个字母上的而不是对整体的：
$$
L_{jump} = \overline{H}\overline{L}D +\overline{H}L\overline{D} = \overline{H}(\overline{L}D + L\overline{D}) = \overline{H}(L \oplus D)
$$
$$
H_{jump} = \overline{H}LD + H\overline{L}\overline{D} = (H \oplus L) \cdot \overline{(L \oplus D)}
$$
\(H_{jump}\) 最后的那个异或不是化简得到的，只是另外一个公式而已，那么得到逻辑表达式之后我们就可以写出代码了：
int lower = 0, higher = 0;
for (int num : nums) {
int temp = lower;
lower = (lower ^ num) & ~higher;
higher = (higher ^ temp) & (~(temp ^ num));
// OR: higher = (~higher & temp & num) | (higher & ~temp & ~num);
}
return lower;
但是这样很明显有个缺点是需要一个临时中间变量，而且公式也显得复杂了些，特别是后面那行被注释掉的替代方案。我们可以考虑在计算 higher 时使用新的 lower 值来替代掉旧的值，当然公式也需要重新整理，注意现在的 L 不再是 Status L 而是 Jump L 了：
$$
H_{jump} = \overline{H}\overline{L}D + H\overline{L}\overline{D} = \overline{L}(H \oplus D)
$$
形式和 \(L_{jump}\) 的计算一模一样，而且不再需要中间变量，这个代码看起来就很舒服了，一家人一段代码就是要整整齐齐：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int lower = 0, higher = 0;
for (int num : nums) {
lower = (lower ^ num) & ~higher;
higher = (higher ^ num) & ~lower;
}
return lower;
}
};
所以所谓的 ones 和 twos 分别是第一次和第二次出现的数字集合的说法，实际上就是一个状态码的高低两位而已，两者相配合存储着当前数出现的次数情况。毕竟它们本身只是个整数，用数字集合的方式来理解难免还是不太直观。
我们刚刚考虑的是数字仅有一个比特位的情况，但是因为所有数字都是相同格式的，拓展到 n 位也完全成立，相邻位之间并不会相互影响，毕竟我们需要的只是最后留下来的数字的二进制表达形式而已，不用关心它本身是什么，也不用关心它的各个相邻位之间的关系，因此可以把每个比特位拆开看待，独立进行各自的运算。
也正是因为题目需要的仅仅是一个结果，而不用了解中间过程的数字、状态是什么，我们可以忽略一个数字把另一个数字的统计状态修改掉的情况，比如某位为 1 的数 A 被加进了 同样位置的二进制位为 1 的数 B，看起来好像是 B 被统计多了一次而 A 被忽略掉了，但是实际上由于对称性，B 还是会对应修改到 A 的这一位上，最终所有的相互修改都被叠加抵消掉，只剩下 lower 里面存着我们需要的值。
这个解决方案也可以推广到任意的数字而不仅仅是 3，不过显然它不能和构造的那个思路一样直接通过修改一个数字来应对变更，而是要根据次数决定状态码的位数，再重新整理出逻辑表达式，拓展性可能不是太好。
另外，在运行时间分布图上最快的一个是这样做的：
int one = 0, two = 0;
for (const auto num : nums) {
two |= one & num;
one ^= num;
auto three = ~(one & two);
one &= three;
two &= three;
}
return one;
但是提交发现运行时间并没有多大差别，好像又是 IO 同步那方面的耗时严重一点，我觉得要考虑一下以后是不是每次都直接加上前面那段优化 IO 的代码上去了（
他这个解法也利用到了刚刚提到的那个对称性的特点，为了简化问题先只考虑一个数字重复三次的情况，再推广到数组里的所有数字，只要把一个数字的情况考虑完善就能不加额外条件直接适用题目的情景了。模拟走一下循环段里面的流程：
two |= one & num：按位与把num和one中都有 1 的位置提取出来，实际上就是把重复的数提取出来，然后通过按位或传递进two里面，也就是two里面现在会存着第二次出现的数字one ^= num：这个就是前面讲了很多次的如果num是第一次出现就放进one里面，不是就把它从one里面删掉three = ~(one & two)：按位与再提取出one和two中都有 1 的位置，取反存进three，所以three里面现在存着的是第三次出现的数字的反码one &= three：因为three里面是反码，就相当于如果one里面的数已经是第三次出现，就和自己的反码进行一次按位与，等于把这个数从one里面删掉two &= three：同上，把出现第三次的数从two里面删除
这样到最后 one 里面就是那个唯一一个仅出现一次的数字了，它和最开始给的那个对 3 取模的思路是类似的，就是消掉出现多次的数，留下出现仅一次的数。如果要推广到任意数字的话，应该得继续往下写 four、five 之类的了，听起来就很可怕。
Problem 260. Single Number III
这个题说是 III 但是比 II 更简单一点，还是其它数字在数组中出现了两次，只是现在出现仅一次的数字有两个了，我们总不可能直接遍历异或然后从得到的结果中给拆分出两个数来。但这个异或的结果还是有价值的，根据这个位操作的特性我们可以知道，结果中含有 1 的位，对应的原来两个数的相同位置上的值一定是相反的。
从这个题目和第一题的相似程度来看，我们可以考虑把数组分为两个子数组，各自包含一个只出现一次的结果，这样就可以用完全一样的解法对两个子数组分别求得结果，那么问题就只在如何分组上了。
刚刚提到整个数组的所有数字异或之后得到的值中，含有 1 的位表示两个答案中那个位置的值是相反的，我们可以就用这个作为掩码来区分两个数，因为现在需要的只是分组而已不用考虑别的位的情况，而对于其它数，无论该位的值是 0 还是 1，两次异或到最后都会被抵消，进而两个子数组各自只剩下一个我们需要的结果。
所以现在，问题就只剩下如何从一个数的二进制表达形式中提取出某个 1 的位置，我们到现在已经用到了很多次将一个数的最低位 1 置零的操作：n &= (n - 1)，可以从这里下手看看能不能得到那个最低位 1。在第一篇文章对这个的解释中，我们知道 n - 1 得到的是最低位 1 及其后的所有位都取反的值，并且这个“其后的所有位”当然都是由零转变成的一了。
这个特性我们稍微修改一下就能用上做为提取末位 1 的桥梁，很显然“末位 1 及其后的所有位”是 1000...000 的格式，只要前面的值也全是 0 就行了，而一个取非加上和原数进行按位与就能清除掉所有这些多余的高位，也就是 n & (~ (n - 1)) 得到的便是仅最低位 1 保持为 1，其它位都为 0 的数字。
从取反的角度考虑一下可以想出另一个方案，如果一个数末尾是 ...111 这样的话，加上个 1 就是 ...1000 了，也就是取反加一可得到和刚刚一样的结果，然后按位与一次就清除掉了多余的高位：n & (~n + 1)，只从代码上看它就是前面那个公式把取反符号放进括号内了而已。
实际上这个取反加一后的值就是二进制下的补码，直接把获得掩码的代码换成 n & -n 就行了：
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int mask = 0;
for (int num : nums) mask ^= num;
mask &= -mask;
vector<int> ans(2, 0);
for (int num : nums) {
if (num & mask) ans[0] ^= num;
else ans[1] ^= num;
}
return ans;
}
};