定义

异或是一个数学运算，用于逻辑运算。如果 a、b 两个值不同，则异或结果为 1 ，否则结果为 0 。真值表如下：

记真值表的时候有的同学可能觉得很容易记错，也有同学喜欢记异或运算的公式，比如：P = AB' ⊕ A'B（“ ' ”表示非）。其实这两种方法都可以，还有一种方式我个人觉得记忆起来更容易一些，即 异或运算是半加运算。什么意思，半加 即不带进位的加法运算。再来看一下上面的真值表：

括号里的 1 是进位，不考虑进位，即 半加 运算，这样记起来是不是更容易些呢？

在计算机中的应用

很常见的一个应用就是交换两个数的值。例如：

这样写法的好处就是少了一个临时变量，执行效率也比较高。

我们再来看一下 LeetCode 上的一些题目，可以用异或运算巧妙的解决。

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]输出: 1

示例 2:

输入: [4,1,2,1,2]输出: 4

这个题首先想到的就是异或的特性。相同的数字异或的结果为 0，那么出现奇数次的一定就是最后我们想要的结果。

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]输出: 2

示例 2:

输入: [3,1,3,4,2]输出: 3

说明：

不能更改原数组（假设数组是只读的）。只能使用额外的 O(1) 的空间。时间复杂度小于 O(n2) 。数组中只有一个重复的数字，但它可能不止重复出现一次。

我们注意看下题目，题目明确说明了数组 nums 包含 1 和 n ，并且只有一个重复的整数，如果不考虑说明中的第四点的话这段代码是正确的。解释一下原理。a 从 1 一直异或到 n，其中有一个重复的数字 x ，那么就是 1 ^ 2 ^ 3 ··· ^ x ^ x ^ ··· ^ n。异或操作因为是半加运算，因此是满足交换律的，我们把 x 拿到最后面， 即 1 ^ 2 ^ 3 ··· ^ n ^ x ^ x，而 x ^ x 一定是 0 ，因此 1 ~ n 每个数异或了 2 次，而 x 异或了 3 次，所以最后 res 的值就是我们要找的 x 的值。

但是有了第四点，这个方法就不太好用了，下面是一个正确的解法，由于跟异或没有太多的关系，因此就不过多解释。

389. 找不同

给定两个字符串 s 和 t，它们只包含小写字母。字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。请找出在 t 中被添加的字母。

示例：

输入：s = "abcd"t = "abcde"输出：e

解释：

'e' 是那个被添加的字母。

这个题目如果想不到用异或运算的话，写起来可能真的会有点麻烦。我们想到异或运算的特点，a ^ a = 0，如果插入了一个字母的话，那么这个两个字符串中，出现的次数肯定是奇数次，而其他的都是偶数次，所以直接把所有的字符都异或一遍，答案自然就出来了！

---

之前还有一个面试题目，就是有 N + 1 块相同容量的硬盘，其中 N 块用来存储数据，如果利用多余的 1 块硬盘来存储 N 块硬盘的数据备份，假设硬盘最多同时只会损坏 1 块。我想通过上面几个题，大家应该很快想到存储办法了吧，答案就是多余的 1 块硬盘存储 N 块硬盘异或的结果，那么当其中 1 块硬盘损坏的时候，只需要把其他好的硬盘数据再异或一遍，即可得到损坏的硬盘的数据了。

通过上面的例子，我们发现在查找“奇数个”的数据的时候，异或运算用起来还是非常方便的。异或运算还有很多其他的应用，比如简单的加密数据，加密：result = a ^ password，解密：a = result ^ password。

异或运算很简单，难点在于遇到问题能不能想到利用异或运算来解决问题，这就需要我们在编程过程中一点点积累经验，祝大家学习顺利！