对异或运算(xor)的探索

由来

开始注意到这个问题是因为在 leetcode 上面刷到了这样一道题——只出现一次的数字。题目要求为：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次，找出那个只出现了一次的元素。需要注意的是：算法应该具有线性时间复杂度，尽量不使用额外的空间。
当时看到这个题，想的思路是：对题目中给出的数组进行遍历，用一个新的数组 N 来存储这些数，如果某个数不存在 N 中，那么就把这个数存进去，如果已经存在，就将 N 中的这个数删除，最后 N 中剩下的一个数就是那个唯一只出现一次的数了。
上面的方法可以实现功能，但是时间复杂度和空间复杂度都比较高，很不划算，然后，我就去看了一下已有的题解，先是很懵逼，之后就觉得非常巧妙了，代码如下：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for i in range(len(nums)):
            result ^= nums[i]
        return result

以上即为，假如给出的数组是这样的：[a, b, p, m, b, m, a] ，代码中最终的结果也就是result = a^b^p^m^b^m^a = p，能够得到这样的答案，那么异或运算肯定就符合交换律，并且a^a = 0; a^0 = 0。
然后我就想，这么神奇的东西，我一定要弄清楚。
所以，以下就是，什么是异或运算？异或运算都哪些性质，为什么？以及，异或运算都可以用来做什么？

异或运算

异或运算，其实就是一种逻辑运算，$p$ 异或 $q$ 记作 $pXORq$ ，在 python 中写作p^q，其真值运算表如下：

p	$T$	$T$	$F$	$F$
q	$T$	$F$	$T$	$F$
p ^ q	$F$	$T$	$T$	$F$

查了维基百科上面还有一些使用 且、或、非 来表达异或关系的表达式(真的不想敲数学公式)。

对两个数进行异或运算时，可以先把两个数转换为二进制形式，然后对其按位进行异或操作，即可得到最后的答案，比如下例：

p	$1$	$0$	$0$	$1$	$1$	$0$	$1$	$1$
q	$0$	$0$	$1$	$0$	$1$	$1$	$1$	$0$
p ^ q	1	0	1	1	0	1	0	1

性质 and why ?

• 交换律：$p$ ^ $q$ = $q$ ^ $p$
• 结合律：$p$ ^ ($q$ ^ $r$) = ($q$ ^ $p$) ^ $r$
• 恒等律：$p$ ^ $0$ = $0$
• 归零律：$p$ ^ $p$ = $0$
• 自反性：$p$ ^ $q$ ^ $q$ = $q$

很奇怪，小学很容易的接受了加法运算可以任意交换位置的事实，今天遇到的这个异或运算却非要想清楚到底为什么。然后我就想啊想啊，总结了一个规律，看对应位上 1 的个数是奇数还是偶数就好了。(在计算机中，^ 就是按位异或)

p	$1$	$0$	$0$	$1$	$1$	$0$	$1$	$1$
q	$0$	$0$	$1$	$0$	$1$	$1$	$1$	$0$
r	$1$	$1$	$1$	$0$	$0$	$1$	$1$	$0$
n = ‘1 的个数’	2	1	2	1	2	2	3	1
n 的奇偶性	偶	奇	偶	奇	偶	偶	奇	奇
p ^ q	0	1	0	1	0	0	1	1

因为 “同为 0 ，异为 1 ” ，相异的也就只有 0 - 1 这种情况啦，而两个 1 异或得到 0 ，所以只要看 1 的个数就好了。而看个数的话，顺序当然就无所谓了。
当然，这里仅仅是对于数字之间异或的小规律，严谨一点的话，还是需要从表达式来推导。

应用

1. 首先就是之前提到的，当数组中其他的数都出现 2 次时，能够得到唯一只出现过一次的数。对这个问题进行推广，也就是，当数组中其他数都出现偶数次时，可以得到唯一出现奇数次的数。
2. 交换两个数：python 可以直接写作 a, b = b, a，但可能有一些其他的语言不能这样写，所以使用异或还是比较有用滴，可以不需要借助中间变量。

   a = 3
   b = 5
   a = a^b		# a = 3 ^ 5
   b = a^b		# b = 3 ^ 5 ^ 5 = 3
   a = a^b		# a = 3 ^ 5 ^ 3 = 5

3. 简单的数据加密，设置一个二进制串为密钥，与明文异或得到密文，与密文再次异或即得到明文。
4. 数字校准，快速比较两数是否相同，利用了 $a$ ^ $a$ = $0$，异或为 0 时，两数相等。据说这个效率比用减法更高。
   (2020.05.02 补充)
5. 奇数偶数交换
   奇数末位为 1 ，和 1 异或，末位变为 0 ，其他位置不变；
   偶数末位为 0 ，和 1 异或，末位变为 0 ，其他位置不变；
   故当一个数和 1 异或时，奇数减一，偶数加一。
   应用：
   可用于需要把数列中所有奇数 +1 ，所有偶数 -1 的场景；比如需要前后两人交换座位。

   推理：
   假如 n 是一个十进制整数，则
   当 n mod 2^(k+1) < 2^k 时，n xor 2^k = n + 2^k
   当 n mod 2^(k+1) >= 2^k 时，n xor 2^k = n - 2^k
   (现在也不知道有啥用，就先写上吧哈哈哈)

参考链接：
力扣网题目-换座位-leck的题解

(以上～先到这，其他的，遇上再说吧……)