XOR 基底の内部演算

components/xor_basis_core.hpp · GitHub で見る

共通ページ

math/xor_basis.hpp が使う固定サイズの内部表現です。通常は公開側の XorBasis を使います。

操作・フィールド	内容	計算量
xor_basis_detail::Core<UInt,Bits>	符号なし整数の XOR 基底	\(O(Bits)\)
row / dimension	先頭 dimension 個に詰めた基底／次元	\(O(1)\)
at	各最上位ビットの基底位置に 1 を加えた値。0 は未使用	\(O(1)\)
digits / mask	要素型のビット数／下位 Bits bit のマスク	\(O(1)\)
valid(x)	x が下位 Bits bit に収まるか	\(O(1)\)
pivot(x)	最上位の 1 の位置。x は非零とする	\(O(1)\)
insert(x)	基底を追加し、格納位置を返す。従属なら -1	\(O(r)\)
minimize(x) / maximize(x)	部分集合の XOR と x の XOR の最小値／最大値	\(O(r)\)
xor_basis_detail::reduce_rows<UInt,maximum>(x,row,count)	消去順の基底に沿って最小化する。maximum=true なら最大化	\(O(\mathrm{count})\)

基底は格納順に消去できる形で保持します。行の直接更新は公開ライブラリの内部からだけ行い、at・dimension も同時に更新します。

構築・初期化・保存領域は \(O(\mathrm{Bits})\)。追加・最小最大は次元を \(r\) として \(O(r)\)、次元が Bits と等しい場合は \(O(1)\)。valid・pivot は \(O(1)\) です。

検証コード

• test/xor_basis_intersection.test.cpp

コード

#ifndef XOR_BASIS_CORE_HPP
#define XOR_BASIS_CORE_HPP

#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <cstdint>
#include <limits>
#include <type_traits>

namespace xor_basis_detail {
template <class UInt, bool maximum = false>
#if defined(__GNUC__) || defined(__clang__)
__attribute__((always_inline))
#endif
inline UInt reduce_rows(UInt x, const UInt *row, int count) {
	int i = 0;
	auto step = [&](UInt value) {
		if constexpr (maximum) x = std::max(x, UInt(x ^ value));
		else x = std::min(x, UInt(x ^ value));
	};
	for (; i + 4 <= count; i += 4) {
		step(row[i]); step(row[i + 1]); step(row[i + 2]); step(row[i + 3]);
	}
	for (; i < count; ++i) step(row[i]);
	return x;
}

template <class UInt, int Bits>
struct Core {
	static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt> && !std::is_same_v<UInt, bool>);
	static constexpr int digits = std::numeric_limits<UInt>::digits;
	static_assert(0 < Bits && Bits <= digits && digits <= 64);
	static constexpr UInt mask = UInt(UInt(~UInt(0)) >> (digits - Bits));
	std::array<UInt, Bits> row{};
	std::array<std::uint8_t, Bits> at{};
	int dimension = 0;
	static bool valid(UInt x) { return (x & mask) == x; }
	static int pivot(UInt x) { return int(std::bit_width(std::uint64_t(x))) - 1; }
	int insert(UInt x) {
		assert(valid(x));
		if (dimension == Bits) return -1;
		x = reduce_rows(x, row.data(), dimension);
		if (!x) return -1;
		row[dimension] = x; at[pivot(x)] = std::uint8_t(dimension + 1);
		return dimension++;
	}
	UInt minimize(UInt x) const {
		if (dimension == Bits) return UInt(x & UInt(~mask));
		x = reduce_rows(x, row.data(), dimension);
		return x;
	}
	UInt maximize(UInt x) const {
		if (dimension == Bits) return UInt(x | mask);
		x = reduce_rows<UInt, true>(x, row.data(), dimension);
		return x;
	}
};
}

#endif

Back to top page