# Finding winner of flipping game

Alice and Bob play a game with N non-negative integers.

Players take successive turns, and in each turn, they are allowed to flip active bits from any of the integers in the list.

That is, they pick one (and only one) non-zero integer in the list and flip its as many active bits as desired.

By flipping an active bit of an integer, we mean turning a bit from 1 to 0 in the binary representation of that integer.

As this flipping continues, eventually all numbers in the list become zero.

So the player who ends up turning the last non-zero integer to 0 in the list is the winner (or the player who cannot play on his turn loses).

Given a possible initial configuration, we need to tell if Alice can or cannot beat Bob. Assume that both of them will play optimally (i.e. they do their best in each turn). Also assume that Alice gets the first turn.

Example : Let N=2 and list be [2,9] then in this Alice will win.But say we have N=3 and list be [8,10,290] then in this Bob will move whatever move Alice takes.

So given list of N numbers we need to find winner of this game.

• It is misleading to call it 'flipping', because that usually means changing a bit from $1$ to $0$ or from $0$ to $1$. Perhaps 'clearing a non-zero bit' would be better than 'flipping an active bit'. Also, you forgot to stipulate that at least one non-zero bit has to be cleared (otherwise the game will never end). – TonyK Sep 13 '14 at 14:00

This is Nim with each heap having the number of stones as there are $1$ bits in the number. The usual Nim strategy applies-you win by leaving a position where the XOR of the binary expansions of the number of stones in each pile is zero. So $(2,9)$ in your game corresponds to $(1,2)$ in Nim and Alice wins by flipping one bit in $9$. $(8,10,290)$ corresponds to $(1,2,3)$ and is a win for Bob.
• user3840069: @TonyK is correct-that is how I went from $(8,10,290)$ to $(1,2,3)$, then $01 \text{ XOR } 10 \text { XOR } 11=0$ – Ross Millikan Sep 13 '14 at 14:12