XOR异或计算
2017-06-14 本文已影响0人
zhuke
1. 异或运算
在数字逻辑中，逻辑算符互斥（exclusive or）是对两个运算元的一种逻辑分析类型，符号为XOR或EOR或⊕。
a⊕b = (¬a ∧ b) ∨ (a ∧¬b)
其真值表如下：
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
总结：
如果两个二进制位相同，就返回0，表示false；否则返回1，表示true。
真值结果是无进位的二进制加法得到的结果。
2. 异或运算的特性
-
交换律：
-
结合律：
- 恒等律：
- 归零律：
- 自反律：
以上均可根据a⊕b = (¬a ∧ b) ∨ (a ∧¬b)的算法定义进行证明。
3.应用
- 快速比较两值是否想等
r = a xor b
if a==b
r == 0
else
r != 0
-
检验一个数字中1的个数的奇偶（奇偶校验）
求10100001中1的个数
1 ^ 0 ^ 1 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 1
按位进行异或运算得到的结果等于1，结果为奇数，得到的结果为0，结果为偶数 -
不使用中间变量，交换两个变量的值
a = a ^ b;
b = a ^ b; //a ^ b ^ b = a ^ 0 = a;
a = a ^ b;
- 面试题：一个整型数组里除了一个数字之外，其他的数字都出现了两次，找出这个数字
对于数组{a, a, b, b, c, c, d}，找出只出现了一次的数字d
a^a^b^b^c^c^d
= 0 ^ 0 ^ 0 ^d
= 0 ^ d
= d
时间复杂度为O(N), 空间复杂度为O(1)
- 在密码学中的应用
message XOR key // cipherText
cipherText XOR key // message
明文 XOR 密钥 --> 密文
密文 XOR 密钥 --> 明文
以上特性很好地对应了加密和解密的过程。所以目前很多加密算法都利用了异或算法的这个特性来做最后的密文打乱的工作。
参考资料：
http://www.ruanyifeng.com/blog/2017/05/xor.html
https://www.lijinma.com/blog/2014/05/29/amazing-xor/
https://zh.wikipedia.org/wiki/%E9%80%BB%E8%BE%91%E5%BC%82%E6%88%96
