This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub luzhiled1333/comp-library
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/ITP1_1_A #include "src/utility/bit/count-leading-0s.hpp" #include "src/cpp-template/header/int-alias.hpp" #include "src/cpp-template/header/rep.hpp" #include "src/cpp-template/header/size-alias.hpp" #include <cassert> #include <iostream> namespace luz { usize naive_countl_zero(u64 x) { for (usize k: rrep(0, 64)) { if (x & (u64(1) << k)) { return 63 - k; } } return 64; } void main_() { for (u64 x: rep(0, 1 << 20)) { assert(countl_zero(x) == naive_countl_zero(x)); } u64 large = u64(1) << 63; assert(countl_zero(large) == naive_countl_zero(large)); std::cout << "Hello World" << std::endl; } } // namespace luz int main() { luz::main_(); }
#line 1 "unit-test/utility/bit/count-leading-0s.test.cpp" // verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/ITP1_1_A #line 2 "src/utility/bit/count-leading-0s.hpp" #line 2 "src/cpp-template/header/int-alias.hpp" #include <cstdint> namespace luz { using i32 = std::int32_t; using i64 = std::int64_t; using i128 = __int128_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using u128 = __uint128_t; } // namespace luz #line 2 "src/cpp-template/header/size-alias.hpp" #include <cstddef> namespace luz { using isize = std::ptrdiff_t; using usize = std::size_t; } // namespace luz #line 2 "src/utility/bit/popcount.hpp" #line 5 "src/utility/bit/popcount.hpp" #include <cassert> namespace luz { usize popcount(u64 x) { assert(__cplusplus <= 201703L); #ifdef __GNUC__ return __builtin_popcountll(x); #endif x -= (x >> 1) & 0x5555555555555555; x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); x += (x >> 4) & 0x0f0f0f0f0f0f0f0f; return x * 0x0101010101010101 >> 56 & 0x7f; } } // namespace luz #line 6 "src/utility/bit/count-leading-0s.hpp" #line 8 "src/utility/bit/count-leading-0s.hpp" namespace luz { usize countl_zero(u64 x) { assert(__cplusplus <= 201703L); if (x == 0) { return 64; } #ifdef __GNUC__ return __builtin_clzll(x); #endif x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; x |= x >> 32; return 64 - popcount(x); } } // namespace luz #line 4 "unit-test/utility/bit/count-leading-0s.test.cpp" #line 2 "src/cpp-template/header/rep.hpp" #line 4 "src/cpp-template/header/rep.hpp" #include <algorithm> namespace luz { struct rep { struct itr { usize i; constexpr itr(const usize i) noexcept: i(i) {} void operator++() noexcept { ++i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rep(const usize f, const usize l) noexcept : f(std::min(f, l)), l(l) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; struct rrep { struct itr { usize i; constexpr itr(const usize i) noexcept: i(i) {} void operator++() noexcept { --i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rrep(const usize f, const usize l) noexcept : f(l - 1), l(std::min(f, l) - 1) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; } // namespace luz #line 8 "unit-test/utility/bit/count-leading-0s.test.cpp" #line 10 "unit-test/utility/bit/count-leading-0s.test.cpp" #include <iostream> namespace luz { usize naive_countl_zero(u64 x) { for (usize k: rrep(0, 64)) { if (x & (u64(1) << k)) { return 63 - k; } } return 64; } void main_() { for (u64 x: rep(0, 1 << 20)) { assert(countl_zero(x) == naive_countl_zero(x)); } u64 large = u64(1) << 63; assert(countl_zero(large) == naive_countl_zero(large)); std::cout << "Hello World" << std::endl; } } // namespace luz int main() { luz::main_(); }