二进制

转换

二进制转十进制：数字x基数^位次幂+
例如：二进制数0101用十进制表示的数就是：1x2^0 + 0x2 ^1 + 1x2 ^2 + 0x2 ^3 = 5

十进制转二进制1.(短除法)：除2取余（从下往上取）
十进制转二进制2.：与二进制转十进制相反

七种位运算

& ：按位与（AND）(∪)a&b 把ab转化为二进制，对于每一位，如果ab这一位都是1，这该位是1，否者为0.将所有位的结果累加

• 遇0则0。如：1 & 1=1,1 & 0=0。只要有0结果就是0。

| ：按位或（OR）(∩) a | b 把ab转化为二进制，对于每一位，如果ab至少有一个是1，则该位结果是1，否者为0.将所有位的结果累加

• 遇1则1。如：1 | 1=1,1 | 0=1。只要有1结果就是1。

~：取反（NOT）(¬)，1-0 0-1

^ ：按位异或（XOR）(⊕) a ^ b 把a b转化为二进制，对于每一位，如果a b恰好有一个是1，则该位结果是1，否者为0.然后将结果转化为十进制

• 口诀：不进位加（相同为0，相异为1）。如：1 ^ 0=1,1 ^ 1=0。

" >> "：右移 a>>b 把a转化为二进制，把所有数位向右移动b个位置，相当于a / 2的b次幂

" << "：左移a<<b 把a转化为二进制，把所有数位向左移动b个位置，新多的位置补零 ，相当于a * 2的b次幂

" >>> "：无符号右移。不管符号位是0还是1，都是补0。

博弈论Nim取子问题简单理解（证明）

转: 链接.
基础知识

• 通常会将先手必败的局面称为奇异局势。
• 减去某一个数，等价于将被减数当中若干个0变成1，1变成0。
• 可以证明:任何一个偶状态在其中一个数变小后一定成为奇状态,而一个奇状态一定可以通过改变一个数变成偶状态.

先是3堆石子

关键：

• 我们有3个数，如果这三个数的每一位的1的数量和都是偶数，也就是数量和不是0就是2的话，那么这一定是一个奇异局面。

举个例子，比如[10, 8, 2]是一个奇异局面，我们把它们写成二进制。10的二进制是1010，8的二进制是1000，2的二进制是10。所以我们可以发现这三个数的二进制位加起来，第1、2、3位都出现了两个1。这个时候先手不论如何操作，后手只需要保证剩下的三个数的二进制位维持这个特性即可。这样做可以保证最后一次拿取结束之后，给先手留下[0, 0, 0]的局面。本质上来说，它的原理和两堆石子的时候是一样的，只不过转化了一种形式。

举个例子，比如我们从10当中拿走3颗石子，得到(7, 8, 2)，我们观察二进制位分别是111, 1000, 10。会发现每一位1的数量从低到高分别是[1, 2, 1, 1]。所以我们可以从1000拿取3个石子，保证留下的数量是101，也就是5。这样剩下的1的个数就是[2, 2, 2]，依然是偶数。所以先手不论如何拿，后手都可以保证一定可以让留下的数字在二进制上保持偶数，先手一定必败。在不满足这个条件的局面当中先手一定必胜，因为先手可以在第一次通过拿取掉多余的1，保证留下一个必败的局面给后手。

这也是这题的解法，即通过二进制位来判断是否先手必胜。

• 判断每个二进制位当中出现的1的次数和是否是偶数，可以通过位运算的 亦或 来完成。（在亦或操作当中，对每一个二进制位进行计算，奇数为1，偶数为0。所以我们只需要计算一下这三堆石子亦或之后的结果是否为0，就可以知道是否每一个二进制位的1的数量是否都是偶数了。）

def win_or_lose(a, b, c):
    return (a ^ b ^ c) == 0

推广 Bouton定理

定理的内容是
先手可以在非平衡的Nim博弈中取胜，
而后手可以在平衡的Nim博弈中取胜。
（这里的 平衡 就是指的是所有二进制位1的数量是偶数。）

def win_or_lose(nums):
    ret = 0
    for i in nums:
        ret ^= i
    return ret == 0

下面转至链接: link.

一. 巴什博弈（Bash Game）

只有一堆n个物品，两个人从轮流中取出（1~m）个；最后取光者胜。

考虑到 若n=m+1 那么 第一个人不论如何取都不能取胜。

进一步我们发现 若 n=k*(m+1)+r; 先取者拿走 r 个，那么后者再拿（1~m）个

n=（k-1）*（m+1）+s； 先取者再拿走s 个 最后总能造成 剩下n=m+1 的局面。

因此，此时先手有必赢策略。

相对应的，若n=k*(m+1) 那么先取者必输。
因此我们可以写出对应的程序（默认 n m都大于0）

int Bash_Game(int n,int m)
//是否先手有必赢策略
{
    if (n%(m+1)!=0) return 1;
    return 0;
}

二、尼姆博弈(Nimm Game)

题目： 当有N堆，每堆有Mi>0个物品，依旧是两个人来取该怎么判断？

int Nimm_Game(int n)//假设n个数存在数组f[]中,有必胜策略返回1
{
    int flag=0;
    for(int i=1;i<=n;i++)
    flag^=f[i];
    if(flag) return 1;
    return 0;
}

三　威佐夫博奕（Wythoff Game）

问题： 有两堆各若干个物品，
两个人轮流从某一堆取同样多的物品
--或 --同时从两堆中取同样多的物品，
规定每次至少取一个，多者不限，最后取光者得胜。

下面就没学
作　　者：Angel_Kitty
出　　处：https://www.cnblogs.com/ECJTUACM-873284962/
关于作者：阿里云ACE，目前主要研究方向是Web安全漏洞以及反序列化。如有问题或建议，请多多赐教！
版权声明：本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文链接。
特此声明：所有评论和私信都会在第一时间回复。也欢迎园子的大大们指正错误，共同进步。或者直接私信我
声援博主：如果您觉得文章对您有帮助，可以点击文章右下角【推荐】一下。您的鼓励是作者坚持原创和持续写作的最大动力！