Basis of xor (tools/xor_basis.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-01-25 08:45:50+09:00
• Include: #include "tools/xor_basis.hpp"
• Link: https://twitter.com/noshi91/status/1200702280128856064

template <typename InputIterator, typename OutputIterator>
void xor_basis(InputIterator begin, InputIterator end, OutputIterator result);

It stores the basis of $[\mathrm{begin}, \mathrm{end})$ to result.

Constraints

• None

Time Complexity

• $O(N^2)$ where $N$ is end - begin

References

• @noshi91 - Twitter

License

• Unknown

Author

• noshi91

Depends on

• chmin function (tools/chmin.hpp)

Verified with

• tests/xor_basis.test.cpp

Code

#ifndef TOOLS_XOR_BASIS_HPP
#define TOOLS_XOR_BASIS_HPP

#include <type_traits>
#include <vector>
#include "tools/chmin.hpp"

// Source: https://twitter.com/noshi91/status/1200702280128856064
// License: unknown
// Author: noshi91

namespace tools {
  template <typename InputIterator, typename OutputIterator>
  void xor_basis(const InputIterator& begin, const InputIterator& end, OutputIterator result) {
    using T = ::std::decay_t<decltype(*begin)>;

    ::std::vector<T> basis;
    for (auto it = begin; it != end; ++it) {
      T e = *it;
      for (const T& b : basis) {
        ::tools::chmin(e, e ^ b);
      }
      if (e != 0) {
        basis.push_back(e);
      }
    }

    for (const T& b : basis) {
      *result = b;
      ++result;
    }
  }
}

#endif

#line 1 "tools/xor_basis.hpp"



#include <type_traits>
#include <vector>
#line 1 "tools/chmin.hpp"



#line 5 "tools/chmin.hpp"
#include <utility>

namespace tools {

  template <typename M, typename N>
  bool chmin(M& lhs, const N& rhs) {
    bool updated;
    if constexpr (::std::is_integral_v<M> && ::std::is_integral_v<N>) {
      updated = ::std::cmp_less(rhs, lhs);
    } else {
      updated = rhs < lhs;
    }
    if (updated) lhs = rhs;
    return updated;
  }
}


#line 7 "tools/xor_basis.hpp"

// Source: https://twitter.com/noshi91/status/1200702280128856064
// License: unknown
// Author: noshi91

namespace tools {
  template <typename InputIterator, typename OutputIterator>
  void xor_basis(const InputIterator& begin, const InputIterator& end, OutputIterator result) {
    using T = ::std::decay_t<decltype(*begin)>;

    ::std::vector<T> basis;
    for (auto it = begin; it != end; ++it) {
      T e = *it;
      for (const T& b : basis) {
        ::tools::chmin(e, e ^ b);
      }
      if (e != 0) {
        basis.push_back(e);
      }
    }

    for (const T& b : basis) {
      *result = b;
      ++result;
    }
  }
}

Back to top page