Skip to content

XOR Basis Hot Sheet

Use this page when the statement is about xor of some subset and the real question is about the span generated by the input numbers.

Do Not Use When

  • the query is against one stored number maximizing xor with x
  • prefix xor or one tree xor identity already solves the task directly
  • the problem is ordinary modular linear algebra instead of bitwise xor structure

Choose By Signal

  • maximum subset xor or "can we xor some chosen numbers to get x?" -> xor-basis.cpp
  • online insert / erase / best partner xor with one current x -> compare Binary Trie hot sheet
  • xor path improved by cycle freedom -> same xor-basis worldview, but usually inside a graph reduction

Core Invariants

  • at most one stored basis vector has highest set bit b
  • insertion either adds one new independent pivot vector or collapses to 0
  • the basis spans exactly the same xor-space as the original numbers
  • x is representable iff elimination by the basis reduces it to 0

Main Traps

  • confusing subset xor with pair xor
  • thinking every inserted number increases the basis dimension
  • scanning bits low-to-high in max-xor queries
  • overclaiming kth-xor or merge features from a starter that only supports insert / representability / maximum

Exact Starter In This Repo

Reopen Paths