Xor Basis
(math/xor_basis.hpp)

• View this file on GitHub
• Last update: 2026-10-27 07:17:18+09:00
• Include: #include "math/xor_basis.hpp"

概要

• 非負整数の集合が xor で張る空間 $V$ を扱う。

使い方

• xor_basis<T = long long>(): $V = {0}$ で初期化する。
• insert(x): $V$ に x を加え、$V$ が広がったかを返す。
• contains(x): x が $V$ に入るかを返す。
• size(): $V$ の次元を返す。$\lvert V \rvert = 2^{\mathrm{size}()}$。
• max(xor_val = 0): $v \in V$ にわたる v ^ xor_val の最大値を返す。
• min(xor_val = 0): $v \in V$ にわたる v ^ xor_val の最小値を返す。
• kth_smallest(k, xor_val = 0): v ^ xor_val ($v \in V$) を昇順に並べたときの k 番目 (0-indexed) を返す。
• kth_largest(k, xor_val = 0): v ^ xor_val ($v \in V$) を降順に並べたときの k 番目 (0-indexed) を返す。

制約

• T は整数型
• $0 \le x, \mathrm{xor_val}$
• kth_smallest, kth_largest: $0 \le k < 2^{\mathrm{size}()}$

計算量

• 各操作: $\mathcal{O}(\mathrm{size}())$

Verified with

• test/unit/xor_basis.test.cpp

Code

#pragma once
#include <algorithm>
#include <bit>
#include <cassert>
#include <concepts>
#include <functional>
#include <limits>
#include <type_traits>
#include <vector>
template <std::integral T = long long> struct xor_basis {
    xor_basis() = default;
    int size() const {
        return int(b.size());
    }
    bool insert(T x) {
        x = reduce(x);
        if (x == 0) return false;
        T p = T(1) << (std::bit_width(std::make_unsigned_t<T>(x)) - 1);
        for (T& v : b) {
            if (v & p) v ^= x;
        }
        b.insert(std::lower_bound(b.begin(), b.end(), x, std::greater<T>()), x);
        return true;
    }
    bool contains(T x) const {
        return reduce(x) == 0;
    }
    T max(T xor_val = 0) const {
        check(xor_val);
        for (T v : b) xor_val = std::max(xor_val, T(xor_val ^ v));
        return xor_val;
    }
    T min(T xor_val = 0) const {
        return reduce(xor_val);
    }
    T kth_smallest(T k, T xor_val = 0) const {
        int r = size();
        assert(0 <= k && (r >= std::numeric_limits<T>::digits || k < (T(1) << r)));
        T x = reduce(xor_val);
        for (int i = 0; i < r; i++) {
            if ((k >> (r - 1 - i)) & 1) x ^= b[i];
        }
        return x;
    }
    T kth_largest(T k, T xor_val = 0) const {
        int r = size();
        T all = r == 0 ? 0 : ((T(1) << (r - 1)) - 1) * 2 + 1;
        assert(0 <= k && k <= all);
        return kth_smallest(all - k, xor_val);
    }

  private:
    std::vector<T> b;
    static void check([[maybe_unused]] T x) {
        if constexpr (std::is_signed_v<T>) assert(x >= 0);
    }
    T reduce(T x) const {
        check(x);
        for (T v : b) x = std::min(x, T(x ^ v));
        return x;
    }
};

#line 2 "math/xor_basis.hpp"
#include <algorithm>
#include <bit>
#include <cassert>
#include <concepts>
#include <functional>
#include <limits>
#include <type_traits>
#include <vector>
template <std::integral T = long long> struct xor_basis {
    xor_basis() = default;
    int size() const {
        return int(b.size());
    }
    bool insert(T x) {
        x = reduce(x);
        if (x == 0) return false;
        T p = T(1) << (std::bit_width(std::make_unsigned_t<T>(x)) - 1);
        for (T& v : b) {
            if (v & p) v ^= x;
        }
        b.insert(std::lower_bound(b.begin(), b.end(), x, std::greater<T>()), x);
        return true;
    }
    bool contains(T x) const {
        return reduce(x) == 0;
    }
    T max(T xor_val = 0) const {
        check(xor_val);
        for (T v : b) xor_val = std::max(xor_val, T(xor_val ^ v));
        return xor_val;
    }
    T min(T xor_val = 0) const {
        return reduce(xor_val);
    }
    T kth_smallest(T k, T xor_val = 0) const {
        int r = size();
        assert(0 <= k && (r >= std::numeric_limits<T>::digits || k < (T(1) << r)));
        T x = reduce(xor_val);
        for (int i = 0; i < r; i++) {
            if ((k >> (r - 1 - i)) & 1) x ^= b[i];
        }
        return x;
    }
    T kth_largest(T k, T xor_val = 0) const {
        int r = size();
        T all = r == 0 ? 0 : ((T(1) << (r - 1)) - 1) * 2 + 1;
        assert(0 <= k && k <= all);
        return kth_smallest(all - k, xor_val);
    }

  private:
    std::vector<T> b;
    static void check([[maybe_unused]] T x) {
        if constexpr (std::is_signed_v<T>) assert(x >= 0);
    }
    T reduce(T x) const {
        check(x);
        for (T v : b) x = std::min(x, T(x ^ v));
        return x;
    }
};

Back to top page