异或运算及其在Nim游戏中的应用

异或运算是一种很神奇用途很广的运算. 从性质上, 异或运算作为二元运算, 关于所有非负整数构成一个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=01∧3∧5∧7=0 从而可以判断这是一个负局面.(可以简单试试这个策略玩一玩这个游戏)

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

欧尼酱,人家想喝可乐!