原创:扣钉日记(微信大众号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
  1. 任何值与0异或,成果为其本身
x ^ 0 = x
  1. 交流律
x ^ y ^ z = x ^ z ^ y
  1. 结合律
x ^ y ^ z = x ^ (y ^ z)

异或的运算定律比较简略,就不写数学证明了,感兴趣可到网上搜索。

完成加减法

XOR的第一种运用场景便是完成加减法,在咱们上小学时,应该都学过进位加法退位减法来做加减运算,咱们来温习一下吧。

  • 进位加法:
    当某一位上两数之和大于10时,需求进位,即高位上要多加一个1。
    异或的4种堪称神奇的运用场景
  • 退位减法:
    当某一位上两数相减不行时,需求退位,即从高位上借(减)一个1,来当作10用。
    异或的4种堪称神奇的运用场景

异或其实与这个类似,不过它不会产生进位与退位,如下:

  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发送给了服务端,且中间通讯数据都是加密的。
    异或的4种堪称神奇的运用场景

    整个进程能够看做先是两边都在密文中做了一次加密,然后两边又逐步解开。

证明其正确性也很简略,只需求将式子代入一下即可,如下:

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会存在时区问题?
真实了解可重复读事务阻隔级别
字符编码解惑