知乎回答 · 2020

如何理解「异或(XOR)」运算在计算机科学中的重要性?

11 条评论 ↗216 个赞同 · 157 个收藏查看知乎原文 ↗

简单的说,如果没有异或运算,计算机科学的信息处理能力将大打折扣。

首先要理解异或的概念,但教科书上的公式和概念说的太抽象,我就不抄了,还是看一个实际的例子吧。

我们都玩过“找不同”游戏,例如下面的两张图片,你能找出几个不同的地方?

如何理解「异或(XOR)」运算在计算机科学中的重要性?配图

找不同

我相信你能找出很多不同之处,比如女孩头上的发饰等等。

这种发现“差异”的过程,就是异或运算,当找到了所有的差异,再也找不出新的差异时,异或运算就计算完成。

异或运算的作用就是帮我们从两堆相似的信息中,发现一些不同的信息。因为相同的信息往往是已知的旧信息,而不同的信息是未知的新信息,这是一个信息增量的过程。

这个信息增量有什么用呢?

太有用了,对大部分生物来说,这些新信息甚至是性命攸关的信息。

自然中的异或计算

除了我们人类能进行异或计算,其实动物也可以,比如这只蝴蝶 。

如何理解「异或(XOR)」运算在计算机科学中的重要性?配图

徒手抓蝴蝶的调皮少女,我女儿(^-^)

小时候徒手抓蝴蝶的诀窍是什么?

当然不是冲过去乱抓,要蹑手蹑脚慢慢走近,当罪恶之手一点点靠近翅膀的时候,猛的一下捏住……

可为什么慢慢走近是有效的,快速跑过去就把蝴蝶吓跑了?

这是因为动物的视觉依靠异或运算来发现运动物体。

  • 对于不动的物体比如建筑,或运动很慢的物体比如云彩,因为变化的差异太小,大脑无法将其从背景里分离,会自动化的进行忽略。
  • 对于快速运动的物体,比如飞来的鸟,大脑发现他和背景有明显的变化差异,认为这是潜在威胁,会自动化的关注,并快速的逃离。

如何理解「异或(XOR)」运算在计算机科学中的重要性?配图

运动物体检验Moving Object Detection

图片出处:https://arxiv.org/pdf/1901.03360.pdf

所以异或运算对动物性命攸关,它们要时刻比较周围的环境信息,把不运动的环境信息忽视掉,专注那些有差异的信息。因为一般来说,静止的是安全的,运动的很可能是危险的,是需要高度警觉的。

当然这一点也会被更聪明的捕食者利用,他们通过隐藏在环境信息中来麻痹猎物。

小孩要是快速接近蝴蝶,会被蝴蝶的视觉异或算法发现,引起高度注意和警觉。而缓慢的靠近蝴蝶则伪装成了自然背景,成功的欺骗了蝴蝶。

当然实际的大脑或电脑的计算算法远比异或复杂,也不仅仅用到异或这一种运算。但其目的都是通过比较前后的信息,来找不同,发现信息中的增量。

天文学家可以用异或运算来发现新的天体

这是一个“天文学找找看游戏”。

下面两张照片是同一片星空,但是不同时间的拍摄照片。亮点大部分是恒星,位置不动,有一颗则是小行星谷神星,它在两个照片中的位置不同,你能找出来吗?

如何理解「异或(XOR)」运算在计算机科学中的重要性?配图

如何理解「异或(XOR)」运算在计算机科学中的重要性?配图

找到了吗,是不是很难?

反正我没找到,在没有计算机之前,可以想像天文学家找移动天体有多难。

但是有了计算机,我们可以对两个图片做异或运算,把两张照片中相同的数据删除,只留下不同的数据,我们就得到处理后的两张照片。

如何理解「异或(XOR)」运算在计算机科学中的重要性?配图

如何理解「异或(XOR)」运算在计算机科学中的重要性?配图

我们很快就要找的了新信息,发现了移动的谷神星。

如何理解「异或(XOR)」运算在计算机科学中的重要性?配图

以上图片的出处:https://www.benengebreth.org/dynamic-sky/ceres/

用维恩图可以演示异或运算的过程

如何理解「异或(XOR)」运算在计算机科学中的重要性?配图

你通过前面的例子和韦恩图,你会发现异或运算能大幅度减少冗余信息。

而计算机科学属于信息科学,在信息处理时就经常需要异或运算来提高效率。

异或运算可以用来压缩数据

我们知道,视频文件是由很多图片帧组成的,相邻的帧之间有很多重复的数据,我们可以用异或把这些冗余的数据去除,只留下帧和帧之间不同的数据。

如何理解「异或(XOR)」运算在计算机科学中的重要性?配图

去掉冗余数据后,图片帧里的数据就减少了很多

如何理解「异或(XOR)」运算在计算机科学中的重要性?配图

图片出处:https://www.i3m-detectors.i3m.upv.es/wp-content/uploads/2019/10/20191106-SeminarioHEM.pdf

这样就可以大幅度压缩视频文件的尺寸。

异或这种信息压缩功能用在通讯上,可以减少通讯量,因为不用传递重复的数据。

用在计算上,则可以减少计算量,因为不用进行重复的计算。

异或运算除了压缩信息,还可以用在加密和解密,数字电路,人工神经网络,这里就不再一一列举,相信这几个例子已经足够大家理解异或在计算机科学中的重要性。

总结

  1. 异或其实就是找不同。
  2. 异或运算在自然中随处可见,对动物来说,异或能提供性命攸关的信息。
  3. 人们利用异或的运算特性,在重复数据中去除冗余信息,实现信息增量和数据压缩。

在信息领域的硬件、软件设计中,异或是不可或缺的存在。

知乎原文