理解异或 Exclusive or

常见的逻辑操作:与、或、非大家应该都熟悉,也非常容易理解。在高中数学中也学习过一些布尔代数的知识。在逻辑电路中(位操作)与、或、非同样也非常容易理解。但是逻辑电路中增加了一个非常重要的运算异或(XOR),常见的教科书只是介绍了异或的定义,于是大多数人只记住了异或的运算规则是什么,但是对异或的含义和使用场景理解却很模糊。因此本文尝试介绍异或的意义,希望能够帮助大家理解异或。

异或的逻辑意义

先从熟悉的“或”说起,“或”表示两个条件中有一个为真,那么结论就为真。比如:当日购物金额满一千或单笔消费满五百可以参与抽奖,两个条件有一个满足结果就为真。但是我们在日常生活中还有一种“或”,两个结果不能同时成立。比如:明天我在北京或上海。我可以在北京,可以在上海,但是我不能既在北京又在上海,两个条件不能同时成立。
因此从结果上看,异或的计算规则就是如果两个条件中有一个为真,结果为真。两个都为真、都为假,结果为假。
或

异或
如果从文氏图上看,两个条件里不相交的部分为真,两个条件里不一样的部分为真,把两个条件里相异的部分起来就是真值的范围。
那为什么基础逻辑运算中没有异或呢?因为异或并不是一个基础运算,异或是一个二级运算符,可以被等价成与或非运算:

逻辑电路中的异或

计算机的数学理论基础是布尔代数,物理基础则是逻辑电路。从理论上看,逻辑运算只需要三个运算符就可以被表示,但是在工程上就要考虑另一件事了:复用!当工程师发现在计算机中需要经常用到一种复合运算,于是就把这种复合运算的函数抽取出来,单独封装。异或就是逻辑电路中的一种基础运算。
最初计算机的设计目的就是为了计算产生的。计算最基础的一项功能是加法。我们观察一下加法在二进制层面的实现:
我们从最简单的个位数加法来看:

0 + 0 =  0 
1 + 1 = 10
0 + 1 =  1
1 + 0 =  1

个位数字的结果就是异或运算的结果:如果两个输入相同,结果是 0;如果输入不同(有一位为 1),结果是 1。
当然还要考虑进位的情况了:

   10
+  11
-----
= 101

因此一个加法器的每一位的和等于两个数的输入、进位的异或结果。进位则等于输入数字的与结果(如果两个数字都为 1,进位为 1)。
因为计算机中的基础加法运算需要使用异或运算,因此逻辑电路中异或门是一个基本组成。

异或性质与应用

异或有一个特有的性质:计算结果由两个输入共同影响。因为结果和两个输入都有关系,如果已知异或结果和一个输入,可以逆推出另一个输入。
这个性质我们对比一下与和或:

  • 或:只要有一个输入为 1,那么另外一个输入无论是 0 或 1 ,结果都为 1
  • 与:只要有一个输入为 0,那么另外一个输入无论是 0 或1 ,结果都为0 (短路效应)

异或的运算结果,无论一个输入是 0 还是 1,都需要知道另外一个输入才能知道结果。有点像钥匙和锁,一定要配对后才能解锁。

异或密码

这个特性在加密算法中特别重要。我们生成了一组密钥,用这个密钥对明文进行一次异或,就得到了一个密文。只要这个密钥不泄露,那么得到了密文也无法计算出明文。
如果是与,如果明文是 0,那么无论密钥是什么,运算结果都是 0。得到密钥和密文也无法逆推出明文。

异或校验

因为异或结果由两个输入共同决定,因此如果知道异或的结果,和一个输入就能知道另外一个输入是什么。比如我们知道异或结果为 1,一个输入为 0。意味着输入中有一个 1,一个为 0,那么另外一个值就是 1 了。
这里再介绍两个个推论,一个数异或上自己结果为 0。因为自己和自己的每一位都是相同的,所以结果为 0。一个数异或上 0 等于自己。这两个性质叫做归零律和恒等律 :

P  P = 0
P  0 = P

下面证明一下知道异或结果和一个输入,怎么求出另外一个输入:

a  b = c
a  b  b = c  b
// 因为 b  b 结果为 0 简化为
a  0 = c  b
a = c  b

真巧啊!异或的结果对一个输入进行一次异或运算就能得到另外一个输入。
这个性质对于数据备份真是帮了大忙了!
比如:两个 3 位二进制序列 101 和 011 进行异或奇偶校验可得到异或校验和 110。若序列 101 丢失,我们可以将已知序列 011 与异或校验和进行异或运算得到丢失的序列。
比如我们有一个硬盘的数据需要备份,但是如果每个硬盘都备份一次就太浪费了。我们可以选择两个硬盘进行异或,保存结果。只要两个硬盘不是同时坏掉那么就可以恢复数据(我承认我有赌的成分)。

面试题

面试题中有一些涉及到位运算,最高频的还是异或的运算了。
典型的一题是LeetCode: 136. 只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

如果用常规的方法免不了需要用额外的空间来统计数字出现的次数。如果利用异或的归零律,每个数字进行异或运算,最后的结果就是只出现了一次的数字:

public int singleNumber(int[] nums) {
    int single = 0;
    for (int num : nums) {
        single ^= num;
    }
    return single;
}

这个特性还有一个更难一点的面试题是《剑指 Offer》中的 56 - 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

这题的解法也是利用异或的特性。解法是分组异或,如果我们把要找的两个数字分到两个组里,两组数字各自异或的结果就是要找的两个数字。
那么怎么把这两个数字分到两个组里呢?还是利用异或的性质:如果两个数字的异或结果为 1,说明两个数字不同。我们先求出整个数组的异或值,这个异或的值等于 a ⊕ b。然后取出结果中为 1 的位数。按照这个位数是 0 还是 1 对数组进行分组,那么这两个要找的数字就会被分到两组数字里。

public int[] singleNumbers(int[] nums) {
    int ret = 0;
    for (int n : nums) {
        ret ^= n;
    }
    int div = 1;
    // 找出异或结果中值为 1 的位数是左移第几位
    while ((div & ret) == 0) {
        div <<= 1;
    }
    int a = 0, b = 0;
    for (int n : nums) {
        if ((div & n) != 0) {
            a ^= n;
        } else {
            b ^= n;
        }
    }
    return new int[]{a, b};
}
© 著作权归作者所有
这个作品真棒,我要支持一下!
奇志技术团队博客 http://meshtech.co/
0条评论
top Created with Sketch.