今天在逛鲁攀的QQ空间，看到一个很有意思的题目，也从另一方面告诉我们了编程中数学的重要性，很多时候数学能够给好的算法和高效的速度提供灵感，例如一个非常复杂的问题，我们却可以用几步就可以实现。

在看到这个题目之后，我就在网上查了一下这个题目并看到了异或运算的神奇，因为在说到xor异或运算的时候，大部分人都不会认为xor异或运算有什么有意思的事情，但是xor异或运算真的很神奇，不如我们首先先看个游戏，这个游戏的名字叫Nim游戏。而我们要看到的就是Nim游戏的必胜法则。（即在何种情况下无论对手如何走自己都会必胜）

有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

这个游戏貌似是很老很老的游戏，但是直到20世纪初才被一位数学家所发现规律，所以难度可见一斑，Nim游戏是博弈论中最经典的模型之一，所以现在我们当下的人去写Nim游戏会发现其实很简单，但是我们都是站在巨人的肩膀上去看问题的。从百科里我们可以知道如下内容：

Nim游戏是组合游戏(Combinatorial Games)的一种，准确来说，属于“Impartial Combinatorial Games”（以下简称ICG）。满足以下条件的游戏是ICG：

• 有两名选手。
• 两名选手交替对游戏进行移动(move)，每次一步，选手可以在（一般而言）有限的合法移动集合中任选一种进行移动。
• 对于游戏的任何一种可能的局面，合法的移动集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素。 如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动），则这名选手负。

大家可以仔细思考一下，如何才能再能自己必胜呢？

首先我们还是得回到xor运算里面来，xor运算有几个非常有趣的规律：

1. 异或自己是自己的逆运算。
2. 异或运算满足消去率。

第一个我们可以从一个非常经典的题目中看到，这个题目就是交换两个数，写一个swap函数。我们普通会写成。

但是还有一个经典答案就是用异或。

貌似更好理解，而且咱们也不必去记是加还是减，统统异或（而且计算机操作异或操作肯定比加减法要快）。

第二个满足消去率，即a^b=c^b，我们可以知道a=b，这是在and，or运算中没有的，所以也具有这个神奇的性质。

所以同Nim游戏，也有一个非常有趣的题目，这个题目就是找到2n+1数中的单独的数字，其中相同的数字有2n个，也就是有n对，比如{1，2，3，4，5，4，3，2，1}，而且这个n很大，如何找到这个n也是非常奇妙的，从这两题，我们可以知道xor异或运算符的神奇了。

对于Nim游戏，我们就是要找到对手的必败态，必败态就是当出现某种局面的时候，对手无论如何走都会输。达到必败态有两种情况，1是直接走到必败态，2是走n步比到必败态。所以我们这里就要找到Nim游戏的必败态。而我前面说了，咱都是凡人，所以直接看别人的研究成果吧。

Nim游戏是必败态当且仅当所有堆硬币的数量都异或起来结果为0，即a1^a2^…^an=0。

证明很简单，但是我不是搞数学的，所以就不贴出来充数了，可自行百科。所以在和别人玩Nim游戏或博弈的游戏的时候，我们就必须找到一种必败态，来让对手无论如何走都会输。

从Nim游戏我们可以看出来，xor运算也确实是非常神奇的，而且在很早时候就出了这个游戏，而在计算机理论之后诞生的时候，这个游戏才慢慢的被揭开，是不是从另一方面说明了2进制更符合自然语言的说法呢（原来看的某本数学书中说的，无法考究）。

当然，因为异或自己是自己的反操作的这个特性，我们也可以回过头来看找独数的这个题{1，2，3，4，5，4，3，2，1}，这个题无论我们怎么遍历都会是n2，另一种算法就是讲数字存放到hash表里，key就是数值，value就是匹配的数，1，1匹配，value就是0，则最后这个hash表里面会存放{1，0}{2，0}..{5，1}，这样我们就可以找到独数，但是浪费了空间，虽然复杂度也是O(n)（实际上可以说n+n/2加上比n大许多个空间）不过既然xor很神奇，不如我们全部异或一下。

1^2^3..^n..^3^2^1

嗯，看来我们只要异或一下，答案就出来了。看来异或运算真的很神奇，也让我感觉到，自己离计算机科学与技术这门学科，只是刚刚敲开了大门而已。

PS：最后还有一题：）

一堆石头有n個，两个人轮流取石，每次每人至少取一個，最多取上次对方取走石头的三倍。最後取光的贏得游戏。當然，第一個拿的人不可以第一次就取光所有石頭。

第一问：
当1 <= n <= 100
结果为何
第二问：
当1 <= n <= 1000
结果为何
第三问：
当1 <= n <= 1000000
结果为何