Skip to content

Nim and the XOR Trick

Pillar: Set — "Bits Are Sets (Ch1 L3). Each bit position is an INDEPENDENT game. XOR = symmetric difference of these bit-sets. The XOR of pile sizes encodes the 'imbalance' in each independent game."

The Setup

Two players sit across a table with \(n\) piles of stones. They alternate turns. On your turn, pick any single pile and remove any positive number of stones from it — one stone, half the pile, the entire pile. The player who takes the last stone wins. This is Nim, the founding game of combinatorial game theory.

Three piles: \([3, 5, 6]\). You go first. Should you feel confident or worried?

The brute-force approach — build the entire game tree and label each position as winning or losing — takes exponential time. But there's a one-line test that instantly classifies any Nim position. It uses XOR, and the reason it works comes down to thinking about bits as independent sets.

The Nim Theorem

A Nim position with piles \(a_1, a_2, \ldots, a_n\) is a losing position for the player to move if and only if:

\[a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0\]

where \(\oplus\) is bitwise XOR. If the XOR is nonzero, the current player can always force a win. If it's zero, every move you make hands your opponent a winning position.

This result is called the Sprague-Grundy theorem for Nim (the full Sprague-Grundy theory generalizes to arbitrary impartial games — that's Ch8 L2). For now, the question is: why does XOR, of all operations, determine who wins?

Why XOR Works — Bit Independence

Write each pile size in binary. Stack them vertically, one row per pile, one column per bit position. Now look at a single column — say bit \(2\) (the fours place). Some piles have a \(1\) there, some have a \(0\). That column is a mini-game all by itself: the count of \(1\)s in that column is either even or odd.

XOR, column by column, counts the parity of \(1\)s. If the XOR of all pile sizes is \(0\), every column has an even number of \(1\)s — every bit-position game is balanced. If the XOR is nonzero, at least one column is imbalanced (odd count of \(1\)s).

Recall from Ch1 L3: XOR is the symmetric difference of bit-sets. When you XOR two numbers, the result has a \(1\) in each position where exactly one of the inputs has a \(1\). XOR of all pile sizes collects the "leftover" \(1\)s — the imbalance — across all piles.

The connection is this: each bit position behaves as an independent single-bit game, and XOR tracks whether each independent game is balanced or imbalanced. A position is losing for the mover exactly when all independent games are simultaneously balanced.

If XOR = 0, you lose

Every bit column has an even count of \(1\)s. Any move you make changes exactly one pile, which flips some bits in that pile's binary representation. This disrupts at least one column — it goes from even to odd. After your move, the XOR is nonzero. You've handed your opponent a winning position.

If XOR \(\neq\) 0, you win

You can always find a move that zeros out the XOR. The trick: look at the highest bit where the XOR is \(1\). At least one pile has a \(1\) in that position (otherwise the column would sum to \(0\) there). Reducing that pile appropriately can zero out the XOR. After your move, the XOR is \(0\) — you've handed your opponent a losing position.

The game is a seesaw: nonzero XOR \(\to\) zero XOR \(\to\) nonzero \(\to\) zero \(\to \cdots\) The player who receives XOR \(= 0\) eventually faces all piles empty (which also has XOR \(= 0\)) with no move to make. That player loses.

The Strategy

When the XOR is nonzero, here's how to find the winning move.

Let \(T = a_1 \oplus a_2 \oplus \cdots \oplus a_n\) (the total XOR, which is nonzero). You need to find a pile \(a_i\) and reduce it to some value \(a_i'\) such that after the change, the new total XOR is \(0\).

The new XOR after changing pile \(i\) from \(a_i\) to \(a_i'\) is:

\[T \oplus a_i \oplus a_i'\]

(XOR out the old value, XOR in the new value.) Setting this to \(0\) gives \(a_i' = T \oplus a_i = a_i \oplus T\).

For this to be a valid move, you need \(a_i' < a_i\) (you must remove at least one stone). So the condition is:

\[a_i \oplus T < a_i\]

When does this hold? Look at the highest set bit of \(T\). Any pile \(a_i\) that has a \(1\) in that bit position satisfies \(a_i \oplus T < a_i\), because XOR flips that high bit from \(1\) to \(0\), which decreases the value (even if lower bits increase, the net effect is a decrease since the highest differing bit went down).

The move: find any \(a_i\) where \(a_i \oplus T < a_i\). Remove \(a_i - (a_i \oplus T)\) stones from pile \(i\).

Worked Example 1: Losing Position

Piles \(= [3, 5, 6]\). Write each in binary:

Pile Bit 2 (4s) Bit 1 (2s) Bit 0 (1s)
\(3 = 011\) \(0\) \(1\) \(1\)
\(5 = 101\) \(1\) \(0\) \(1\)
\(6 = 110\) \(1\) \(1\) \(0\)
Column sum 2 2 2
Parity even even even

\(3 \oplus 5 \oplus 6 = 0\). Every column is balanced. This is a losing position for the player to move — no matter what you do, you break the balance and hand your opponent a win.

Verify: \(3 \oplus 5 = 6\), and \(6 \oplus 6 = 0\). Confirmed.

Worked Example 2: Winning Position

Piles \(= [3, 4, 5]\). Binary:

Pile Bit 2 (4s) Bit 1 (2s) Bit 0 (1s)
\(3 = 011\) \(0\) \(1\) \(1\)
\(4 = 100\) \(1\) \(0\) \(0\)
\(5 = 101\) \(1\) \(0\) \(1\)
Column sum 2 1 2
Parity even odd even

\(T = 3 \oplus 4 \oplus 5 = 2\) (binary \(010\)). Nonzero — the player to move wins.

The highest set bit of \(T\) is bit \(1\). Which piles have a \(1\) in bit \(1\)? Only pile \(3 = 011\).

Winning move: reduce pile \(3\) to \(3 \oplus 2 = 1\). Remove \(3 - 1 = 2\) stones from the first pile.

After the move, piles are \([1, 4, 5]\). Check: \(1 \oplus 4 \oplus 5 = 0\). You've zeroed the XOR. Your opponent is now in a losing position.

Misere Nim

In Misere Nim, the player who takes the LAST stone loses (opposite of normal play). You'd think the analysis changes dramatically. It barely changes at all.

The strategy is identical to normal Nim with one exception at the endgame. The difference kicks in only when every pile has at most \(1\) stone.

Misere Nim rule: a position is losing for the player to move if and only if:

  • The XOR of all pile sizes is \(0\) AND at least one pile has size \(\geq 2\), OR
  • The XOR of all pile sizes is nonzero AND every pile has size \(\leq 1\).

Equivalently: play the normal Nim strategy, but when you're about to enter the endgame (all piles are \(0\) or \(1\)), leave an odd number of \(1\)-piles instead of an even number. In normal Nim you'd leave an even number (XOR \(= 0\)); in Misere you flip it.

Why? In normal Nim, XOR \(= 0\) with all piles \(\leq 1\) means an even number of \(1\)-piles. The mover takes one, leaving odd, and eventually the opponent takes the last stone — the mover loses. In Misere, you WANT the opponent to take the last stone, so you want to leave them with \(1\) pile of size \(1\). The parity flips.

The Code

#include <bits/stdc++.h>
using namespace std;

string nimWinner(vector<int>& piles) {
    int totalXOR = 0;
    for (int pileSize : piles) totalXOR ^= pileSize;
    return totalXOR != 0 ? "First" : "Second";
}

pair<int,int> nimWinningMove(vector<int>& piles) {
    int totalXOR = 0;
    for (int pileSize : piles) totalXOR ^= pileSize;
    if (totalXOR == 0) return {-1, -1};
    for (int i = 0; i < (int)piles.size(); i++) {
        int reducedSize = piles[i] ^ totalXOR;
        if (reducedSize < piles[i]) {
            int stonesToRemove = piles[i] - reducedSize;
            return {i, stonesToRemove};
        }
    }
    return {-1, -1};
}

string misereNimWinner(vector<int>& piles) {
    int totalXOR = 0;
    bool allSingletons = true;
    for (int pileSize : piles) {
        totalXOR ^= pileSize;
        if (pileSize > 1) allSingletons = false;
    }
    if (allSingletons) {
        int numNonEmpty = 0;
        for (int pileSize : piles) numNonEmpty += (pileSize > 0);
        return numNonEmpty % 2 == 0 ? "First" : "Second";
    }
    return totalXOR != 0 ? "First" : "Second";
}

int main() {
    int numPiles;
    cin >> numPiles;
    vector<int> piles(numPiles);
    for (int i = 0; i < numPiles; i++) cin >> piles[i];
    cout << nimWinner(piles) << "\n";
    auto [pileIndex, stonesToRemove] = nimWinningMove(piles);
    if (pileIndex != -1)
        cout << "Remove " << stonesToRemove << " from pile " << pileIndex << "\n";
    return 0;
}

Complexity

\(O(n)\) time to compute the XOR and find the winning move, \(O(1)\) space (beyond storing the piles).

Common Mistakes

  • Confusing XOR = 0 with "first player wins." XOR = 0 means the current player LOSES. Zero XOR = balanced = no winning move. The most common sign error in game theory problems.

  • Forgetting Misere is almost the same as normal. Students often try to rework the entire theory for Misere Nim. The only difference is the endgame parity — when all piles are \(\leq 1\), you flip the winning condition. Everything before that is standard Nim strategy.

  • Not checking \(a_i \oplus T < a_i\). When finding the winning move, you must pick a pile where XOR with the total is strictly smaller. Not every pile qualifies — only those with a \(1\) in the highest set bit of \(T\). Picking the wrong pile gives an invalid move (you'd need to add stones, which isn't allowed).

Quick Recap

  • A Nim position is losing for the mover iff the XOR of all pile sizes is \(0\).
  • XOR works because each bit position is an independent game. XOR tracks parity (balance) across all independent bit-games simultaneously.
  • Winning move: find a pile \(a_i\) where \(a_i \oplus T < a_i\) and reduce it to \(a_i \oplus T\).
  • Misere Nim differs only in the endgame: when all piles are \(\leq 1\), the winning parity flips.
  • The bit-independence idea extends far beyond Nim — it's the foundation of the Sprague-Grundy theorem (Ch8 L2).

Problems

Problem Link Difficulty Focus
CSES — Nim Game I cses.fi/problemset/task/1730 Easy Direct Nim; XOR all pile sizes, check nonzero
LC 292 — Nim Game leetcode.com/problems/nim-game Easy Single-pile Nim with max 3 stones per turn; not standard Nim but same flavor (losing iff divisible by 4)
LC 1025 — Divisor Game leetcode.com/problems/divisor-game Easy Game theory via parity argument; first player wins iff \(n\) is even
CSES — Nim Game II cses.fi/problemset/task/1098 Medium Misere Nim; same XOR trick with endgame parity flip
CF 850C — Arpa and a game with Mojtaba codeforces.com/problemset/problem/850/C Hard Nim variant; requires Sprague-Grundy values per pile, but XOR combination is the core