XOR / Linear Basis

Treat integers as vectors over ${\mathbb{F}}_2$ (bit $i$ is coordinate $i$). XOR is vector addition, so a set of numbers spans a linear subspace, and Gaussian elimination gives a basis of at most $B$ elements (30 or 60 bits).

The structure

struct XorBasis {
    static const int B = 60;
    long long basis[B] = {};
    int sz = 0;
 
    bool insert(long long x) {                 // returns true if x expanded the span
        for (int i = B - 1; i >= 0; i--) {
            if (!(x >> i & 1)) continue;
            if (!basis[i]) { basis[i] = x; sz++; return true; }
            x ^= basis[i];
        }
        return false;                          // x was already representable
    }
 
    bool contains(long long x) const {
        for (int i = B - 1; i >= 0; i--)
            if (x >> i & 1) { if (!basis[i]) return false; x ^= basis[i]; }
        return x == 0;
    }
 
    long long maxXor(long long start = 0) const {
        long long res = start;
        for (int i = B - 1; i >= 0; i--)
            if (basis[i] && (res ^ basis[i]) > res) res ^= basis[i];
        return res;
    }
};

basis[i] holds a vector whose highest set bit is $i$ — the reduced row echelon form, maintained incrementally.

Each insertion is $O(B)$, so building from $n$ numbers is $O(nB)$.

What it answers

Question	Method
Maximum XOR of any subset	greedy from the top bit
Minimum non-zero XOR of a subset	the smallest basis element after full reduction
Is $x$ representable as a subset XOR?	contains(x)
Number of distinct subset XORs	$2^{\mathrm{sz}}$
Number of subsets giving a specific XOR	$2^{n-\mathrm{sz}}$ if representable, else 0
$k$-th smallest subset XOR	fully reduce the basis, then read $k$ in binary
Rank of the set over ${\mathbb{F}}_2$	sz
Merge two sets	insert one basis into the other, $O(B^2)$

The $2^{n-\mathrm{sz}}$ fact is the one people forget: every achievable XOR value is achieved by exactly $2^{n-\mathrm{sz}}$ subsets, because the kernel of the map has that size.

$k$-th smallest subset XOR

Fully reduce so each basis vector’s leading bit appears in no other vector:

void reduce() {
    for (int i = 0; i < B; i++)
        if (basis[i])
            for (int j = i + 1; j < B; j++)
                if (basis[j] >> i & 1) basis[j] ^= basis[i];
}
long long kth(long long k) {                   // 0-indexed among the 2^sz values
    reduce();
    long long res = 0;
    int idx = 0;
    for (int i = 0; i < B; i++)
        if (basis[i]) { if (k >> idx & 1) res ^= basis[i]; idx++; }
    return res;
}

After reduction, the basis vectors are independent in each bit position, so the $k$-th value is read directly from $k$‘s binary representation.

Basis vs binary trie

	XOR basis	Binary trie
Represents	the span of the set	the elements of the set
Max XOR over subsets	✔	✘
Max XOR with a single element	✘	✔
Count elements with a property	✘	✔
Deletion	hard	✔
Memory	$O(B)$	$O(nB)$
Merge two structures	$O(B^2)$	$O(nB)$

Read the problem carefully: “choose a subset” → basis; “choose an element” → trie.

Range queries on a basis

Prefix bases. Maintain, for each prefix, a basis where each vector also records the latest index at which it could be inserted. Then a query on $[l,r]$ uses the prefix-$r$ basis restricted to vectors with index $\ge l$:

long long b[B], pos[B];
void insert(long long x, int idx) {
    for (int i = B-1; i >= 0; i--) {
        if (!(x >> i & 1)) continue;
        if (!b[i]) { b[i] = x; pos[i] = idx; return; }
        if (pos[i] < idx) { swap(b[i], x); swap(pos[i], idx); }   // keep the newer one
        x ^= b[i];
    }
}
// query max XOR over [l, r]: use only basis vectors with pos >= l

$O(nB)$ preprocessing, $O(B)$ per query. This is the standard solution to “maximum subset XOR in a range”.

Merging on a tree. Bases merge in $O(B^2)$, which makes them usable with small-to-large, segment trees over ranges, and binary lifting on trees (maximum XOR on a tree path).

Cycle space of a graph

The XOR of edge weights around any cycle forms a linear space. Build a spanning tree, and for each non-tree edge insert dist[u] ^ dist[v] ^ w into a basis. Then:

• Maximum XOR path from $u$ to $v$ = maxXor(dist[u] ^ dist[v]).
• The number of distinct path XOR values between two vertices is $2^{\mathrm{sz}}$.

This is a beautiful application: a graph problem reduced entirely to linear algebra over ${\mathbb{F}}_2$.

See also: Linear Basis · Binary Trie · Gaussian Elimination