Magic Exclusive OR

楔子

作为CS的学生,我们应该都了解异或(Exclusive OR),也许是位运算,也许是那张真值表:

A B $\bigoplus$
F F F
F T T
T F T
T T F

但最近CodeForces上的一道题又让我对它产生了新的思考。它和模有什么关系?这个运算的本质又是什么?

从群论上说:

异或是$\mathbb{Z}_2$群的加法运算,满足加法结合律和交换律。

emm,换一种数论的说法:

在模2剩余系中进行加法运算。

所以,它其实和加法有一些类似。

第一章

还记得那个不使用另外的变量交换两个变量的著名trick嚒?

没有深入理解的时候你也许会诧异,

a = a ^ b
b = a ^ b
a = a ^ b

列个表也许更清楚?

Expression a b
init a b
a = a ^ b a ^ b b
b = a ^ b a ^ b a ^ b ^ b = a
a = a ^ b a ^ b ^ a = b a
result b a

所以它其实只是利用了异或的交换律和结合律,当然你不考虑溢出的话用加法也能轻松实现。

a = a + b
b = a - b
a = a - b

Notes:

这种异或的交换其实并不推荐。

一是现在的编译器已经足够优秀来优化朴素的交换了(汇编代码显示了由于中间变量存在寄存器中异或的方法一定不会更快),还增加了阅读的难度;

二是其实这样做有一个坑:

你交换两个相同数值的变量没有问题,第一步的零异或其他值还是其他值

但如果是同一个的引用的话,第二步就变成零异或零了,最后就会变成零了。

第二章

另外,利用异或的归零律,我们能写出比a - b == 0更高效的快速比较a ^ b == 0

在汇编中,异或也常用来变量的置零:a = a ^ a

在校验中,异或可以方便的进行奇偶校验:对二进制数进行按位异或,判断1的奇偶性。

在面试中,也常常出现异或的题目:

一个整型数组除了$N$个数字出现一次外其余均出现两次,找出这$N$个数字。

($N = 2, 3$)

一个朴素的解法是通过复杂度为$O(nlgn)$的排序,但是通过异或,我们可以在$O(n)$内解决这个问题。

对数组每一项异或,出现偶数次就变成零了,剩下的就是出现奇数次的数的异或。

我们先考虑一下$N=2$的情况:异或后的结果某一位为$1$表示奇数次的数在这一位上不一样。我们只需要对整个数组这一位为$1$的数进行异或,即可得到一个奇数次的数。

再来考虑$N=3$的情况:

对于一个$len$长的数组,我们知道它的每一项$a[i], (0 \leq i < n)$,

不妨假设$a, b, c$三个数出现一次,其他数出现两次,那我们还知道这三个数的异或结果$(a \wedge b \wedge c)$。

现在我们要在$O(n)$的时间内找出这三个数。

首先来个引理:

$(a \wedge b \wedge c) = 0 \Rightarrow$ $a, b, c$ 中两个数的最低的为$1$位相同,与另一个数不同。

因为$(a \wedge b \wedge c) = 0$,故而在每一位的异或上,都有两个相同,与另一个不同。

记$(a \wedge b \wedge c) = XOR$,考虑

$$(XOR \wedge a) \wedge (XOR \wedge b) \wedge (XOR \wedge c) = (b \wedge c) \wedge (a \wedge c) \wedge (a \wedge b) = 0$$

故由引理:上式中三数有两个最低1位的位置相同。

对于整个数组,我们用$XOR$的最低1位去异或数组中每一个数,数组中的数要么出现两次,要么那两个数在这一位上相同,得出在这一位上不同的数在这一位上的值。

然后再次用$XOR$异或遍历整个数组,在得到的$XOR \wedge a[i]$中找出上一步中对应位为该值的情况。然后互相异或排除掉出现两次的干扰数据,得到在最低1位上不相同的(例如为$a$)的$(XOR \wedge a)$,再去异或$XOR$即可。

有了$a$以后,知道了$b \wedge c$的结果,就可以通过之前的方法(比如给数组再加个$a$),轻易地求出$b$和$c$。

后记

CF的解答我就放在专门的post里了。

Reference

https://www.zhihu.com/question/62003033

https://www.lijinma.com/blog/2014/05/29/amazing-xor/

http://codeforces.com/contest/842/problem/D

Avatar
Yang Li
@zjzsliyang