在逻辑学中，逻辑算符异或（exclusive or）是对两个运算元的一种逻辑析取类型，符号为 XOR 或 EOR 或 ⊕（编程语言中常用^）。但与一般的逻辑或不同，异或算符的值为真仅当两个运算元中恰有一个的值为真，而另外一个的值为非真。转化为命题，就是：“两者的值不同。”或“有且仅有一个为真。”

1 ⊕ 1 = 0 0 ⊕ 0 = 0 1 ⊕ 0 = 1 0 ⊕ 1 = 1

Y = A ’ ⋅ B + A ⋅ B ’ Y = A’ · B + A · B’ Y=A’⋅B+A⋅B’

解释：我使用·作为与，我使用+作为或，我使用’作为否(本来应该使用头上一横，但是太难编辑了，就使用了’）；

根据定义我们很容易获得异或两个特性：

恒 等 律 ： X ⊕ 0 = X 恒等律：X ⊕ 0 = X 恒等律：X⊕0=X

归 零 律 ： X ⊕ X = 0 归零律：X ⊕ X = 0 归零律：X⊕X=0

然后我们使用真值表可以证明：

（1）交换律

因为·与和+或两个操作满足交换律，所以：

A ⊕ B = B ⊕ A A ⊕ B = B ⊕ A A⊕B=B⊕A

（2）结合律

你可以使用同样推导方法得出（请允许我偷懒一下，数学公式敲起来不容易 +_+）：

证明过程中使用了如下几个方法（·与 +或 '否）：

·与 +或交换律：

·与 +或结合律：

·与 +或分配律：

摩尔定理

结论：

交换律：A ⊕ B = B ⊕ A 结合律：A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C

有了归零率和结合律，我们就可以轻松证明：

自反：A ⊕ B ⊕ B = A ⊕ 0 = A

可能这些特性会很顺其自然的理解，但是如果你在解决问题的时候，你可能会忘记异或的这些特性，所以适当的应用可以让我们加深对异或的理解；

说明：以下的的异或全部使用符号^

可能你已经被乱七八糟的公式和演算搞的有点烦了，不就是很简单的异或运算吗？还解释的那么复杂，嘿嘿，不要着急，打好了基础，你就站在了巨人的肩膀，让我们开始异或的神奇之旅吧；

先让我们来一个简单的问题；判断两个int数字a，b是否相等，你肯定会想到判断a - b == 0，但是如果判断a ^ b == 0效率将会更高，但是为什么效率高呢？就把这个给你当家庭作业吧。

0 ^ 1 = 1

1 ^ 1 = 0

例如：翻转10100001的第6位， 答案：可以将该数与00100000进行按位异或运算;10100001 ^ 00100000 = 10000001

例如：求10100001中1的数量是奇数还是偶数； 答案：1 ^ 0 ^ 1 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 1,结果为1就是奇数个1，结果为0就是偶数个1； 应用：这条性质可用于奇偶校验（Parity Check），比如在串口通信过程中，每个字节的数据都计算一个校验位，数据和校验位一起发送出去，这样接收方可以根据校验位粗略地判断接收到的数据是否有误

校验和恢复主要利用的了异或的特性：IF a ^ b = c THEN a ^ c = b 应用：一个很好的应用实例是RAID5，使用3块磁盘（A、B、C）组成RAID5阵列，当用户写数据时，将数据分成两部分，分别写到磁盘A和磁盘B，A ^ B的结果写到磁盘C；当读取A的数据时，通过B ^ C可以对A的数据做校验，当A盘出错时，通过B ^ C也可以恢复A盘的数据。

原理： 第一步没啥好说a = a^b 第二步：b=b^a ,也就是 b=b^a^b ,也就是b=a^0,此处换值 第三步：a=a^b 也就是a=a^b^a,也就是b

比如，从{1, 2, 3, 4, 5, 3, 2, 4, 5}中找出单个的数字： 1

让我们从最简单的，找一个数字开始；

题目：（LeetCode 中通过率最高的一道题） Single Number: Given an array of integers, every element appears twice except for one. Find that single one. Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 思路： 拿到这个题目，本能的你会使用排序（数字文字我们常常需要排序），排序后可以来判断是否数字成对出现，思路很明显，但是排序的算法上限是 O(nlogn)，不符合题目要求；

学习了强大的异或，我们可以轻松的使用它的特性来完成这道题目： （1）A ^ A = 0; （2）异或满足交换律、结合律； 所有假设有数组：A B C B C D A使用异或：

是不是很神奇？时间复杂度为O(n)，当然是线性的，空间复杂度O(1)； 代码：