XorBasis

XorBasis maintains a linear basis of values generated by XOR operations.

If we regard an integer as a bit vector, XOR is addition over GF(2).
Therefore, by keeping only linearly independent values, subset XOR queries can be answered efficiently, just like Gaussian elimination.

Use cases

Typical use cases include:

• maximum subset XOR
• maximizing or minimizing x xor y, where y is generated by XORing inserted values
• checking whether a value x is representable
• maximum XOR path using cycle XORs in a graph
• merging XOR bases for range queries

Idea

Treat each bit of an integer as a coordinate over GF(2).
For example, 13 = 1101_2 is a vector over GF(2).

When adding x, inspect bits from high to low.

• If there is no basis vector with that pivot bit, store x as a new basis vector.
• If such a basis vector already exists, replace x by x xor basis to eliminate that high bit.

If x becomes zero, the original value was representable by the existing basis.
Otherwise, the remaining value has a new pivot bit and is inserted as an independent vector.

This is the same idea as Gaussian elimination over GF(2).

Import

import atcoder/extra/math/xor_basis

Type

type XorBasis[T: SomeInteger]

T is an integer type, usually int, int64, or uint64.

Constructor

proc initXorBasis[T: SomeInteger](maxLog: int = 60): XorBasis[T]

maxLog is the largest bit index inspected by the basis.

For example, if all values satisfy 0 <= x < 2^60, use maxLog = 59, or maxLog = 60 with a little extra room.

Operations

proc rank[T](xb: XorBasis[T]): int
proc len[T](xb: XorBasis[T]): int
proc empty[T](xb: XorBasis[T]): bool

proc add[T](xb: var XorBasis[T], x: T): bool
proc addAll[T](xb: var XorBasis[T], xs: openArray[T])

proc reduce[T](xb: XorBasis[T], x: T): T
proc canRepresent[T](xb: XorBasis[T], x: T): bool
proc contains[T](xb: XorBasis[T], x: T): bool

proc maxXor[T](xb: XorBasis[T]): T
proc maxXor[T](xb: XorBasis[T], x: T): T
proc minXor[T](xb: XorBasis[T], x: T): T

proc basisSeq[T](xb: XorBasis[T]): seq[T]
proc merge[T](a, b: XorBasis[T]): XorBasis[T]

• rank() / len() returns the number of independent basis vectors.
• add(x) inserts x and returns true if the rank increases.
• reduce(x) reduces x by the current basis.
• canRepresent(x) checks whether x is representable.
• x in xb is also available for representation tests.
• maxXor() returns the maximum representable XOR value.
• maxXor(x) returns the maximum value of x xor y.
• minXor(x) returns the minimum value of x xor y.
• merge(a, b) combines two bases.

Example

var xb = initXorBasis[int](maxLog = 4)doAssert xb.add(3) == truedoAssert xb.add(5) == truedoAssert xb.add(6) == false  # 6 = 3 xor 5doAssert xb.rank == 2doAssert 6 in xbdoAssert 1 notin xbdoAssert xb.maxXor() == 6doAssert xb.maxXor(1) == 7doAssert xb.minXor(7) == 1

Merge

Bases can be merged.

var a = initXorBasis[int](maxLog = 3)var b = initXorBasis[int](maxLog = 3)discard a.add(1)discard a.add(2)discard b.add(4)let c = merge(a, b)doAssert c.maxXor() == 7doAssert 7 in c

Nim-friendly usage

Since contains is defined, representability can be written with in.

if x in xb:
  echo "x is representable"

Also, rank is a proc, but Nim UFCS allows xb.rank.

doAssert xb.rank == xb.len

Constraints

This implementation is mainly intended for non-negative integers satisfying 0 <= x < 2^(maxLog + 1).

If negative integers are inserted, their uint64 representation is used. For competitive programming, non-negative values are recommended.

Complexity

Let B = maxLog + 1.

• add: O(B)
• reduce: O(B)
• canRepresent: O(B)
• maxXor, minXor: O(B)
• merge: about O(B^2), but usually B <= 64
• memory: O(B)

Practice problems

Related resources and libraries

• cp-algorithms: Gaussian elimination / linear algebra over fields
• Library Checker: GF(2) linear algebra problems
• Codeforces: subset XOR / maximum XOR basis style problems
• Nyaan Library: Binary Basis / XOR Basis style modules
• ei1333 Library: Linear Basis style modules