XOR Linear Basis

May 2026 · 30 min read

An XOR linear basis represents all XOR values you can form from a set of numbers. It is Gaussian elimination over GF(2), where each bit is a coordinate and XOR is addition. This technique is a major jump from interview bit tricks into serious competitive programming.

Mental Model

Given numbers a1, a2, ..., consider every subset XOR. The basis stores independent vectors so every possible subset XOR can be reconstructed from them, but no basis vector can be reconstructed from the others.

numbers: 5(101), 3(011), 6(110)

5 ^ 3 = 6, so 6 is dependent.
A basis can be {5, 3}; it generates {0, 5, 3, 6}.

Insertion

Keep one basis vector per highest set bit. To insert x, eliminate its highest set bit with the existing basis if possible. If no basis vector owns that bit, x becomes a new independent vector.

struct XorBasis {
    static const int LOG = 60;
    long long basis[LOG + 1] = {};

    bool insert(long long x) {
        for (int b = LOG; b >= 0; --b) {
            if (((x >> b) & 1) == 0) continue;
            if (!basis[b]) {
                basis[b] = x;
                return true;
            }
            x ^= basis[b];
        }
        return false;
    }
};

Maximum Subset XOR

To maximize the value, greedily try basis vectors from high bit to low bit. If XORing improves the answer, keep it.

long long max_xor() {
    long long ans = 0;
    for (int b = LOG; b >= 0; --b) {
        ans = max(ans, ans ^ basis[b]);
    }
    return ans;
}

This works because a higher bit dominates all lower bits. If a basis vector can set a higher bit without unsetting a more important bit, it is always beneficial.

Can a Value Be Represented?

Reduce the target using the basis. If it becomes zero, it is representable as a subset XOR.

bool can_make(long long x) {
    for (int b = LOG; b >= 0; --b) {
        if ((x >> b) & 1) {
            if (!basis[b]) return false;
            x ^= basis[b];
        }
    }
    return true;
}

Rank and Count

The rank is the number of non-zero basis vectors. If rank is r, the set generates exactly 2^r distinct XOR values. If you inserted n numbers and rank is smaller than n, some numbers were dependent.

Reduced Row-Echelon Form

For k-th smallest XOR value or clean enumeration, reduce the basis so each leading bit appears in exactly one vector.

void reduce() {
    for (int b = 0; b <= LOG; ++b) {
        if (!basis[b]) continue;
        for (int j = b + 1; j <= LOG; ++j) {
            if ((basis[j] >> b) & 1) basis[j] ^= basis[b];
        }
    }
}

Applications

Maximum subset XOR: the direct use case.
Path XOR queries: combine basis with tree paths or offline processing.
Representability: test whether a target XOR can be formed.
Counting distinct XORs: rank gives the answer immediately.

Pitfalls

Use enough bits: 60 for signed 64-bit non-negative values, 63 for full unsigned 64-bit values.
The basis answers subset XOR questions, not subsequence order questions.
For minimum positive XOR, you need reduced form or careful enumeration.

Practice Problems

CSES - Maximum Xor Subarray warmup trie solution first; compare with basis thinking.
Codeforces 1100F - Ivan and Burgers range basis basis with segment/query ordering.
Codeforces 845G - Shortest Path Problem? cycle basis reduce path XOR using cycle XORs.
Codeforces 959F - Mahmoud and Ehab and Yet Another XOR Task rank counting count subsets forming target XOR.