64 bit 内の XOR 順位選択

components/xor_select.hpp · GitHub で見る

共通ページ

Predecessor Set・XOR の整数集合が共有する内部処理です。

xor_select_detail::argmin(word,key) は、1 bit の立つ位置のうち key との XOR が最小になる位置を返します。word != 0、key < 64 とします。時間・追加空間は \(O(1)\) です。

検証コード

• test/predecessor_set.test.cpp
• test/predecessor_set_priority_queue.test.cpp
• test/set_xor_min.test.cpp
• test/set_xor_min.test.cpp
• test/sortable_segtree.test.cpp
• test/topological_sort.test.cpp

コード

#ifndef XOR_SELECT_HPP
#define XOR_SELECT_HPP

#include <bit>
#include <cassert>
#include <cstdint>

namespace xor_select_detail {
inline unsigned argmin(std::uint64_t word, unsigned key) {
	assert(word && key < 64);
	if (std::has_single_bit(word)) return std::countr_zero(word);
	if ((word >> key) & 1) return key;
	unsigned shift = key & 32;
	word = std::rotl(word, shift);
	auto exchange = [&](unsigned shift, std::uint64_t mask) {
		word = ((word & mask) << shift) | ((word & ~mask) >> shift);
	};
	exchange(key & 16, 0x0000ffff0000ffffULL);
	exchange(key & 8, 0x00ff00ff00ff00ffULL);
	exchange(key & 4, 0x0f0f0f0f0f0f0f0fULL);
	exchange(key & 2, 0x3333333333333333ULL);
	exchange(key & 1, 0x5555555555555555ULL);
	return std::countr_zero(word) ^ key;
}
}

#endif

Back to top page