异或运算是一种很神奇用途很广的运算. 从性质上, 异或运算作为二元运算, 关于所有非负整数构成一个 Abel 群, 0 作为幺元, 每个元的逆元都是自身(等价于说 $char(N ^ \star,xor)=2$)。

异或的定义和简单性质

异或, 英文: exclusive OR, 缩写 xor, 习惯记作 $\wedge$。这个运算 $1\wedge 1=0\wedge 0=0,1\wedge 0=0\wedge 1=1$。 对任意是两个非负整数 $a,b$ 将其写成二进制, 然后各位分别进行异或操作即可. 容易根据上面定义说明之前提到的性质. 下面再介绍一个重要但不是很明显的性质:

引理: 若 $k=a_1\wedge ⋯\wedge a_n≠0$ 则必然存在 $i$, 使得 $a_i \wedge k<a_i$。
证明: 因为 $k \neq 0$, 所以必然记 $k$ 得最高位是第 $t$ 位, 则必然存在 $i$, 使得 $a_i$ 的第 $t$ 为不为 0(否则 $k$ 的第 $t$ 位的 1 咋来的). 那么此时 $a_i \wedge k$ 的第 $t$ 为 0, 前面的位不变, 从而小于 $a_i$。

异或的简单应用

简单的直接贴代码吧, 不废话.

用异或来改变两个数

1
2
3
4
5
swap(UI & a, UI & b){
	a = a^b;
	b = a^b;
	a = a^b
} // UI 表示 unsigned int, 写的很骚气.

异或找出唯一出现奇数次的数

把这一堆数全体直接异或即可.

这个方法可以推广到找出两个只出现奇数次的, 其它出现偶数次的两个数, 方法就是先异或之后的值按照最高位进行标记然后分成两组, 再来一遍.

Nim 取石子问题

在 2002 年国家 IO 集训队中张一飞写了<<由感性认识到理性认识——透析一类搏弈游戏的解答过程>>中明确的表面了这个取 Nim 石子游戏用异或可以完美的解决.

我把他结果简单表达如下, 并在做一点小小的改变之后得到类似的结果

游戏规则 1 : 甲乙两人面对若干堆石子，其中每一堆石子的数目任意给定, 两人轮流取走一些石子, 每次至少取一枚石子, 每次只能从某一堆中取, 可以取完, 谁无法取子, 谁就是输家(规则 2 正好相反).

在规则 1 中张一飞一步一步由浅入深, 从具体例子过度到理性的判断, 最终给出若所有石子数异或结果为 0, 则后手胜, 反之先手胜.

首先对于此类取石子博弈问题: 必败准则

必胜局面必然存在一步转化成为一个必负局面;
必负局面必然任意一步转化都会成为必胜局面.

而对于异或也有类似的结果: $k=a_1\wedge \cdots \wedge a_n$

若 $k \neq 0$ 由引理知道, 可以减小某个 $a_i$ 使得之后的异或和为 0.
若 $k=0$, 则任意改变都会导致异或和不为 0.

这样操作下去堆数一定在一直减小.
对于规则 1: 由于空局面是负局面容易看出, 若异或和为 0 则先手负, 反之先手胜.
而对于规则 2, 由于空局面是胜局面,而 1 局面是负局面, 这就有些尴尬了. 并且局面并不能像规则 1 一样进行局面分解, 因此十分麻烦.

规则 2 的感性判断

  1. 去掉任意多的 0 和偶数个 1 并不会影响结果(是对的, 但是要分情况推敲一下)
  2. 无法根据子局面的胜负来判断总局面的胜负.
  3. 负局面的价值远远高于胜局面, $(1),(n,n>1),(1,2n,2n+1)$, 奇数个 1, 偶数个 2 是负局面(用数学归纳法容易证明)
  4. 从小的开始枚举, 为被负局面包含的极小局面是胜局面, 被所有胜局面包围的是负局面, 这样可以一直进行下去直到得到我们的结果.
  5. 前戏终于结束了, 要来真的了 0.0(好害怕)

规则 2 的理性判断

经过总时长 8 个小时左右的零碎时间思考, 最终给出下面结果:

  1. 首先我们先剔除所有 0 和偶数个 1 得到新的局面至多有一个 1. 如果为空, 则为胜局面.
  2. 对于堆数 $n=1$ 的情形, $a1=1$ 为负局面, 其它为胜局面.
    对于堆数 $n>1$ 是若 $a_1\wedge ⋯\wedge a_n=0$ 为负局面, 其它为胜局面.
    证明: 首先证明结论对 $n=2$ 是成立, 即 $a_1=a_2$(不可能同时为 1)时是负局面, 因为 $a_1=a_2=2$是负局面, 若 $a_1=a_2<k$ 是负局面, $a_1=a_2 = k$, 则下一步必然是 $(a1,a2)=(m<k,k)$ 为胜局面(若 $m=0,1$ 时显然, 否则下一步 $(a_1=a2)=(m,m)$ 为负局面). 因此结论对 $n=2$ 成立. 现在若结论对于 $n<k$ 成立, 那么由引理若 $a_1\wedge ⋯\wedge a_n=0$ 则下一步必然导致 $a′_1 \wedge ⋯ \wedge a′_n \neq 0$. 若其中某个 $a′_i=0$, 那么由归纳法必然导致结论成立. 那么后手就可以取走一些石子导致 $a′′_1 \wedge ⋯\wedge a′′_n=0$. 另外一出现多于 2 个 1 直接剔除(不会改变异或和的值). 这样下去堆数必然减少, 由归纳法可知结论成立.

例如1∧3∧5∧7=0 从而可以判断这是一个负局面.(可以简单试试这个策略玩一玩这个游戏)

感谢张一飞的论文, 感谢 FDU 高数杭老师提供题目, 感谢蔡学弟把问题分享给我。感谢网友批评指正。