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

发表于 |

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

异或的定义和简单性质

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

引理: 若$k = a_1 \wedge \cdots \wedge a_n \neq 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$的情形, $a_1 = 1$为负局面, 其它为胜局面.
    对于堆数$n>1$是若$a_1 \wedge \cdots \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$, 则下一步必然是$(a_1, a_2) = (m<k, k)$ 为胜局面(若$m=0, 1$时显然, 否则下一步$(a_1 = a_2) = (m,m)$为负局面). 因此结论对$n=2$成立. 现在若结论对于$n<k$成立, 那么由引理若$a_1 \wedge \cdots \wedge a_n = 0$, 则下一步必然导致$a_1’ \wedge \cdots \wedge a_n’ \neq 0$. 若其中某个$a_i’ = 0$, 那么由归纳法必然导致结论成立. 那么后手就可以取走一些石子导致$a_1’’ \wedge \cdots \wedge a_n’’ = 0$. 另外一出现多于$2$个1直接剔除(不会改变异或和的值). 这样下去堆数必然减少, 由归纳法可知结论成立.

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

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