#ifndef NO_UNIQUE_ADDRESS
# ifdef __has_cpp_attribute
# if __has_cpp_attribute(no_unique_address)
# define NO_UNIQUE_ADDRESS [[no_unique_address]]
# endif
# endif
# ifndef NO_UNIQUE_ADDRESS
# define NO_UNIQUE_ADDRESS
# endif
#endif
namespace details {
inline unsigned int bsf32(uint32_t n) noexcept {
#if defined __GNUC__
return __builtin_ctz(n);
#elif defined _MSC_VER
unsigned long ans;
_BitScanForward(&ans, n);
return ans;
#elif
static constexpr unsigned char table[32] = {
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9,
};
return table[((n & -n) * 0x077CB531) >> 57];
#endif
}
inline unsigned int bsf64(uint64_t n) noexcept {
#if defined __GNUC__
return __builtin_ctzll(n);
#elif defined _MSC_VER
unsigned long ans;
_BitScanForward64(&ans, n);
return ans;
#elif
static constexpr unsigned char table[64] = {
0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4,
62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5,
63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11,
54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6,
};
return table[((n & -n) * 0x03f79d71b4ca8b09) >> 58];
#endif
}
inline unsigned int bsr32(uint32_t n) noexcept {
#if defined __GNUC__
return 31 - __builtin_clz(n);
#elif defined _MSC_VER
unsigned long ans;
_BitScanReverse(&ans, n);
return ans;
#elif
float t = n;
uint32_t ans;
memcpy(&ans, &t, sizeof(float));
return (ans >> 23 & 255) - 127;
#endif
}
inline unsigned int bsr64(uint64_t n) noexcept {
#if defined __GNUC__
return 63 - __builtin_clzll(n);
#elif defined _MSC_VER
unsigned long ans;
_BitScanReverse64(&ans, n);
return ans;
#elif
float t = n;
uint32_t ans;
memcpy(&ans, &t, sizeof(float));
return (ans >> 23 & 255) - 127;
#endif
}
inline unsigned int popcnt32(uint32_t n) noexcept {
#if defined __GNUC__
return __builtin_popcount(n);
#elif defined _MSC_VER
return __popcnt(n);
#elif
n -= ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
return ((((n >> 4) + n) & 0x0f0f0f0f) * 0x01010101) >> 24;
#endif
}
inline unsigned int popcnt64(uint64_t n) noexcept {
#if defined __GNUC__
return __builtin_popcountll(n);
#elif defined _MSC_VER
return __popcnt64(n);
#elif
n -= ((n >> 1) & 0x5555555555555555);
n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333);
return ((((n >> 4) + n) & 0x0f0f0f0f0f0f0f0f) * 0x0101010101010101) >> 56;
#endif
}
inline unsigned int parity32(uint32_t n) noexcept {
#if defined __GNUC__
return __builtin_parity(n);
#elif defined _MSC_VER
return __popcnt(n) & 1;
#elif
n ^= n >> 1;
n ^= n >> 2;
n = (n & 0x11111111) * 0x11111111;
return (n >> 28) & 1;
#endif
}
inline unsigned int parity64(uint64_t n) noexcept {
#if defined __GNUC__
return __builtin_parityll(n);
#elif defined _MSC_VER
return __popcnt64(n) & 1;
#elif
n ^= n >> 1;
n ^= n >> 2;
n = (n & 0x1111111111111111) * 0x1111111111111111;
return (n >> 60) & 1;
#endif
}
template<typename I, bool B = 32 < std::numeric_limits<I>::digits>
struct _BitFuncImpl {
inline static unsigned int bsf(I n) noexcept { return bsf64(n); }
inline static unsigned int bsr(I n) noexcept { return bsr64(n); }
inline static unsigned int popcnt(I n) noexcept { return popcnt64(n); }
inline static unsigned int parity(I n) noexcept { return parity64(n); }
};
template<typename I>
struct _BitFuncImpl<I, false> {
inline static unsigned int bsf(I n) noexcept { return bsf32(n); }
inline static unsigned int bsr(I n) noexcept { return bsr32(n); }
inline static unsigned int popcnt(I n) noexcept { return popcnt32(n); }
inline static unsigned int parity(I n) noexcept { return parity32(n); }
};
template<typename I>
inline unsigned int bsf(I n) noexcept { return _BitFuncImpl<I>::bsf(n); }
template<typename I>
inline unsigned int bsr(I n) noexcept { return _BitFuncImpl<I>::bsr(n); }
template<typename I>
inline unsigned int popcnt(I n) noexcept { return _BitFuncImpl<I>::popcnt(n); }
template<typename I>
inline unsigned int parity(I n) noexcept { return _BitFuncImpl<I>::parity(n); }
template<typename T, size_t K = 0, bool = std::is_empty<T>::value && !std::is_final<T>::value>
struct Derivable {
private:
T val;
public:
constexpr Derivable() = default;
template<typename... Args>
constexpr Derivable(Args&&... args) noexcept(std::is_nothrow_constructible<T, Args&&...>::value) : val(std::forward<Args>(args)...) {}
inline constexpr T& value() noexcept { return val; }
inline constexpr const T& value() const noexcept { return val; }
};
template<typename T, size_t K>
struct Derivable<T, K, true> : private T {
constexpr Derivable() = default;
template<typename... Args>
constexpr Derivable(Args&&... args) noexcept(std::is_nothrow_constructible<T, Args&&...>::value) : T(std::forward<Args>(args)...) {}
inline constexpr T& value() noexcept { return *this; }
inline constexpr const T& value() const noexcept { return *this; }
};
template<typename Alloc>
struct InitializerIterator {
using traits = std::allocator_traits<Alloc>;
using pointer = typename traits::pointer;
using value_type = typename traits::value_type;
InitializerIterator(const InitializerIterator&) = delete;
InitializerIterator(InitializerIterator&& other) noexcept
: ptr(other.ptr), cur(other.cur), p_alloc(other.p_alloc)
{
other.ptr = other.cur = nullptr;
other.p_alloc = nullptr;
}
InitializerIterator(pointer ptr, Alloc& alloc) noexcept : ptr(ptr), cur(ptr), p_alloc(&alloc) {}
~InitializerIterator() noexcept {
if (!std::is_trivially_destructible<value_type>::value)
for (pointer it = ptr;it != cur;++it)
traits::destroy(*p_alloc, std::addressof(*it));
}
inline pointer release() noexcept {
return ptr = cur;
}
inline InitializerIterator& operator*() noexcept { return *this; }
inline InitializerIterator& operator++() noexcept { return *this; }
inline InitializerIterator& operator++(int) noexcept { return *this; }
InitializerIterator& operator=(const InitializerIterator&) = delete;
InitializerIterator& operator=(InitializerIterator&& other) noexcept {
ptr = other.ptr;
cur = other.cur;
p_alloc = other.p_alloc;
other.ptr = other.cur = nullptr;
other.p_alloc = nullptr;
return *this;
}
template<typename T>
inline InitializerIterator& operator=(T&& val) noexcept(noexcept(std::is_nothrow_constructible<value_type, T&&>::value)) {
traits::construct(*p_alloc, std::addressof(*cur), std::forward<T>(val));
++cur;
return *this;
}
private:
pointer ptr, cur;
Alloc* p_alloc;
};
}
作者：白
链接：https:
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
