异或运算相关(坑)

异或(exlusive OR, XOR, \( \oplus \))是一种非常优美的逻辑/集合运算符。
数学上,对于两个取值为\(S = \{ 0,1 \} \)的量\( p, q \),异或被表示为$$
\begin{alignat}{1}
p \oplus q &=& (\lnot p \land q) &\lor& (p \land \lnot q) \\
&=& (p \lor q) &\land& (\lnot p \lor \lnot q) \\
&=& (p \lor q) &\land& \lnot (p \land q)
\end{alignat}
$$如果用Venn图来表示,就是这样:(From Wikipidia)

其实我们可以用更简洁的语言描述这个运算符$$
p \oplus q = [p \neq q]
$$或者$$
p \oplus q = (p + q) \mod 2
$$异或之所以优美,是因为这是一个满足以下性质的运算符:

(1)交换律$$
p \oplus q = q \oplus p
$$(2)结合律$$
(p \oplus q) \oplus r = p \oplus (q \oplus r)
$$(3)恒等率$$
p \oplus 0 = p
$$(4)归零率$$
p \oplus p = 0
$$性质(1), (2)使得异或的运算方式非常自由;
性质(3), (4)使得异或是自己的逆运算!简直太棒了。(再见吧逆元)

平常我们用到的xor(”^” in C)是对于每一个二进制位按位异或。比如$$
12 \ \mathrm{xor} \ 10 = 6
$$就是因为$$
(1100)_2 \ \mathrm{xor} \ (1010)_2 = (0110)_2
$$
对于这样的运算,可以有以下几种看法:

  1. 按位异或:将两个数按二进制位异或;
  2. 半加:将两个数做不进位的加法,并且因此有$$a + b = (a \ \mathrm{xor} \ b) + (a \ \mathrm{and} \ b) \times 2$$其中\( a \ \mathrm{and} \ b \)是进位的表示。进行这样的运算的逻辑运算单元被称为半加器;递归或者递推这个过程,可以通过\( \mathrm{and} \)和\( \mathrm{xor} \)完成加法;
  3. \( \mathbb{Z}_2 \)群的加减法:用群来描述(2),即异或是\( \mathbb{Z}_2 \)群的加法运算,同时也是减法运算(因为\( \mathrm{xor} \)是自己的逆运算);
  4. 存在性取反:将\( b \)存在的二进制位在\( a \)中取反;或者在集合运算中,将\(b\)集合在\(a\)集合中的存在性取反;
  5. 对称差:集合运算中\(a \oplus b\)表示\(a\)与\(b\)集合的对称差。

异或的美妙主要就体现在这些性质上,这也导致异或可以应用在许多令人赞叹的地方。

变量交换

本来这只是一个小trick,但是我第一次见到的时候还是感觉很奇妙的。
通常来说我们交换两个变量是这么做的:

这里用到了一个辅助空间来帮助我们完成交换。
当然,有一种方法可以使得任何可以加减的变量不借助辅助空间进行交换:

注意到+和-互为逆运算,因此可以考虑使用异或,来减少运算符种类。
我们惊奇地发现,如果使用异或,不仅只需要用到一种运算符,运算代价更小,而且可以交换任何可以由二进制表示的变量

异或密码

做题时经常见到这样令人绝望的话:

我们会通过一些方法使你的程序强制在线回答询问。

强制在线就不能愉快地用莫队了,并且根本不能用离线线段树了!(摔)

然而作为读入文件已经给定的OI来说,垃圾出题人不想写交互库是不可能真正在线查询的,所以就需要用一种特殊的方法对读入文件加密。通常来说,出题人都会使用异或作为加密方法。

异或加密是基于以下式子$$
A \oplus key = B \\
B \oplus key = A
$$这是一种典型的对称加密方法。

而在这些题目中,使得询问在线的方法是这样的

这就使得你的程序必须依次回答询问了,因为每一个询问都需要由上一个询问的答案作为\(key\)来解密。

同样的,在很多地方都可以用这种方法进行加密,因为其易于实现,而且计算成本小。

如果使用重复密码,即将明文异或一段循环的密文,那么如果密文和明文字符的长度相同,可以通过最简单的频率分析进行破译;如果循环节不同,那么将会有助于加密的强度,因为会增加频率分析的难度。当然更靠谱的方法是使用随机数流生成与密码等长的密码,只要保证密码本随机且一次性,得到的密文理论上是无法破解的。

不过由于异或是对称加密,在已知明文攻击下都是脆弱的,其应用必然没有非对称性加密算法广,所以异或密码也算是比较少见的了。

当然,利用这种对称性,不仅可以加密信息,还可以存储信息。一个非常著名的应用即是硬盘阵列RAID5。

普通的RAID1的工作原理是牺牲一半的空间作为镜像,同时写入工作盘和镜像盘,只从工作盘中读取数据;当其中一个硬盘出现故障时,从另一块硬盘恢复。这样当然安全,但是空间效率仅为\( \frac 12 \),显然不是一种低成本的数据保护方案,仅适用于对数据安全要求极高而对成本要求较低的场合。

而RAID5则只牺牲一块硬盘作为保护,存储其他所有硬盘的信息的异或,使用\(n\)块硬盘,那么效率为\( \frac{n – 1}{n}\)。比如对于三个硬盘组成的RAID5阵列来说,\(A\)与\(B\)存储原信息,而\(C = A \oplus B\)。这样,写入时,在\(A\)和\(B\)上写入原信息,并在\(C\)的对应位置对于变化的位进行取反;读取时直接从\(A\)和\(B\)读取信息;当\(C\)出现故障时显然不影响信息,当\(A\)或\(B\)出故障时,只需用\(C \oplus \)另一块硬盘即可得到丢失的数据。甚至,当\(AC\)或\(BC\)同时出故障时,也可以得到一半信息。

当然如果坏掉的是\(AB\)的话就跪了,最有名的例子即是ZOJ

ZOJ Will Come Back Soon

Sorry for the long downtime. On June 8th 2016, two disks in ZOJ’s RAID 5 system were corrupted. Unfortunately, serious data loss was resulted in this accident.

We will roll back ZOJ to some day in 2015, which means data in nearly a year will disappear. Registration and submission information during this period cannot be found. We grieve on the loss. Still, we will not stop trying to bring back the lost data.

Sorry again for all the inconvenience and loss resulted.

线性基

由于异或的性质,可以由\( \oplus \)来替代\( + \)定义在\( \mathbb{Z}_2 \)上的向量空间,并且可以通过这种方法解决一系列求子集元素异或值的问题。

并且,OI中所有和异或有关的题,几乎不是贪心就是利用维护线性基来解决了;或者一些模型通过列出异或方程组来解决的问题也是通过高斯消元/线性基来解决。(比如灯和开关)

我本来想好好写下这一段的,粗浅地学习了线性基相关的知识后才发现我原来就是只菜鸡。这里我留一个神犇的博客吧,写得真的很好。

https://blog.sengxian.com/algorithms/linear-basis

(等我自以为能够拿得出手的时候,我就在这里放点例题和代码吧)

FWT

快速沃尔什变换,也叫快速沃尔什-哈达玛变换(Fast Walsh–Hadamard transform),是一种快速计算沃尔什变换(也叫哈达玛变换)的算法。正如同FFT本是用于处理数字信号而被OI用作多项式乘法加速一样,FWT在OI中的应用是用来处理一类子集上的卷积问题,即$$
C_i = \sum_{j \oplus k = i} A_jB_k
$$\(\oplus\)其实可以被替换成任何一种逻辑运算符,因为这种算法是基于位运算按位分治的。
(坑)
{
在我不想写这里的时候先放一些关于FWT的Link吧:
Wikipedia:

快速沃尔什变换(需要梯子)

Bilibili(雾):

uestc郭大侠讲述fwt(虽然没证明

博客:

CSDN – Fast Walsh-Hadamard Transform (快速沃尔什变换)

一只猪的未完成的blog – FWT

}

其他

其他就很多了,异或这种思想可以巧妙地应用在很多地方。

  • 树上莫队

莫队算法是将一类统计问题通过巧妙分组来优化暴力的离线算法,将程序复杂度从\(O(n^2)\)优化至\(O(n \sqrt n)\)。提出这个算法的是伟大的莫涛莫队长。莫队十分巧妙,哪天有时间了一定要好好写一下。通常莫队是通过分块来解决询问的,即使对于树上的查询也是如此。
但是,树与序列不同,树上的路径是难以简单地用两个点单纯地移动来统计两点路径的信息的。于是,vfk提出了一种做法:WC 2013 糖果公园 park 题解

那我复述一遍这个做法吧。设\( (u, v) \)表示树上从\(u\)到\(v\)的路径,并且我们用\(lca\)表示两点的最近公共祖先,\(root\)代表树的根,那么有$$
\begin{align*}
(u, v)\ &= \ (u, lca) + (v, lca) \ – (lca, lca) \\
&= \ (u, root) \ – (lca, root) + (v, root) \ – (lca, root) + (lca, lca) \\
&= \ (u, root) \oplus (lca, root) \oplus (v, root) \oplus (lca, root) \oplus (lca, lca) \\
&= \ (u, root) \oplus (v, root) \oplus (lca, lca)
\end{align*}
$$这个结果让我们非常兴奋:只需要统计两个点到根的路径,用异或来对路径进行贡献计算,再单独计算最近公共祖先的贡献就行了!这样就可以很方便地进行树上莫队了。用个图来表示这个结果,就是这样的:

而且相比起其他表示方式,使用异或来计算贡献只需实现一种标记函数。

  • (坑)

3 comments

  • 说到奇妙的变量交换…
    [a,b] = [b,a]
    在一些脚本语言里居然可以这样写 (。・`ω´・)

    • 嗨呀,我猜这些脚本语言里包括py吧…
      我本来以为python会把[b,a]看做一个list赋值给前面,结果居然只是把两个值压入栈然后交换指针。。。
      不是很懂脚本语言们QAQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

ˆ Back To Top