Lab 08 — XOR Linear Basis

Goal

Build a linear basis over GF(2) for a set of integers and answer the three canonical queries in O(60) each: maximum subset XOR, “can value v be formed as a subset XOR”, and k-th smallest span value. This is Gaussian elimination wearing a bitmask costume — the standard weapon for every CF “XOR of some subset” problem, and the structured alternative to the bitwise trie from phase-03 lab-07.

Background Concepts

Integers are vectors. A 60-bit integer is a vector in GF(2)⁶⁰; XOR is vector addition (each bit position an independent coordinate mod 2). “Some subset XORs to v” = “v is in the span”. All of linear algebra applies: span, independence, rank, basis.

Basis by bit position. Keep basis[b] = a vector whose highest set bit is b (or 0 if none). Insertion: walk x’s bits from high to low; at each set bit b, if basis[b] exists, reduce x ^= basis[b]; else store x there and stop. If x reduces to 0, it was already in the span — dependent. This is online Gaussian elimination, one column at a time.

Span structure. With rank r independent vectors out of n inserted, the span has exactly 2ʳ distinct values, and each is produced by exactly 2^(n−r) of the 2ⁿ subsets (each dependent element doubles every count uniformly). The empty subset contributes 0 — 0 is always in the span.

Row-reduced (canonical) form. After insertion the basis is echelon but not canonical: a row may still contain lower rows’ pivot bits. Eliminating them (each pivot bit appears in exactly one row) makes the rows, sorted ascending, generate span values monotonically: XOR-combining rows selected by the bits of k yields the k-th smallest span value. That’s the k-th query in O(60).

Basis vs trie. The bitwise trie (phase-03 lab-07) answers “max x XOR (one array element)”. The basis answers “max XOR of any subset”. Different questions — see follow-ups.

Interview Context

FAANG asks the trie problems (LC 421, LC 1707); the basis itself is CF Div 1/2 staple, ICPC regular, and a favorite of quant firms because it’s “do you actually know linear algebra” in disguise. Interview signal: the moment you say “these are vectors over GF(2), so I’ll row-reduce”, you’ve separated yourself from everyone pattern-matching on tries. Derive-from-scratch is expected; it’s 25 lines.

Problem Statement (LC 421)

Primary: Maximum XOR subset (classic CF/GFG): given a[1..n], find the maximum XOR over all 2ⁿ subsets. Related LC anchors:

• LC 421 (Maximum XOR of Two Numbers in an Array): max over pairs — trie territory, but the basis’s max_xor(start) machinery is the same greedy.
• LC 1707 (Maximum XOR With an Element From Array): max x XOR a[i] with a[i] ≤ m — offline sorted trie insertion; the trie-flavored cousin.

Constraints

• 1 ≤ n ≤ 10⁵; 0 ≤ a[i] < 2⁶⁰ (fix bits = 60; rank ≤ 60 regardless of n).
• Queries (contains / max / k-th): up to 10⁵, each O(bits).
• k-th query: 1 ≤ k ≤ 2^rank.

Clarifying Questions

1. Is the empty subset allowed? (Yes — 0 is in the span; matters for “minimum XOR” and k = 1.)
2. Max element bit width? (Sets the loop bound; 60 covers 10¹⁸, 30 covers 10⁹.)
3. Duplicates in input? (Fine — second copy reduces to 0, rejected as dependent, counted in n−rank.)
4. Do I need which subset achieves the max, or just the value? (Value; recovering a witness needs tracking masks alongside — doubles state.)
5. Are elements inserted online or all up front? (Basis is naturally online; deletion is NOT supported — rebuild or use offline tricks.)

Examples

a = [3, 10, 5, 25, 2, 8] → rank 5 (8 is dependent), span size 2⁵ = 32
max subset XOR = 31 (witness: 3^5^25), each span value formed 2^(6−5) = 2 ways
a = [1, 2, 3] → rank 2 (3 = 1^2 dependent), span {0, 1, 2, 3}, each formed 2×
contains(3) = True, contains(4) = False
kth on [1, 2, 3]: kth(1) = 0, kth(2) = 1, kth(3) = 2, kth(4) = 3
LC 421 on [3, 10, 5, 25, 2, 8] → best pair 5^25 = 28 (pairs ≠ subsets: 28 < 31)

Initial Brute Force

Enumerate all 2ⁿ subsets, XOR each, take max / collect set for membership and k-th. Ten lines; the stress oracle for n ≤ 20 (pair with phase-07 lab-06 stress testing).

Brute Force Complexity

O(2ⁿ · n) time, O(2ⁿ) space for the value set. n = 40 is already 10¹²; n = 10⁵ is absurd. Meet-in-the-middle (phase-03 lab-09) buys n ≈ 40 for max-subset-XOR — still exponential.

Optimization Path

1. Brute force 2ⁿ — oracle only.
2. Observe XOR = GF(2) addition → the answer set is a linear span → at most 2⁶⁰ ≠ 2ⁿ structure, rank ≤ 60.
3. Online Gaussian elimination: insert each element in O(60) → basis. Max via greedy high-bit descent; membership via reduction; total O(n · 60).
4. k-th queries: one O(60²) row reduction, then O(60) per query.

Final Expected Approach

class XorBasis:
    """Linear basis over GF(2) for integers < 2^bits. All ops O(bits)."""
    def __init__(self, bits=60):
        self.bits = bits
        self.basis = [0] * bits           # basis[b]: vector with highest bit b, or 0

    def insert(self, x):
        """True if x was independent (basis grew), False if x already in span."""
        for b in range(self.bits - 1, -1, -1):
            if not (x >> b) & 1:
                continue
            if not self.basis[b]:
                self.basis[b] = x
                return True
            x ^= self.basis[b]
        return False

    def contains(self, x):
        for b in range(self.bits - 1, -1, -1):
            if (x >> b) & 1:
                if not self.basis[b]:
                    return False
                x ^= self.basis[b]
        return True

    def max_xor(self, start=0):
        res = start
        for b in range(self.bits - 1, -1, -1):
            if self.basis[b] and (res ^ self.basis[b]) > res:
                res ^= self.basis[b]
        return res

    @property
    def rank(self):
        return sum(1 for v in self.basis if v)

    def reduced(self):
        """Row-reduced echelon rows, ascending: each pivot bit in exactly one row."""
        rows = []                          # (pivot_bit, vector), pivots ascending
        for b in range(self.bits):
            if self.basis[b]:
                v = self.basis[b]
                for pb, pv in rows:
                    if (v >> pb) & 1:
                        v ^= pv
                rows.append((b, v))
        return [v for _, v in rows]

    def kth(self, k):
        """k-th smallest span value, 1-indexed (kth(1) == 0). −1 if out of range."""
        rows = self.reduced()
        if not 1 <= k <= 1 << len(rows):
            return -1
        k -= 1
        res = 0
        for i, v in enumerate(rows):
            if (k >> i) & 1:
                res ^= v
        return res

def max_subset_xor(nums):
    b = XorBasis(max(nums).bit_length() if nums else 1)
    for x in nums:
        b.insert(x)
    return b.max_xor()

Data Structures Used

• Fixed array basis[0..bits) — the whole structure is 60 machine words.
• Row-reduced copy (list of ≤ 60 ints) built on demand for k-th queries.

Correctness Argument

Insertion invariant: basis[b] is 0 or has highest bit exactly b; the multiset span never changes, because reducing x by basis vectors replaces it with x ⊕ (span element) — elementary row operations preserve span. x reaches 0 iff it was a GF(2) combination of stored vectors, so the return value is exactly independence.

Greedy max: descend bits high→low; taking res ^= basis[b] when it increases res is optimal because a set bit at position b dominates all lower bits combined (2ᵇ > 2ᵇ−1), and lower basis vectors cannot disturb bit b (their highest bit is < b). Exchange argument, same skeleton as the trie greedy in LC 421.

k-th monotonicity: after full reduction, pivot bit pᵢ appears only in row i. For masks k < k' differing highest at bit j: rows above j are chosen identically, rows below cannot touch bit p_j, so value(k’) has bit p_j set where value(k) doesn’t, and all higher bits agree → value(k’) > value(k). Strictly increasing in k, hence kth(k) is the k-th smallest.

Counting: rank r vectors are independent → 2ʳ distinct combinations; each of the n−r dependent inserts doubles the number of subsets hitting every value equally → 2^(n−r) each. (Verified against full subset enumeration in tests.)

Complexity

Implementation Requirements

• insert returns bool — required for rank/counting answers; don’t discard it.
• Bit loop bound is a constructor parameter; default 60, never hardcode 32.
• max_xor(start) must accept a start value (LC 1707-style “x XOR best” queries).
• kth must treat k = 1 as 0 (empty subset) and reject out-of-range k.
• No deletion API — document that; rebuilds are O(n · 60).

Tests

• 300 random arrays (n ≤ 10, values < 2⁸) vs full 2ⁿ subset enumeration: max, membership for every probe, k-th for every k in range, rank = independent-insert count, span size 2^rank, every span value formed exactly 2^(n−rank) times.
• max_xor(start) vs max(start ^ v for v in span) with random starts.
• Reduced rows sorted ascending and regenerate the same span.
• Degenerates: all zeros (rank 0, span {0}, kth(1)=0), single element, duplicates.
• 60-bit values: insert 50 random < 2⁵⁹, membership of elements and of ad-hoc XOR combos. (All executed for this lab.)

Follow-up Questions

• Basis or trie — how do you choose? → Subset-XOR questions (max subset XOR, “is v reachable”, k-th value) → basis: the answer set is a span, size 2ʳ. Pairwise-XOR questions (LC 421 max pair, LC 1707 bounded max) → trie: you need “best partner among actual elements”, and the span contains values no single element attains.
• Count subsets XORing to exactly v. → 0 if not contains(v), else 2^(n−rank) — every reachable value is hit by equally many subsets. (Empty subset counts for v = 0; subtract 1 if the problem demands non-empty.)
• Merge two bases. → insert every nonzero vector of one into the other: O(60²). Powers the segment-tree-of-bases / divide-and-conquer patterns; note there’s no efficient “un-merge”.
• Range queries: max subset XOR over a[l..r], offline. → prefix bases with time tags: keep for each prefix a basis remembering the latest insertion index per pivot, prefer newer vectors when inserting; query (l, r) uses pivots with tag ≥ l. O((n + q) · 60). CF-standard technique.
• Where’s the “real” linear algebra? → this IS Gaussian elimination over GF(2): insert = eliminate against pivot rows; rank–nullity says #subsets mapping to each value = 2^(dim kernel) = 2^(n−r); reduced() is Gauss–Jordan back-substitution. Saying it this way in an interview is worth more than the code.
• Minimum non-zero subset XOR? → smallest reduced row (= kth(2)). And max is the XOR of all reduced rows — every pivot set.

Product Extension

Erasure coding and RAID parity are literally spans over GF(2): a stripe’s parity blocks are XOR combinations, and “can we reconstruct block v from surviving blocks” is contains(v) on the survivors’ basis. Same math in network coding (butterfly routing) and in deduplicating feature-flag bitmask configs: rank tells you how many independent toggles actually exist across 10⁵ stored configs.

Language/Runtime Follow-ups

• Python: arbitrary-precision ints make bits > 64 free (hash prefixes, 128-bit ids); the O(60) loops are ~µs — no need for numpy.
• C++: uint64_t basis[60]; find the high bit with 63 - __builtin_clzll(x) to jump straight to the pivot instead of scanning — insertion becomes O(rank).
• Java: long[] + Long.numberOfLeadingZeros; beware >>> vs >> on the sign bit if you ever use bit 63.
• Go: bits.Len64(x) − 1 for the pivot; fixed [60]uint64 array keeps it allocation-free.
• JS/TS: Number XOR truncates to 32 bits (^ operates on int32!) — anything beyond 2³¹ needs BigInt throughout.

Common Bugs

1. Low-to-high insertion: reducing from bit 0 upward breaks the invariant “basis[b] has highest bit b” — vectors land in wrong slots and max_xor misses bits.
2. Wrong return on dependent insert: returning True when x reduced to 0 corrupts rank, and with it the 2^(n−rank) counting answers.
3. k-th on the raw basis: without full row reduction, mask order is not value order — answers are span members but not the k-th. The monotonicity proof needs exclusive pivots.
4. Forgetting 0 ∈ span: k-th smallest with k = 1 must be 0 (empty subset); minimum non-zero is kth(2). Off-by-one between the two conventions is endemic.
5. Hardcoded 32 bits: values up to 10¹⁸ silently lose their top 28 bits; the basis “works” on samples and fails on real data.
6. basis[b] > res instead of (res ^ basis[b]) > res: the greedy must test the XOR result — a basis vector can have bit b set where res also does, making XOR decrease res.

Debugging Strategy

Shrink to 4-bit values and print the basis as binary rows after every insert — the echelon shape (one row per pivot, highest bit on the diagonal) is visually checkable. For [1, 2, 3]: insert 1 → row at bit 0; insert 2 → row at bit 1; insert 3 → 3^2=1, 1^1=0 → rejected, rank 2. If kth misbehaves, print reduced() and confirm no row contains another row’s pivot bit; then table kth(1..2ʳ) against the sorted brute-force span — the first mismatch’s mask tells you which row still carries a stray pivot. Keep the 2ⁿ enumerator from Tests as the permanent oracle (lab-06 stress harness).

Mastery Criteria

• XorBasis with insert/contains/max_xor from blank, first-run correct, in <10 minutes.
• Added reduced() + kth and passed a brute-force diff in <10 more minutes.
• Stated the 2^rank / 2^(n−rank) counting facts with proof sketch, unprompted, in <2 minutes.
• Articulated basis-vs-trie decision rule on LC 421 vs max-subset-XOR in <1 minute.
• Solved max-subset-XOR cold (classic CF/GFG) in <15 minutes including the stress test.
• Explained the whole structure as Gaussian elimination + rank–nullity to a linear-algebra-literate interviewer.