异或运算 XOR 教程

作者: 阮一峰

日期: 2021年1月27日

大家比较熟悉的逻辑运算,主要是"与运算"(AND)和"或运算"(OR),还有一种"异或运算"(XOR),也非常重要。

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

一、含义

XOR 是 exclusive OR 的缩写。英语的 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 交换值

两个变量连续进行三次异或运算,可以互相交换值。

假设两个变量是xy,各自的值是ab。下面就是xy进行三次异或运算,注释部分是每次运算后两个变量的值。


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 之间的整数。只有一个成员出现了两次,其他成员都只出现一次,请找出重复出现的那个数字。

五、参考链接

(完)

留言(21条)

请问在浏览器测试 1 ^ 2的值是3,是什么原因啊

引用mguy的发言:

请问在浏览器测试 1 ^ 2的值是3,是什么原因啊

明白了,二进制...

请问一下,为什么是 A[n-2]? 不是A[n-1] ? n-2 好像算出来的结果不对。

引用woodong的发言:

请问一下,为什么是 A[n-2]? 不是A[n-1] ? n-2 好像算出来的结果不对。

明白了,因为缺少一个数

用异或加密 ,有2个原文和对应的加密结果就可以反推出密钥。

写得好,非常好

引用saheibe的发言:

用异或加密,有2个原文和对应的加密结果就可以反推出密钥。

怎么反推?

异或交换最省空间,但不一定正确。
如下是一段会出问题的C语言代码,出问题的原因是交换时a,b指针指向同一个变量v


int v=1;
int *a=&v,*b=&v;
(*a)=(*a)^(*b);
(*b)=(*a)^(*b);
(*a)=(*a)^(*b);
printf("%d",v);// 0

使用普通方法交换时并不会出问题


int v=1;
int *a=&v,*b=&v;
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
printf("%d",v);// 1

贴上 力扣上缺失的数字题目 https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/

引用saheibe的发言:

用异或加密,有2个原文和对应的加密结果就可以反推出密钥。

我怎么感觉一个原文和加密结果就能算出密钥呢?

请问大家,'a1' ^ 'a2' == 0 是什么原因?

看到老师分享链接的文章也很有意思 翻译&补充了一下 有兴趣的小伙伴可以看看呀 https://juejin.cn/post/6922667752972894221/

最后一道题目的答案:先把这 N + 1 个数字全部 XOR,得到的值再和 1 到 N 都 XOR 一下,最终结果就是重复的数。(因为它出现了三次,未抵消;其他数都只出现了两次,抵消。)

那个例子和答案不对。
例如:1,2,3,4中我少了4,你 1^2^3=0,根本就不是正确的答案。

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

解法写的是1^2^3^1^2^3^4 和你后面说的应该是一个意思 没问题

使用异或交换两个数字虽然不需要一个额外变量,但是并不能带来性能的提升。(可以从编译后的汇编码中求证)而且这种写法容易导致一种问题,就是 swap(&a, &a) 这种调用会导致a变为0,因此不推荐使用。

另外”加法的速度没有异或运算快,而且需要额外的空间”这句话不一定正确。现代计算机中加法和异或运算是一样快的,都只要一个cpu时钟周期。不过处于对溢出的考虑,加法相对不可靠。

点赞,之前老是感觉异或有些懵,感觉就差一点理解,现在真的是一点就透啊;

@emon100:

这个是两个值的交换,你这个是因为引入了第三个值v,而且跟指针和引用有关系

'a'^'b'在js中为什么不是将字符串转为二进制后进行异或运算?是有什么隐情在里面吗?

最后那道练习的解法应该是把所有数组成员(A[0] 一直到 A[n])与 1 到 n 的整数全部放在一起,进行异或运算。这样重复的那个数字应该会出现3次,异或计算以后只剩下一次,得到这个数字。

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

真的是想什么,阮大发什么。最近正在看这块的知识

我要发表看法

«-必填

«-必填,不公开

«-我信任你,不会填写广告链接