常见解题套路
- 异或运算
- 应用
- 1 简化计算
- 2 交换值
- 3 加密
- 4 数据备份
- 一道面试题
- leetcode相关题目链接
- 参考
异或运算
异或运算: 判断两个值是否不同,相同为0,不同为1，体现在二进制位上则为: 1^ 0=1 或者 0^ 1=1 或者 0 ^0=0 或者 1 ^1=0 。
异或运算满足以下定律:
（1）一个值与自身的运算，总是为 false。
x ^ x = 0
（2）一个值与 0 的运算，总是等于其本身。
x ^ 0 = x
（3）可交换性
x ^ y = y ^ x
（4）结合性
x ^ (y ^ z) = (x ^ y) ^ z
应用
根据上面的这些运算定律，可以得到异或运算的很多重要应用。
1 简化计算
多个值的异或运算，可以根据运算定律进行简化。
a ^ b ^ c ^ a ^ b = a ^ a ^ b ^ b ^ c = 0 ^ 0 ^ c = c
2 交换值
两个变量连续进行三次异或运算，可以互相交换值。
假设两个变量是x和y，各自的值是a和b。下面就是x和y进行三次异或运算，注释部分是每次运算后两个变量的值。
x = x ^ y // (a ^ b, b) y = x ^ y // (a ^ b, a ^ b ^ b) => (a ^ b, a) x = x ^ y // (a ^ b ^ a, a) => (b, a)
这是两个变量交换值的最快方法，不需要任何额外的空间。
3 加密
异或运算可以用于加密。
第一步，明文（text）与密钥（key）进行异或运算，可以得到密文（cipherText）。
text ^ key = cipherText
第二步，密文与密钥再次进行异或运算，就可以还原成明文。
cipherText ^ key = text
原理很简单，如果明文是 x，密钥是 y，那么 x 连续与 y 进行两次异或运算，得到自身。
(x ^ y) ^ y = x ^ (y ^ y) = x ^ 0 = x
4 数据备份
异或运算可以用于数据备份。
文件 x 和文件 y 进行异或运算，产生一个备份文件 z。
x ^ y = z
以后，无论是文件 x 或文件 y 损坏，只要不是两个原始文件同时损坏，就能根据另一个文件和备份文件，进行还原。
x ^ z = x ^ (x ^ y) = (x ^ x) ^ y = 0 ^ y = y
上面的例子是 y 损坏，x 和 z 进行异或运算，就能得到 y。
一道面试题
一些面试的算法题，也能使用异或运算快速求解。
请看下面这道题。
一个数组包含 n-1 个成员，这些成员是 1 到 n 之间的整数，且没有重复，请找出缺少的那个数字。
最快的解答方法，就是把所有数组成员（A[0] 一直到 A[n-2]）与 1 到 n 的整数全部放在一起，进行异或运算。
A[0] ^ A[1] ^ … ^ A[n-2] ^ 1 ^ 2 ^ … ^ n
上面这个式子中，每个数组成员都会出现两次，相同的值进行异或运算就会得到 0。只有缺少的那个数字出现一次，所以最后得到的就是这个值。
你可能想到了，加法也可以解这道题。
1 2 … n - A[0] - A[1] - … - A[n-2]
但是，加法的速度没有异或运算快，而且需要额外的空间。如果数字比较大，还有溢出的可能。
下面是一道类似的题目，大家可以作为练习。
一个数组包含 n 1 个成员，这些成员是 1 到 n 之间的整数。只有一个成员出现了两次，其他成员都只出现一次，请找出重复出现的那个数字。
leetcode相关题目链接
- 异或运算的简单应用
136. 只出现一次的数字
- 没有使用异或运算,而是采用计算每个二进制位上的累加和取余3,判断当前位是否需要设置为1
137. 只出现一次的数字 II
- 异或运算 分组
260. 只出现一次的数字 III
- 异或运算
剑指 Offer 53 - II. 0～n-1中缺失的数字
参考
异或运算 XOR 教程
不定期更新…
