异或运算与尼姆博奕

异或运算

异或运算定义：异或运算方法是一个二进制逻辑运算，设其运算符合为^，a,b为二进制数，则a,b的异或为a^b。

其运算满足如下：1^1=0,0^0=0,1^0=1,0^1=1，即 相同的为0，不相同为1。

a、b按低位到高位进行1位的二进制运算（高位没有则补0）即得a^b的值。

public class Xor {
	public static void main(String[] args) {
		System.out.println(Integer.toBinaryString(34));
		System.out.println(Integer.toBinaryString(23));
		System.out.println(Integer.toBinaryString(34^23));
	}
}

 输出：

100010
  10111
110101

 

异或运算的一些基本性质：

1、交换律：a^b=b^a    （根据定义显然可得）  

2、结合律：a^b^c=a^(b^c)   （根据定义显然可得）  

3、对于任何数a，都有a^a=0，a^0=a（根据定义显然可得）  

3、自反性：  a^b^b=a         (a^b^b=a^(b^b)=a^0=a)

 

 

 

 尼姆博奕(Nim Game)：有三堆各若干个物品（显然每堆的物品数大于0），两人轮流从某一堆取任意多的物品，每次最少取一个，不设上限，最后取光者获胜。

（一般谈论这个博弈时，都会先谈到 巴什博奕、威佐夫博弈）

设（a,b,c）为三堆石子的个数（a>=0；b>=0；c>=0），先手为 甲；后手为乙。

 

必败局势，一般称为奇异局势，显然（0,0,0）是一个奇异局势（因为谁面对这种局势，都无法做到游戏给出的条件：每次最少取一个）

讨论局势是必败还是必胜，都是相对于首先面对此局势者来说。因此站在甲的角度来讨论。甲面对（0,0,0）必输。

当甲面对（a,a,0），甲每次拿x，乙随后也跟着拿x，因此甲面对的局势始终是（a-x,a-x,0）。因此转化为甲最终都会面对（0,0,0），因此甲必输。

因为游戏是两个人交替进行。由此可得，如果局势（a,b,c）是必胜局势，那么甲就有策略，使得拿走某堆中的x个物品后，一般地设为（a-x,b,c）=(a',b,c)。此时

(a',b,c)就是一个必败的局面。反之，必败的局面可以变为必胜的局面。由此，我们寻找一个函数F，当

F(a,b,c)=1时，称（a,b,c）为必胜局面，F(a,b,c)=0时，称（a,b,c）为必败局面(奇异局势)。

 

更一般地，考虑N>=2堆物品的情况。每堆数量为（a1,a2,...,aN）   (1,2,..,N一般在数学中用下标表示)

定理：（a1,a2,...,aN）为奇异局势当且仅当a1^a2^...^aN=0    

证明：（a1,a2,...,aN）=（0,0,...,0）时显然成立。

            当（a1,a2,...,aN）不为（0,0,...,0）时，若a1^a2^...^aN=k<>0，显然k的最高位为1。

           则一定存在一个ai(1<=i<=N)，它在k的最高位的值为1。（若a1,a2,...,aN在k的最高位处都为0，那么异或运算规则，不可能得到k的最高位为1）

            因此，ai^k<ai（因为最高位变为0了）

            设ai'=ai^k，则a1^a2^...^ai'^...^aN=a1^a2^...^ai^...^aN^k (代入ai'=ai^k，并由异或的交换律得到)

                                                              =k^k=0

           因此当a1^a2^...ai^...^aN=k<>0时，存在移动ai->ai' （即移动ai-ai'>0）使得a1^a2^...ai^...^aN=0

 

           若a1^a2^...ai^...^aN=0，则不存在合法移动，使得a1^a2^...ai‘^...^aN=0。

              因为若a1^a2^...ai^...^aN=a1^a2^...ai’^...^aN=0，则两边同时异或a1,可得a2^...ai^...^aN=a2^...ai’^...^aN，

             继续两边异或a3...aN(除了共有的ai,ai')，由此可推出ai=ai'。显然这不是合法的移动。

             由以上证明得出

              1) a1^a2^...ai^...^aN=k<>0，一定存在一步特定移动使得a1^a2^...ai^...^aN=0；

              2) a1^a2^...ai^...^aN=0，不存在一步合法移动使得a1^a2^...ai‘^...^aN再次为0，

                  即当 a1^a2^...ai^...^aN=0时，任意移动一步后都会变为 a1^a2^...ai’^...^aN<>0。

             由1）、2）可得

               3)当a1^a2^...ai^...^aN=0时，下一步必然为a1^a2^...ai’^...^aN<>0，再下一步可以变为a1^a2^...ai’’^...^aN=0。

            必要性：由（a1,a2,...,aN）为奇异局势（必败局势），考虑甲先乙后。

              假设a1^a2^...ai^...^aN<>0,那么甲通过移动，可使a1^a2^...ai‘^...^aN=0。如此一直下去，每次乙都只能面对a1^a2^...ai^...^aN=0的局势。

             由于游戏的结束点必然为（0,0,...,0），因此乙最终将面对（0,0,...,0）。在乙面对（0,0,...,0）的上一步，设为（b1,...,bN）,此时b1^...^bN<>0。

            但乙最终先面对了（0,0,...,0），显然是甲胜，这与（a1,a2,...,aN）为奇异局势（必败局势，甲必败）矛盾。

            因此必有a1^a2^...ai^...^aN=0。

            充分性：由a1^a2^...^aN=0，由3）乙始终有办法让甲面对的局势始终是x1^x2^...^xN=0。因此甲最终面对的必然是（0,0,...,0)的局势，

            而（0,0,...,0)就是个奇异局势。

             证毕。