数字中的集位数和基于setbit的游戏

Question

我试过这个关于位操作的问题是通过这个：

数字的美是指该数中的集合位数。A和B开始玩一个棋盘上写着N号的游戏，轮到移动的玩家走到棋盘上，写一个新的N-K，其中k<=N和K的美是1。同样重要的是，new的美必须与N的美相等。最后一位玩家要成功完成他的移动，就赢得了这场比赛。

他们都玩得很好。

我不是在这里找代码，我想知道如何处理这个问题？

Answer 1

这是典型的博弈论问题。球员发挥最佳意味着，任何球员都会做出这样的举动，从而使其获胜的机会最大化(考虑到当第2名球员有机会的时候，他也会愿意这样做)。

在这种情况下，让我们看看允许的移动：

根据要求，一个数字的美应该保持不变，而k应该有美丽的1，即只有1位集(用于ex )。00000100)

为了进一步说明，让我们假设我们只有8位数。

如果您仔细地看到，为了保持N的美丽不变，k中设置的位位于N有0的索引(其中之一)，而1位于它的左边。我想举一个例子：

让我们说N是01010001。现在k可以是00100000，00001000。如果你看到N-k，它的美丽依然不变。操作结束后，您将注意到1向右移动，因此0向左移动。例如，当N=01010001和k=00100000 (N-k) = 00110001。

此外，游戏的结束位置将是这样的，所有的0's都在左边，所有的1's都在右边(00000111)。您可以在给定数字N的情况下计算可能的移动次数。如果这是奇怪的，那么球员的首发获胜，否则他就输了。

现在，计算这些移动的数量是简单的枚举问题。