异或运算XOR 教程- 阮一峰的网络日志

XOR 是exclusive OR 的缩写。

英语的exclusive 意思是"专有的，独有的"，可以理解为XOR 是更单纯的OR 运算。

我们知道，OR 运算的运算子有两种情况， ... 阮一峰的网络日志»首页»档案 上一篇：科技爱好者周刊（第 1 下一篇：科技爱好者周刊（第 1 分类： 理解计算机 ⇐   ⇒ 异或运算XOR教程 作者：阮一峰 日期：2021年1月27日 大家比较熟悉的逻辑运算，主要是"与运算"（AND）和"或运算"（OR），还有一种"异或运算"（XOR），也非常重要。

本文介绍异或运算的含义和应用。

一、含义 XOR是exclusiveOR的缩写。

英语的exclusive意思是"专有的，独有的"，可以理解为XOR是更单纯的OR运算。

我们知道，OR运算的运算子有两种情况，计算结果为true。

（1）一个为true，另一个为false; （2）两个都为true。

上面两种情况，有时候需要明确区分，所以引入了XOR。

XOR排除了第二种情况，只有第一种情况（一个运算子为true，另一个为false）才会返回true，所以可以看成是更单纯的OR运算。

也就是说，XOR主要用来判断两个值是否不同。

XOR一般使用插入符号（caret）^表示。

如果约定0为false，1为true，那么XOR的运算真值表如下。

0^0=0 0^1=1 1^0=1 1^1=0 二、运算定律 XOR运算有以下的运算定律。

由于非常简单，这里就省略证明了。

（1）一个值与自身的运算，总是为false。

x^x=0 （2）一个值与0的运算，总是等于其本身。

x^0=x （3）可交换性 x^y=y^x （4）结合性 x^(y^z)=(x^y)^z 三、应用 根据上面的这些运算定律，可以得到异或运算的很多重要应用。

3.1简化计算 多个值的异或运算，可以根据运算定律进行简化。

a^b^c^a^b =a^a^b^b^c =0^0^c =c 3.2交换值 两个变量连续进行三次异或运算，可以互相交换值。

假设两个变量是x和y，各自的值是a和b。

下面就是x和y进行三次异或运算，注释部分是每次运算后两个变量的值。

x=x^y//(a^b,b) y=x^y//(a^b,a^b^b)=>(a^b,a) x=x^y//(a^b^a,a)=>(b,a) 这是两个变量交换值的最快方法，不需要任何额外的空间。

3.3加密 异或运算可以用于加密。

第一步，明文（text）与密钥（key）进行异或运算，可以得到密文（cipherText）。

text^key=cipherText 第二步，密文与密钥再次进行异或运算，就可以还原成明文。

cipherText^key=text 原理很简单，如果明文是x，密钥是y，那么x连续与y进行两次异或运算，得到自身。

(x^y)^y =x^(y^y) =x^0 =x 3.4数据备份 异或运算可以用于数据备份。

文件x和文件y进行异或运算，产生一个备份文件z。

x^y=z 以后，无论是文件x或文件y损坏，只要不是两个原始文件同时损坏，就能根据另一个文件和备份文件，进行还原。

x^z =x^(x^y) =(x^x)^y =0^y =y 上面的例子是y损坏，x和z进行异或运算，就能得到y。

四、一道面试题 一些面试的算法题，也能使用异或运算快速求解。

请看下面这道题。

一个数组包含n-1个成员，这些成员是1到n之间的整数，且没有重复，请找出缺少的那个数字。

最快的解答方法，就是把所有数组成员（A[0]一直到A[n-2]）与1到n的整数全部放在一起，进行异或运算。

A[0]^A[1]^...^A[n-2]^1^2^...^n 上面这个式子中，每个数组成员都会出现两次，相同的值进行异或运算就会得到0。

只有缺少的那个数字出现一次，所以最后得到的就是这个值。

你可能想到了，加法也可以解这道题。

1+2+...+n-A[0]-A[1]-...-A[n-2] 但是，加法的速度没有异或运算快，而且需要额外的空间。

如果数字比较大，还有溢出的可能。

下面是一道类似的题目，大家可以作为练习。

一个数组包含n+1个成员，这些成员是1到n之间的整数。

只有一个成员出现了两次，其他成员都只出现一次，请找出重复出现的那个数字。

五、参考链接 ThatXORTrick （完） 文档信息 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证） 发表日期：2021年1月27日 相关文章 2022.06.03:字节序探析：大端与小端的比较 今天谈谈一个重要的计算机概念，大家可能都听说过它，但是很少深究，那就是字节序（Endianness）。

2022.02.04:万兆家庭网络的时代 最近，我想将家里的网络设备，都升级到千兆。

2021.12.07:为什么Web3与区块链有关 互联网迄今有两个阶段：Web1.0和Web2.0。

2019.11.17:容错，高可用和灾备 标题里面的三个术语，很容易混淆，专业人员有时也会用错。

留言（31条） mguy 说： 请问在浏览器测试1^2的值是3,是什么原因啊 2021年1月27日10:16 |# |引用 mguy 说： 引用mguy的发言： 请问在浏览器测试1^2的值是3,是什么原因啊 明白了,二进制... 2021年1月27日10:18 |# |引用 woodong 说： 请问一下，为什么是A[n-2]？不是A[n-1]？n-2好像算出来的结果不对。

2021年1月27日10:41 |# |引用 woodong 说： 引用woodong的发言： 请问一下，为什么是A[n-2]？不是A[n-1]？n-2好像算出来的结果不对。

明白了，因为缺少一个数 2021年1月27日10:51 |# |引用 saheibe 说： 用异或加密，有2个原文和对应的加密结果就可以反推出密钥。

2021年1月27日12:48 |# |引用 王大炮 说： 写得好，非常好 2021年1月27日14:00 |# |引用 MAXIM 说： 引用saheibe的发言： 用异或加密，有2个原文和对应的加密结果就可以反推出密钥。

怎么反推? 2021年1月27日16:26 |# |引用 emon100 说： 异或交换最省空间，但不一定正确。

如下是一段会出问题的C语言代码，出问题的原因是交换时a,b指针指向同一个变量v intv=1; int*a=&v,*b=&v; (*a)=(*a)^(*b); (*b)=(*a)^(*b); (*a)=(*a)^(*b); printf("%d",v);//0 使用普通方法交换时并不会出问题 intv=1; int*a=&v,*b=&v; inttmp; tmp=*a; *a=*b; *b=tmp; printf("%d",v);//1 2021年1月27日17:44 |# |引用 andy 说： 贴上力扣上缺失的数字题目https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/ 2021年1月27日21:55 |# |引用 Rivalsa 说： 引用saheibe的发言： 用异或加密，有2个原文和对应的加密结果就可以反推出密钥。

我怎么感觉一个原文和加密结果就能算出密钥呢？ 2021年1月28日08:11 |# |引用 江月 说： 请问大家，'a1'^'a2'==0是什么原因？ 2021年1月28日09:36 |# |引用 何必 说： 看到老师分享链接的文章也很有意思翻译&补充了一下有兴趣的小伙伴可以看看呀https://juejin.cn/post/6922667752972894221/ 2021年1月28日12:53 |# |引用 郭帅 说： 最后一道题目的答案：先把这N+1个数字全部XOR，得到的值再和1到N都XOR一下，最终结果就是重复的数。

（因为它出现了三次，未抵消；其他数都只出现了两次，抵消。

） 2021年1月28日20:50 |# |引用 mfk 说： 那个例子和答案不对。

例如：1，2，3，4中我少了4，你1^2^3=0，根本就不是正确的答案。

你给的答案是“有很多数字每个出现2次，只有一个数字只出现了1次，请找出只出现1次的那个数字”这个题的。

2021年1月29日09:31 |# |引用 Rigyoku 说： 解法写的是1^2^3^1^2^3^4和你后面说的应该是一个意思没问题 2021年1月29日16:38 |# |引用 Dove 说： 使用异或交换两个数字虽然不需要一个额外变量，但是并不能带来性能的提升。

（可以从编译后的汇编码中求证）而且这种写法容易导致一种问题，就是swap(&a,&a)这种调用会导致a变为0，因此不推荐使用。

另外”加法的速度没有异或运算快，而且需要额外的空间”这句话不一定正确。

现代计算机中加法和异或运算是一样快的，都只要一个cpu时钟周期。

不过处于对溢出的考虑，加法相对不可靠。

2021年2月1日13:15 |# |引用 ksy 说： 点赞，之前老是感觉异或有些懵，感觉就差一点理解，现在真的是一点就透啊; 2021年2月2日11:11 |# |引用 Locust 说： @emon100： 这个是两个值的交换，你这个是因为引入了第三个值v，而且跟指针和引用有关系 2021年2月8日11:07 |# |引用 齐仁 说： 'a'^'b'在js中为什么不是将字符串转为二进制后进行异或运算？是有什么隐情在里面吗？ 2021年3月2日15:26 |# |引用 胡糊糊 说： 最后那道练习的解法应该是把所有数组成员（A[0]一直到A[n]）与1到n的整数全部放在一起，进行异或运算。

这样重复的那个数字应该会出现3次，异或计算以后只剩下一次，得到这个数字。

编程初学者，不知道解的对不对，望赐教。

2021年3月5日22:05 |# |引用 乱敲代码 说： 真的是想什么，阮大发什么。

最近正在看这块的知识 2021年4月22日15:35 |# |引用 hf 说： 哈哈哈，牛批哦！一直没仔仔细细看XOR的用法分析，今天看到了，很有意思。

2021年6月23日14:29 |# |引用 草色青青 说： 引用Rivalsa的发言： 我怎么感觉一个原文和加密结果就能算出密钥呢？ 用全是1的明文去异或加密得到的加密结果就是秘钥的反，再求反就得到了密文 ^(1^cipherkey) 2021年10月5日15:03 |# |引用 梅子奕 说： 引用mguy的发言： 请问在浏览器测试1^2的值是3,是什么原因啊 请问咋用浏览器测试异或？ 2021年11月2日16:34 |# |引用 K 说： 引用梅子奕的发言： 请问咋用浏览器测试异或？ 就f12在控制台console输出就行了啊 2021年11月9日13:56 |# |引用 edte 说： 最后一题和给的例子是一样的，重复的直接异或为0，然后0^x=x，所以和缺失一个数字是一样的。

直接与1.2.3...n异或即可。

2021年11月15日10:41 |# |引用 阳络 说： 3.4数据备份。

数据备份直接生成x的copy不就好了么？没明白为什么要异或成z进行备份？（奥卡姆剃刀原理，如无必要勿增实体） 2021年12月13日06:47 |# |引用 bgfist 说： 引用Rivalsa的发言： 我怎么感觉一个原文和加密结果就能算出密钥呢？ 问题是都加密了，怎么还能得到原文呢 2022年1月8日17:29 |# |引用 liweizheng 说： @mfk： 这俩本来就是一个问题啊，是你的解法不对，要把所有数都^起来。

2022年1月20日14:59 |# |引用 liweizheng 说： 引用bgfist的发言： 问题是都加密了，怎么还能得到原文呢 这是异或的性质啊 2022年1月20日15:01 |# |引用 Kyle_Jehring 说： @emon100： 这种情况是因为在一个地址空间中对自身做异或，因此肯定会出问题 结局方案就是在交换之前判断一下a、b指针是否指向同一片地址空间 if(a==b)return; 按照原文的说法X、Y是两个变量，默认在栈中分配了两个地址，因此原文没问题 2022年6月26日12:13 |# |引用 我要发表看法 您的留言 （HTML标签部分可用） 您的大名： «-必填 电子邮件： «-必填，不公开 个人网址： «-我信任你，不会填写广告链接 记住个人信息？ 正在发表您的评论，请稍候 «-点击按钮 Weibo| Twitter| GitHub Email:[email protected]