← all categories

Xor Basis 9555684b

XOR linear basis over GF(2), BIT bits wide. add() inserts a vector into the basis (returns false if it was already in the span); check() tests membership without modifying the basis. Distinct from xor-trie.h (which enumerates max-XOR against an explicit multiset, not a basis).

Time: O(BIT) per operation. tested

content/math/xor-basis.h

template <int BIT>
struct XorBasis {
    array<bitset<BIT>, BIT> b{};

    bool add(bitset<BIT> x) {
        for (int i = BIT - 1; i >= 0; i--) {
            if (!x.test(i)) continue;
            if (b[i].any()) x ^= b[i];
            else { b[i] = x; return true; }
        }
        return false;
    }

    bool check(bitset<BIT> x) {
        for (int i = BIT - 1; i >= 0; i--) {
            if (!x.test(i)) continue;
            if (!b[i].any()) return false;
            x ^= b[i];
        }
        return true;
    }
};