XOR Basis and GF(2)

Pillar: Set — "XOR is addition in GF(2). A set of numbers forms a vector SPACE under XOR. The basis is the minimal spanning SET." Pillar: Chain — "Gaussian elimination cascades reductions: fix the highest pivot bit, reduce all others."

---

The Setup

You have five numbers: \(6, 3, 5, 7, 2\). Someone asks: what's the maximum value you can get by XORing some non-empty subset of them?

Brute force: try all \(2^5 - 1 = 31\) subsets. That's fine for \(n = 5\). Now make it \(n = 10^5\) numbers, each up to \(10^{18}\). Brute force is out of the question.

The answer hinges on a structure you already know from Ch1 L3. XOR is symmetric difference on sets of bit positions. But there's a deeper fact: if you treat each number as a vector of bits, XOR is vector addition in a specific algebraic field. That field is \(\text{GF}(2)\), and Gaussian elimination works in it. The result is a compact basis -- at most 60 vectors for 60-bit numbers -- that captures every XOR you could ever produce from the original set.

---

XOR as Addition over GF(2)

The Field

\(\text{GF}(2)\) is the simplest possible field. It has two elements: \(0\) and \(1\). The operations:

\(+\) (addition)	\(0\)	\(1\)
\(0\)	\(0\)	\(1\)
\(1\)	\(1\)	\(0\)

\(\times\) (multiplication)	\(0\)	\(1\)
\(0\)	\(0\)	\(0\)
\(1\)	\(0\)	\(1\)

Addition is XOR. Multiplication is AND. Every nonzero element (\(1\)) has an inverse (\(1\) itself). That's a field.

Numbers as Vectors

A 60-bit integer is a vector in \(\text{GF}(2)^{60}\). The number \(6 = 110_2\) is the vector \((0, 1, 1, 0, 0, \ldots)\) -- bit 1 and bit 2 are \(1\), everything else is \(0\).

XORing two numbers is adding their vectors coordinate-by-coordinate in \(\text{GF}(2)\). Each bit is independent: \(1 \oplus 1 = 0\), \(1 \oplus 0 = 1\), exactly mod-2 addition.

This means the set of all XOR combinations of your numbers forms a vector space over \(\text{GF}(2)\). Everything from linear algebra applies: linear independence, span, basis, dimension.

---

Linear Independence over GF(2)

A set of numbers \(\{v_1, v_2, \ldots, v_k\}\) is linearly independent over GF(2) if no element can be written as the XOR of some subset of the others. Equivalently, \(c_1 v_1 \oplus c_2 v_2 \oplus \cdots \oplus c_k v_k = 0\) (where each \(c_i \in \{0, 1\}\)) implies all \(c_i = 0\).

Check: are \(6, 3, 5\) independent? Is there a non-empty subset that XORs to zero?

• \(6 \oplus 3 = 5\). So \(6 \oplus 3 \oplus 5 = 0\).

They are dependent. You can express \(5\) as \(6 \oplus 3\). The set \(\{6, 3, 5\}\) has rank 2, not 3.

A basis for the XOR space is a maximal linearly independent subset. If the basis has \(k\) elements, the space contains exactly \(2^k\) distinct values (including zero). Every XOR-reachable value can be expressed uniquely as a XOR of some subset of the basis.

---

XOR Basis via Gaussian Elimination

The Algorithm

Process each number one at a time. Maintain an array basis[0..59] where basis[b] is the basis vector whose highest set bit is bit \(b\) (or \(0\) if no basis vector occupies that pivot).

For each incoming number value:

1. Scan bits from high to low. Find the highest set bit \(b\) of value.
2. If basis[b] is empty, store value there. Done -- this number was independent.
3. If basis[b] is occupied, XOR value with basis[b]. This clears bit \(b\) from value. Go back to step 1 with the reduced value.
4. If value becomes \(0\), the original number was a linear combination of existing basis elements. It's redundant -- don't insert it.

This is Gaussian elimination, adapted for \(\text{GF}(2)\). Instead of subtracting a multiple of the pivot row, you XOR with the pivot (since in \(\text{GF}(2)\), subtraction IS XOR).

Why It Works

Each basis vector "owns" a unique highest bit. When you reduce a new number against the basis, you're eliminating its bits one at a time, highest first. If the number survives (stays nonzero), it has a highest bit that no current basis vector owns -- so it's genuinely independent and extends the basis.

The cascade of reductions is the Chain pillar at work. Each XOR clears one bit and drops the number to a lower pivot. The chain terminates when either the number reaches zero (dependent) or finds an unoccupied pivot (independent).

---

Trace: Building a Basis from \(\{6, 3, 5, 7, 2\}\)

Write each number in binary (3 bits shown):

Number	Binary	Highest Bit
\(6\)	\(110\)	\(2\)
\(3\)	\(011\)	\(1\)
\(5\)	\(101\)	\(2\)
\(7\)	\(111\)	\(2\)
\(2\)	\(010\)	\(1\)

Insert \(6\) (\(110\)). Highest bit is \(2\). basis[2] is empty. Store \(6\). Basis: \(\{6\}\).

Insert \(3\) (\(011\)). Highest bit is \(1\). basis[1] is empty. Store \(3\). Basis: \(\{6, 3\}\).

Insert \(5\) (\(101\)). Highest bit is \(2\). basis[2] = 6. Reduce: \(5 \oplus 6 = 3\). Now highest bit is \(1\). basis[1] = 3. Reduce: \(3 \oplus 3 = 0\). Value is zero -- \(5\) is dependent. Skip it.

Insert \(7\) (\(111\)). Highest bit is \(2\). basis[2] = 6. Reduce: \(7 \oplus 6 = 1\). Now highest bit is \(0\). basis[0] is empty. Store \(1\). Basis: \(\{6, 3, 1\}\).

Insert \(2\) (\(010\)). Highest bit is \(1\). basis[1] = 3. Reduce: \(2 \oplus 3 = 1\). Now highest bit is \(0\). basis[0] = 1. Reduce: \(1 \oplus 1 = 0\). Value is zero -- \(2\) is dependent. Skip it.

Final basis:

Pivot Bit	Basis Vector	Binary
\(2\)	\(6\)	\(110\)
\(1\)	\(3\)	\(011\)
\(0\)	\(1\)	\(001\)

Basis size \(= 3\), so the XOR space has \(2^3 = 8\) distinct values: \(\{0, 1, 2, 3, 4, 5, 6, 7\}\). You can reach any 3-bit number by XORing subsets of \(\{6, 3, 1\}\).

---

Applications

Maximum XOR Subset

Greedily build the answer from the highest basis bit downward. Start with result = 0. For each basis vector from high to low, XOR it in if doing so increases result.

The greedy choice is correct because each basis vector controls a unique highest bit. Taking basis[b] sets bit \(b\) in the result. No later basis vector can affect bit \(b\) (they all have lower pivots). So the decision at each bit is locally optimal and globally irreversible.

For our basis \(\{6, 3, 1\}\):

• result = 0. Try \(6\): \(0 \oplus 6 = 6 > 0\). Take it. result = 6 (\(110\)).
• Try \(3\): \(6 \oplus 3 = 5 < 6\). Skip it. (Bit 2 would be cleared, losing more than bit 1 gains -- but the cleaner check is just result = max(result, result ^ basis[bit]) for each pivot.)
• Try \(1\): \(6 \oplus 1 = 7 > 6\). Take it. result = 7 (\(111\)).

Maximum XOR \(= 7\).

Count Distinct XOR Values

If the basis has \(k\) vectors, the number of distinct values you can XOR from the original set is exactly \(2^k\). Each of the \(k\) basis vectors is independently included or excluded. This includes the empty subset (which gives \(0\)).

Check if a Target XOR is Achievable

Reduce the target through the basis, just like insertion. If it reaches \(0\), the target is in the span. If it stays nonzero but hits an empty pivot, the target is not achievable.

---

Gaussian Elimination for Reals

The same algorithm works over the real numbers for solving linear systems. The idea is identical: for each column, find a pivot row, then eliminate that variable from all other rows. The differences from GF(2):

• Instead of XOR, you subtract a scaled multiple of the pivot row.
• You need partial pivoting (pick the row with the largest absolute value) to avoid numerical instability.
• You must handle three outcomes: unique solution (full rank), no solution (inconsistent), infinitely many solutions (underdetermined).

The CSES problem "System of Linear Equations" asks you to implement exactly this.

The Procedure

Given an \(n \times n\) system \(Ax = b\), form the augmented matrix \([A \mid b]\) of size \(n \times (n+1)\).

For each column \(c\) from left to right:

1. Find the row with the largest absolute value in column \(c\) (among rows not yet used as pivots). This is partial pivoting.
2. Swap that row into the current pivot position.
3. Divide the entire pivot row by the pivot element, making the pivot \(1\).
4. For every other row, subtract a multiple of the pivot row to zero out column \(c\).

After processing all columns, the matrix is in reduced row echelon form. If any row reads \(0 = b_i\) with \(b_i \neq 0\), the system is inconsistent. If there are fewer pivots than variables, the system has infinitely many solutions. Otherwise, read the unique solution directly from the last column.

---

Code

XOR Basis: Builder, Max Query, Reachability Query

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

struct XORBasis {
    vector<long long> basis;
    int basisSize = 0;
    static const int MAX_BITS = 60;

    XORBasis() : basis(MAX_BITS, 0) {}

    bool insert(long long value) {
        for (int bit = MAX_BITS - 1; bit >= 0; bit--) {
            if (!((value >> bit) & 1)) continue;
            if (!basis[bit]) {
                basis[bit] = value;
                basisSize++;
                return true;
            }
            value ^= basis[bit];
        }
        return false;
    }

    long long queryMax() {
        long long result = 0;
        for (int bit = MAX_BITS - 1; bit >= 0; bit--) {
            result = max(result, result ^ basis[bit]);
        }
        return result;
    }

    bool canRepresent(long long target) {
        for (int bit = MAX_BITS - 1; bit >= 0; bit--) {
            if ((target >> bit) & 1) target ^= basis[bit];
        }
        return target == 0;
    }
};

int main() {
    int numElements;
    cin >> numElements;
    XORBasis xorBasis;
    for (int i = 0; i < numElements; i++) {
        long long value;
        cin >> value;
        xorBasis.insert(value);
    }
    cout << xorBasis.queryMax() << "\n";
    cout << (1LL << xorBasis.basisSize) << "\n";
    return 0;
}

Real Gaussian Elimination (CSES System of Linear Equations)

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

int main() {
    int numVariables;
    cin >> numVariables;

    vector<vector<double>> augmented(numVariables, vector<double>(numVariables + 1));
    for (int row = 0; row < numVariables; row++)
        for (int col = 0; col <= numVariables; col++)
            cin >> augmented[row][col];

    const double EPSILON = 1e-9;
    int pivotRow = 0;
    vector<int> pivotColumn(numVariables, -1);

    for (int col = 0; col < numVariables && pivotRow < numVariables; col++) {
        int bestRow = pivotRow;
        for (int row = pivotRow + 1; row < numVariables; row++) {
            if (abs(augmented[row][col]) > abs(augmented[bestRow][col]))
                bestRow = row;
        }
        if (abs(augmented[bestRow][col]) < EPSILON) continue;

        swap(augmented[pivotRow], augmented[bestRow]);
        double pivotValue = augmented[pivotRow][col];
        for (int j = col; j <= numVariables; j++)
            augmented[pivotRow][j] /= pivotValue;

        for (int row = 0; row < numVariables; row++) {
            if (row == pivotRow) continue;
            double factor = augmented[row][col];
            if (abs(factor) < EPSILON) continue;
            for (int j = col; j <= numVariables; j++)
                augmented[row][j] -= factor * augmented[pivotRow][j];
        }

        pivotColumn[pivotRow] = col;
        pivotRow++;
    }

    for (int row = pivotRow; row < numVariables; row++) {
        if (abs(augmented[row][numVariables]) > EPSILON) {
            cout << "INCONSISTENT\n";
            return 0;
        }
    }

    if (pivotRow < numVariables) {
        cout << "UNDERDETERMINED\n";
        return 0;
    }

    vector<double> solution(numVariables);
    for (int row = 0; row < numVariables; row++)
        solution[pivotColumn[row]] = augmented[row][numVariables];

    cout << fixed << setprecision(6);
    for (int i = 0; i < numVariables; i++)
        cout << solution[i] << "\n";

    return 0;
}

Complexity:

• XOR basis insertion: \(O(B)\) per element, \(O(NB)\) total, where \(B\) is the number of bits (typically \(60\)). Space: \(O(B)\).
• Real Gaussian elimination: \(O(n^3)\) time, \(O(n^2)\) space.

---

Common Mistakes

• Using int instead of long long for the basis. If values go up to \(10^{18}\), you need 60-bit vectors. 1 << bit overflows for bit >= 31 -- always use 1LL << bit or store the basis as long long.
• Forgetting that the empty XOR is zero. The \(2^k\) reachable values include \(0\) (the XOR of the empty subset). If the problem asks for non-empty subsets only, you may need to subtract one or handle zero separately.
• Wrong greedy direction for max XOR. You must iterate from the highest pivot bit downward. Going low to high can set a low bit that prevents you from setting a more valuable high bit later. The top-down order guarantees each decision is final -- no higher pivot can undo it.

---

Quick Recap

• Each bit of a number is an independent coordinate in \(\text{GF}(2)\). XOR is vector addition. AND is coordinate-wise multiplication. The set of all XOR combinations forms a vector space.
• The XOR basis stores at most \(B\) vectors (one per bit position). Each vector "owns" its highest set bit as a pivot. Insertion is Gaussian elimination: reduce the incoming number against existing pivots until it either dies (dependent) or claims a new pivot (independent).
• Max XOR: greedily pick basis vectors from highest pivot down. Count distinct XORs: \(2^{|\text{basis}|}\). Check reachability: reduce the target through the basis and see if it hits zero.
• Real Gaussian elimination is the same algorithm with subtraction instead of XOR, plus partial pivoting for numerical stability. Handles unique solutions, inconsistent systems, and underdetermined systems.

---

Problems

Problem	Link	Difficulty	Technique
SPOJ XMAX -- XOR Maximization	spoj.com/problems/XMAX	Medium	Build XOR basis, query max XOR
CSES -- System of Linear Equations	cses.fi/problemset/task/2171	Medium	Real Gaussian elimination with partial pivoting
CF 895C -- Square Subsets	codeforces.com/problemset/problem/895/C	Hard	XOR basis over prime exponent parities, count subsets with all-even exponents
CF 959F -- Mahmoud and Ehab and another array construction task	codeforces.com/problemset/problem/959/F	Hard	XOR basis + greedy construction to avoid target