原创：扣钉日记（微信公众号ID：codelogs），欢送分享，转载请保留出处。

简介

家喻户晓，编程语言个别都内置了3种位运算符&(AND)、|(OR)、~(NOT)，用来实现位运算，但其实还有一种十分罕用的位运算，即异或^(XOR)，数学中罕用⊕示意。

异或的运算逻辑如下：
1 ⊕ 1 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1
0 ⊕ 0 = 0

简略来说，异或的个性是，两个值雷同，后果为0，不同则后果为1，所以才叫异或嘛，两个值相异再或起来，不就是1嘛

因为异或非凡的运算个性，使其能够实现一些神奇的操作，如下：

  1. 实现加减法
  2. 加解密
  3. 密钥替换
  4. 数据备份

那就来一起看看吧！

运算定律

  1. 任何值与本身异或，后果为0

    x ^ x = 0

  2. 任何值与0异或，后果为其本身

    x ^ 0 = x

  3. 交换律

    x ^ y ^ z = x ^ z ^ y

  4. 结合律

    x ^ y ^ z = x ^ (y ^ z)

    异或的运算定律比较简单，就不写数学证实了，感兴趣可到网上搜寻。

实现加减法

XOR的第一种使用场景就是实现加减法，在咱们上小学时，应该都学过进位加法与退位减法来做加减运算，咱们来温习一下吧。

  • 进位加法：
    当某一位上两数之和大于10时，须要进位，即高位上要多加一个1。
  • 退位减法：
    当某一位上两数相减不够时，须要退位，即从高位上借(减)一个1，来当作10用。

异或其实与这个相似，不过它不会产生进位与退位，如下：

  1. 如二进制加法01 + 01 = 10，而异或运算是01 ^ 01 = 00，它其实做了加法，但高位不进位，所以异或又称不进位加法。
  2. 如二进制减法10 - 01 = 01，而异或运算是10 ^ 01 = 11，也能够看做个位0向高位借了一个1当2来用，但高位不减1，所以异或也能够称为不退位减法。

利用异或的这个个性，只有再解决一下进位和退位问题，就能够实现加减法了，如下是java代码实现：

public static int intPlus(int a, int b){    while (b != 0){        // 加法(未思考进位)        int sum = a ^ b;        // 进位值，二进制中1 + 1的场景才会进位，a & b只有两个都为1，后果才是1，左移一位，就是进位值了        int addition = (a & b) << 1;        // 赋值，下次循环将进位加到a外面来，直到进位等于0        a = sum;        b = addition;    }    return a;}public static int intSubtract(int a, int b){    while (b != 0){        // 减法(未思考退位)        int sum = a ^ b;        // 退位值，二进制中0 - 1的场景才会退位，~a & b只有a=0,b=1，后果才是1，左移一位，就是退位值了        int abdication = (~a & b) << 1;        // 赋值，下次循环将退位再从a中减掉，直到退位等于0        a = sum;        b = abdication;    }    return a;}

这也是为什么CPU外面都是做位运算的逻辑门电路，却能实现数值计算

加解密

应用XOR能够实现简略的加解密，如果明文为plain，密钥为key，密文为secret，则：

// 加密secret = plain ^ key// 解密plain = secret ^ key

为什么肯定能解密呢，如下：

secret ^ key     = (plain ^ key) ^ key     // 代入加密表达式    = plain ^ (key ^ key)     // 代入结合律    = plain ^ 0               // 任何值与本身异或等于0    = plain                   // 任何值与0异或等于本身

java实现如下：

public static byte[] xorEncrypt(byte[] plain, byte[] key){    byte[] secret = new byte[plain.length];    for(int i = 0; i < plain.length; i++){        secret[i] = (byte) (plain[i] ^ key[i % key.length]);    }    return secret;}public static byte[] xorDecrypt(byte[] secret, byte[] key){    return xorEncrypt(secret, key);}public static void main(String[] args) {    byte[] plain = "hello xor".getBytes(StandardCharsets.UTF_8);    byte[] key = "1234".getBytes(StandardCharsets.UTF_8);    byte[] secret = xorEncrypt(plain, key);    byte[] plain2 = xorDecrypt(secret, key);    // 输入 plain:aGVsbG8geG9y,secret:WVdfWF4SS1tD, plain2:aGVsbG8geG9y    System.out.printf("plain:%s,secret:%s, plain2:%s", Base64.encode(plain), Base64.encode(secret),            Base64.encode(plain2));}

密钥替换

密钥替换就是通信单方须要将加密密钥发送给对方，但不让两头的信道监听者晓得密钥是什么，而利用XOR就能够实现一种最简略的密钥替换计划，如下：

  1. 客户端生成一个随机密钥p，而后再应用本人的密钥k1对其XOR加密，将加密后的s1发送给服务端，即s1 = p ^ k1。
  2. 服务端再应用本人的密钥k2对s1做XOR加密，将加密后的s2回复给客户端，即s2 = s1 ^ k2。
  3. 客户端再应用本人的密钥k1对s2做XOR解密，将解密后的s3回复给服务端，即s3 = s2 ^ k1。
  4. 服务端再应用本人的密钥k2对s3做XOR解密，即s4 = s3 ^ k2，而按XOR的性质，s4会等于p，即客户端顺利将p发送给了服务端，且两头通信数据都是加密的。

    整个过程能够看做先是单方都在密文中做了一次加密，而后单方又逐渐解开。

证实其正确性也很简略，只须要将式子代入一下即可，如下：

s4 = s3 ^ k2   = (s2 ^ k1) ^ k2   = ((s1 ^ k2) ^ k1) ^ k2   = (((p ^ k1) ^ k2) ^ k1) ^ k2   = p ^ k1 ^ k2 ^ k1 ^ k2         // 利用结合律   = p ^ (k1 ^ k2) ^ (k1 ^ k2)     // 再利用结合律，把k1 ^ k2看成整体，就是加密之后再解密了   = p   //也能够这样证实   = p ^ k1 ^ k2 ^ k1 ^ k2            = p ^ (k1 ^ k1) ^ (k2 ^ k2)     // 利用交换律   = p ^ 0 ^ 0                     // 利用本身与本身异或为0   = p                             // 利用任何值与0异或为其本身

数据备份

应用XOR也能够很容易实现多个数据的互备，如下：
如果有数据a、b、c，则z = a ^ b ^ c，而后把数据z备份下来。

  • 当a失落时，可应用z ^ b ^ c来复原。
  • 当b失落时，可应用z ^ a ^ c来复原。
  • 当c失落时，可应用z ^ a ^ b来复原。

这真是太神奇了，备份了一份数据z后，失落了任何一份数据，都能够通过数据z与其它数据一起复原回来，而磁盘阵列技术raid5的数据备份原理，就是用的这个个性。

实现异或

因为在布尔代数中，其实只须要与、或、非运算就能够实现所有其它运算，所以异或其实也是能够通过与、或、非实现的，最直观的实现形式如下：

a ^ b = (~a & b) | (a & ~b)

ok，异或的应用场景就介绍到这了，还有没有其它神奇的使用场景呢？如果有，可留言告知下

往期内容

密码学入门
接口偶然超时，竟又是JVM进展的锅！
耗时几个月，终于找到了JVM进展十几秒的起因
mysql的timestamp会存在时区问题？
真正了解可反复读事务隔离级别
字符编码解惑