异或算法的含义

[hankviv]

作者：张英锋 链接：https://www.zhihu.com/question/31116687/answer/964367526 来源：知乎 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

异或是一个有趣而又重要的概念，首先，它是一种运算（Operation），其次，它隐藏在自然和生活的秩序中，很多人不了解它的含义和价值。先看一个小例子：小时候我们都玩过“找不同”游戏，例如下面的两张图片，你能找出几个不同的地方？找不同游戏图片出处维基百科：https://en.wikipedia.org/wiki/Spot_the_difference我相信你能找出很多不同之处，比如墙上的钟表、图画、老奶奶头发上的发簪等等。这种在两个图片中发现不同或者“差异”的过程，就是异或运算，当找到了所有的差异，再也找不出新的差异时，异或运算就计算完成。异或运算的作用就是帮我们从两堆相似的信息中，发现一些新的信息。因为相同的信息往往是已知的旧信息，而不同的信息是未知的新信息，这是一个信息增量的过程。这个信息增量有什么用呢？太有用了，对大部分生物来说，这些新信息甚至是性命攸关的信息。自然中的异或计算除了我们人类能进行异或计算，其实动物也可以，比如这只蝴蝶 。徒手抓蝴蝶的调皮少女，我女儿(^-^)小时候徒手抓蝴蝶的诀窍是什么？当然不是冲过去乱抓，要蹑手蹑脚慢慢走近，当罪恶之手一点点靠近翅膀的时候，猛的一下捏住……可为什么慢慢走近是有效的，快速跑过去就把蝴蝶吓跑了？这是因为动物的视觉依靠异或运算来发现运动物体。对于不动的物体比如建筑，或运动很慢的物体比如云彩，因为变化的差异太小，大脑无法将其从背景里分离，会自动化的进行忽略。对于快速运动的物体，比如飞来的鸟，大脑发现他和背景有明显的变化差异，认为这是潜在威胁，会自动化的关注，并快速的逃离。运动物体检验Moving Object Detection图片出处：https://arxiv.org/pdf/1901.03360.pdf小孩要是快速接近蝴蝶，会被蝴蝶的视觉异或算法发现，引起高度注意和警觉。而缓慢的靠近蝴蝶则伪装成了自然背景，成功的欺骗了蝴蝶。当然实际算法比这个复杂，可以近似的说是一种异或运算。所以异或运算对动物性命攸关，它们要时刻比较周围的环境，一般来说，静止的是安全的，运动的很可能是危险的，是需要高度警觉的。当然这一点也会被更聪明的捕食者利用。除了自然生物，异或运算在社会生活中还有哪些用途？在信息科学领域，到处可以看到异或运算。天文学家可以用异或运算来发现新的天体这是一个“天文学找找看游戏”。下面两张照片是同一片星空，但是不同时间的拍摄照片。亮点大部分是恒星，位置不动，有一颗则是小行星谷神星，它在两个照片中的位置不同，你能找出来吗？找到了吗，是不是很难？反正我没找到，在没有计算机之前，可以想像天文学家找移动天体有多难。但是有了计算机，我们可以对两个图片做异或运算，把两张照片中相同的数据删除，只留下不同的数据，我们就得到处理后的两张照片。我们很快就要找的了新信息，发现了移动的谷神星。以上图片的出处：https://www.benengebreth.org/dynamic-sky/ceres/用维恩图可以演示异或运算的过程异或运算还可以用来压缩数据我们知道，视频文件是由很多图片帧组成的，相邻的帧之间有很多重复的数据，我们可以用异或把这些冗余的数据去除，只留下帧和帧之间不同的数据。去掉冗余数据后，图片帧里的数据就减少了很多图片出处：https://www.i3m-detectors.i3m.upv.es/wp-content/uploads/2019/10/20191106-SeminarioHEM.pdf这样就可以大幅度压缩视频文件的尺寸。异或运算的用途非常多，例如在加密算法、数字电路、人工神经网络中都有异或的身影，这里就不再一一列举，相信这几个例子已经足够大家理解异或的含义和价值。总结异或其实就是找不同。异或运算在自然中随处可见，对动物来说，异或能提供性命攸关的信息。人们利用异或的运算特性，在重复数据中去除冗余信息，实现信息增量和数据压缩。在信息领域的硬件、软件设计中，异或是不可或缺的存在。

[hankviv]

转载来源 如何理解「异或」的含义？ - 张英锋的回答 - 知乎 https://www.zhihu.com/question/31116687/answer/964367526