二元数博弈的美
这是一个众所周知的问题(类似的问题：number of setbits in a number and a game based on setbits，但答案不清楚)：
数字X的美是X的二进制表示中的1s数，两个玩家正在规划一个游戏。黑板上写着一个数字n。游戏内容如下： 每次玩家选择一个整数(0 <= k)，使得2^k小于n，( n-2^k )和n一样漂亮，然后n从黑板上删除，取而代之的是n-2^k。不能继续游戏的玩家(没有满足约束的k)会输掉游戏。 第一个玩家开始游戏，他们轮流。知道双方的比赛都是最佳的，必须指定胜利者。
现在我想出的解决方案是：
向右移动1位是将数字减去2^p，其中(p=将位移动到- 1)。例子: 11001 -> 25，如果我把它改为10101 --> 21 ( 25-(2^2))
玩家不能在1轮中进行2次或2次以上的右移(而不是程序上的右移)，因为它们不能加到2的幂。因此，玩家只需将设定位移动到其右侧一次就可以了。这意味着只有R轮，其中R是设置的位可以移动到一个更正确的位置的次数。因此，如果R是奇数，赢家永远是第一名，如果R是偶数，则为第二名。
Original#: 101001 41
after 1st: 11001 25 (41-16)
after 2nd: 10101 21 (25-4)
after 1st: 1101 13 (21-8)
after 2nd: 1011 11 (13-2)
after 1st: 111 7 (11-4) --> the game will end at this point我不确定这个方法的正确性，对吗？还是我错过了什么大事？
回答 3
Stack Overflow用户
发布于 2014-04-21 17:47:07
你的方法在正确的轨道上。这里要做的观察是，正如你给出的例子所示，当所有的游戏都在最不重要的位上结束时，游戏就结束了。因此，我们基本上需要数一数，我们需要多少掉期，才能使零到达最重要的位。
让我们举个例子，假设游戏开始的初始数是12，游戏状态如下：
Initial state 1100 (12) ->
A makes move 1010 (10) ->
B makes move 1001 (9) ->
A makes move 0101 (5) ->
B makes 0011 (3)
A cannot move further and B wins这可以通过编程方式(java程序v7)实现，如
public int identifyWinner (int n) {
int total = 0, numZeros = 0;
while (n != 0) {
if ((n & 0x01) == 1) {
total += numZeros;
} else {
numZeros++;
}
n >>= 1;
}
return (total & 0b1) == 1 ? 1 : 2;
}还要注意的是，即使玩家有多个选择可以进行下一个步骤，如下图所示，结果不会改变，尽管导致结果的中间变化可能会改变。
同样，让我们看一下状态流，以相同的初始值12为例。
Initial state 1100 (12) ->
A makes move 1010 (10) ->
(B here has multiple choices) B makes move 0110 (6)
A makes move 0101 (5) ->
B makes 0011 (3)
A cannot move further and B winsA不能更进一步，因为没有k (k >=0，n< 2**k k =0，1是这里唯一可行的选择)，n-2^k和n一样美丽，所以B赢了。
以41为起点也可以进行多种选择，但A将永远获胜(41(S) -> 37(A) -> 35(B) -> 19(A) -> 11(B) -> 7(A))。
希望能帮上忙！
Stack Overflow用户
发布于 2014-04-15 22:24:03
是的，每转一个1就可以向右移动，如果它的右边是0。
但是，不，移动的次数与零的数目无关。反例：
101 (1 possible move)对比
110 (2 possible moves)Stack Overflow用户
发布于 2014-06-01 01:18:06
游戏中的移动次数是每个0的左边1的总数之和。(或者相反，每个1的右边的0之和。)
(即11000有2+2+2=6次移动，而10100有1+2+2=5次移动，因为0在其右侧少1次移动)
如果游戏中的移动总数为奇数，则该游戏的获胜者将是第一位玩家，如果游戏中的移动次数为偶数，则为第二位玩家。
证明:在任何给定的移动中，玩家必须在1的右边选择一个与0对应的位。否则，如果选择一个不同的0，则1的总数会增加，如果选择1的对应点，则会减少1的总数。这样的移动将导致相应所选位的右边的1被移动到其右侧的一个位置。根据这一观察结果，每个1必须通过其右侧的每0个移动，而它所通过的每一个0要消耗一个移动。请注意，无论任何玩家在任何给定的移动中所做的选择，游戏中的移动总数仍然是固定的。
由于哈希迪普已经在每一个位( O(n)解决方案)上发布了一个correct solution循环，我将发布一个优化分治O(log(n))解决方案(在C/C++中)，这让人想起了计算汉明重量的similar algorithm。当然，使用Big来描述这里的算法有些可疑，因为位数是恒定的。
我已经验证了以下所有32位无符号整数上的代码与线性算法的结果相同。在我的机器上，这个代码按照45秒的顺序运行所有的值，而线性代码则需要6分45秒。
代码：
bool FastP1Win(unsigned n) {
unsigned t;
// lo: 0/1 count parity
// hi: move count parity
// 00 -> 00 : 00 >>1-> 00 &01-> 00 ; 00 |00-> 00 ; 00 &01-> 00 &00-> 00 *11-> 00 ^00-> 00
// 01 -> 01 : 01 >>1-> 00 &01-> 00 ; 01 |00-> 01 ; 01 &01-> 01 &00-> 00 *11-> 00 ^01-> 01
// 10 -> 11 : 10 >>1-> 01 &01-> 01 ; 10 |01-> 11 ; 10 &01-> 00 &01-> 00 *11-> 00 ^11-> 11
// 11 -> 00 : 11 >>1-> 01 &01-> 01 ; 11 |01-> 11 ; 11 &01-> 01 &01-> 01 *11-> 11 ^11-> 00
t = (n >> 1) & 0x55555555;
n = (n | t) ^ ((n & t & 0x55555555) * 0x3);
t = n << 2; // move every right 2-bit solution to line up with the every left 2-bit solution
n ^= ((n & t & 0x44444444) << 1) ^ t; // merge the right 2-bit solution into the left 2-bit solution
t = (n << 4); // move every right 4-bit solution to line up with the every left 4-bit solution
n ^= ((n & t & 0x40404040) << 1) ^ t; // merge the right 4-bit solution into the left 4-bit solution (stored in the high 2 bits of every 4 bits)
t = n << 8; // move every right 8-bit solution to line up with the every left 8-bit solution
n ^= ((n & t & 0x40004000) << 1) ^ t; // merge the right 8-bit solution into the left 8-bit solution (stored in the high 2 bits of every 8 bits)
t = n << 16; // move every right 16-bit solution to line up with the every left 16-bit solution
n ^= ((n & t) << 1) ^ t; // merge the right 16-bit solution into the left 16-bit solution (stored in the high 2 bits of every 16 bits)
return (int)n < 0; // return the parity of the move count of the overall solution (now stored in the sign bit)
}解释：
要找到游戏中的移动次数，我们可以将问题分成较小的部分，并将其组合在一起。一个人必须跟踪在任何给定的棋子中0的数目，以及在任何给定的棋子中移动的次数。
例如，如果我们将问题分成两个16位的部分，那么下面的方程表示解的组合：
totalmoves = leftmoves + rightmoves + (rightzeros * (16 - leftzeros)); // 16 - leftzeros yields the leftones count因为我们不关心总移动，只要值是偶数或奇数(奇偶)，我们只需要跟踪奇偶。
以下是加法均等的真值表：
even + even = even
even + odd = odd
odd + even = odd
odd + odd = even给定上述真值表，可以用XOR表示加法的奇偶性。
乘法奇偶的真值表：
even * even = even
even * odd = even
odd * even = even
odd * odd = odd给定上述真值表，乘法的奇偶可以用a和表示。
如果我们把问题分成几个均匀大小的部分，那么零计数和一计数的奇偶总是相等的，我们不需要单独跟踪或计算它们。
在算法的任何给定阶段，我们都需要知道零/一计数的奇偶性，以及该解中移动次数的奇偶。这需要两位。因此，让我们将解决方案中的每两位进行转换，使高比特变为移动计数奇偶，而低比特变成零/一计数奇偶。
这是通过计算完成的：
unsigned t;
t = (n >> 1) & 0x55555555;
n = (n | t) ^ ((n & t & 0x55555555) * 0x3);从这里开始，我们将每一个相邻的2位解组合成一个4位的解(使用&进行乘法，^作为加法，以及上面描述的关系)，然后每个相邻的4位解合并成8位的解，然后每一相邻的8位的解变成16位的解，最后每一个相邻的16位的解变成32位的解。
最后，只返回第二最不重要位中移动次数的奇偶。
https://stackoverflow.com/questions/23038358
复制相似问题
腾讯云开发者
