lower_bound_eytzinger.hpp

		
constexpr int portable_ffs(uint32_t mask) {

if (std::is_constant_evaluated()) {
	if (mask == 0) return 0;

	auto count = 1;
	while ((mask & 1U) == 0) {
		mask >>= 1;
		++count;
	}
	return count;
}

unsigned long r;
if (_BitScanForward(&r, mask)) {
	return static_cast<int>(r + 1);
}

return 0;
}

template <class Iterator, class K, class C>
constexpr Iterator lower_bound_eytzinger(Iterator beg, Iterator end, const K& key, const C& comp) {
	auto k = 1;
	auto n = std::distance(beg, end);

	while (k <= n) {
		//__builtin_prefetch(b + k * block_size);
		auto c = comp(*(beg + k - 1), key);
		k = 2 * k + static_cast<int>(c);
	}

	k >>= util::portable_ffs(~k);
	return beg + k - 1;
}