XOR 异或运算在计算机中的应用

1. 什么是异或运算

异或，英文为exclusive OR，缩写成xor。

xor是一个数学运算符。它应用于逻辑运算。异或的数学符号为“⊕”，计算机符号为“xor”。如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。



异或也叫半加运算，其运算法则相当于不带进位的二进制加法：二进制下用1表示真，0表示假，则异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1），这些法则与加法是相同的，只是不带进位，所以异或常被认作不进位加法。



真值表如下：



2. 异或运算的特性

• 交换律：A⊕B = B⊕A

• 结合律：A⊕(B⊕C) = (A⊕B)⊕C

• 恒等律：X⊕0 = X

• 归零律：X⊕X = 0

• 自反律：A⊕B⊕B = A⊕(B⊕B) = A⊕0 = A

3. XOR在计算机中的应用

3.1 快速比较两值是否想等

r = a xor b
if r == 0 
    print(“a == b”)
else
    print(“a != b")

3.2 检验一个数字中1的个数的奇偶（奇偶校验）

求10100001中1的个数的奇偶性

1 ^ 0 ^ 1 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 1

按位进行异或运算得到的结果等于1，结果为奇数，得到的结果为0，结果为偶数

3.3 不使用中间变量，交换两个变量的值

a = a ^ b;
b = a ^ b; //a ^ b ^ b = a ^ 0 = a;
a = a ^ b;

3.4 特殊场景，寻找特殊数据

利用异或运算的归零律：X⊕X = 0 和恒等律：X⊕0 = X

对于数组{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)

3.5 密码学中对称加密解密

利用异或运算的自反律: A⊕B⊕B = A⊕(B⊕B) = A⊕0 = A

message XOR key // cipherText

cipherText XOR key // message

明文 XOR 密钥 --> 密文

密文 XOR 密钥 --> 明文

以上特性很好地对应了加密和解密的过程。所以目前很多加密算法都利用了异或算法的这个特性来做最后的密文打乱的工作。



以上，to be continued！