Nim, Sprague-Grundy, and XOR Invariants

May 2026 · 26 min read

XOR is not just a bit trick; it is the invariant behind impartial combinatorial games. Nim is the gateway: if the XOR of heap sizes is zero, the position is losing with perfect play. If it is non-zero, the current player can move to a zero-XOR state.

Nim

There are piles of stones. A move chooses one pile and removes at least one stone. The player who takes the last stone wins.

int nim_sum = 0;
for (int pile : piles) nim_sum ^= pile;

if (nim_sum == 0) losing_position();
else winning_position();

Finding the Winning Move

If x = xor(all piles) is non-zero, choose a pile where the highest set bit of x is also set. Replace pile p with p ^ x, which is smaller.

int x = 0;
for (int p : piles) x ^= p;
for (int i = 0; i < n; ++i) {
    int target = piles[i] ^ x;
    if (target < piles[i]) {
        // reduce piles[i] to target
        break;
    }
}

Grundy Numbers

Every impartial finite game state has a Grundy number. A terminal state has Grundy 0. Other states take the mex of reachable Grundy values.

grundy[state] = mex({ grundy[next] for each legal move state -> next })

The XOR of Grundy numbers across independent subgames determines the winner, just like Nim heaps.

Computing mex

int mex(vector<int> vals) {
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int g = 0;
    for (int x : vals) {
        if (x == g) ++g;
        else if (x > g) break;
    }
    return g;
}

Game Patterns

• Independent components combine by XOR of Grundy values.
• A zero XOR state is losing if both players play optimally.
• Many subtraction games have periodic Grundy sequences.
• Graph games may reduce to Grundy values on DAG states.

Practice Problems

• CSES - Nim Game I nim-sum direct XOR invariant.
• CSES - Nim Game II mod piles variant requiring game interpretation.
• LeetCode 1510 - Stone Game IV game DP losing/winning states.
• Codeforces 1383B - GameGame highest bit XOR game reasoning by MSB counts.