algorithm-dev
This documentation is automatically generated by online-judge-tools/verification-helper
verify/aoj-ITP1_1_A-popcount.test.cpp
- View this file on GitHub
- Last update: 2025-07-03 00:41:25+09:00
- Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
Depends on
Code
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"
#include <bitset>
#include <cassert>
#include <iostream>
#include <limits>
#include <random>
#include "../algorithm/Others/popcount.hpp"
#include "../algorithm/Utils/debug.hpp"
constexpr int naive_popcount(uint64_t bit) {
int res = 0;
while(bit) {
res++;
bit &= bit - 1;
}
return res;
}
int main() {
constexpr int t = 10000;
std::random_device seed;
std::mt19937_64 rng(seed());
static_assert(algorithm::popcount32(std::numeric_limits<uint32_t>::min()) == 0);
static_assert(algorithm::popcount32(std::numeric_limits<uint32_t>::max()) == 32);
static_assert(algorithm::popcount64(std::numeric_limits<uint64_t>::min()) == 0);
static_assert(algorithm::popcount64(std::numeric_limits<uint64_t>::max()) == 64);
std::uniform_int_distribution<uint32_t> uniform(std::numeric_limits<uint32_t>::min(),
std::numeric_limits<uint32_t>::max());
for(int i = 0; i < t; ++i) {
uint32_t arg = uniform(rng);
auto target = algorithm::popcount32(arg);
auto want = naive_popcount(arg);
debug(i, std::bitset<32>(arg), target, want);
assert(target == want);
}
std::uniform_int_distribution<uint64_t> uniform2(std::numeric_limits<uint64_t>::min(),
std::numeric_limits<uint64_t>::max());
for(int i = 0; i < t; ++i) {
uint64_t arg = uniform2(rng);
auto target = algorithm::popcount64(arg);
auto want = naive_popcount(arg);
debug(i, std::bitset<64>(arg), arg, target, want);
assert(target == want);
}
std::cout << "Hello World" << std::endl;
}#line 1 "verify/aoj-ITP1_1_A-popcount.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"
#include <bitset>
#include <cassert>
#include <iostream>
#include <limits>
#include <random>
#line 1 "algorithm/Others/popcount.hpp"
#include <cstdint>
namespace algorithm {
constexpr int popcount32(uint32_t bit) {
bit -= (bit >> 1) & 0x5555'5555U;
bit = (bit & 0x3333'3333U) + ((bit >> 2) & 0x3333'3333U);
bit = (bit + (bit >> 4)) & 0x0f0f'0f0fU;
bit += bit >> 8;
bit += bit >> 16;
return bit & 0x0000'003fU;
}
constexpr int popcount64(uint64_t bit) {
bit -= (bit >> 1) & 0x5555'5555'5555'5555ULL;
bit = (bit & 0x3333'3333'3333'3333ULL) + ((bit >> 2) & 0x3333'3333'3333'3333ULL);
bit = (bit + (bit >> 4)) & 0x0f0f'0f0f'0f0f'0f0fULL;
bit += bit >> 8;
bit += bit >> 16;
bit += bit >> 32;
return bit & 0x0000'0000'0000'007fULL;
}
} // namespace algorithm
#line 1 "algorithm/Utils/debug.hpp"
#include <chrono>
#include <iomanip>
#line 7 "algorithm/Utils/debug.hpp"
#include <queue>
#include <ranges>
#include <stack>
#include <string>
#include <string_view>
#include <tuple>
#include <type_traits>
#include <utility>
#ifdef DEBUG
#define debug(...) algorithm::debug::debug_internal(__LINE__ __VA_OPT__(, #__VA_ARGS__, __VA_ARGS__))
namespace algorithm {
namespace debug {
constexpr std::ostream &os = std::clog;
// Forward declaration.
template <typename Type>
void print(const Type &);
template <std::ranges::range R>
void print(const R &);
template <typename... Types>
void print(const std::basic_string<Types...> &);
void print(std::string_view);
template <typename... Types>
void print(const std::stack<Types...> &);
template <typename... Types>
void print(const std::queue<Types...> &);
template <typename... Types>
void print(const std::priority_queue<Types...> &);
template <typename T, typename U>
void print(const std::pair<T, U> &);
template <typename... Types>
void print(const std::tuple<Types...> &);
template <class Tuple, std::size_t... Idxes>
void print_tuple(const Tuple &, std::index_sequence<Idxes...>);
auto elapsed() {
static const auto start = std::chrono::system_clock::now();
return std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::system_clock::now() - start).count();
}
template <typename Type, typename... Args>
void debug_internal(int line, std::string_view context, const Type &first, const Args &...args) {
constexpr const char *open_bracket = (sizeof...(args) == 0 ? "" : "(");
constexpr const char *close_bracket = (sizeof...(args) == 0 ? "" : ")");
os << "(" << std::setw(8) << elapsed() << ") [L" << line << "] " << open_bracket << context << close_bracket << ": " << open_bracket;
print(first);
((os << ", ", print(args)), ...);
os << close_bracket << std::endl;
}
void debug_internal(int line) {
os << "(" << std::setw(8) << elapsed() << ") [L" << line << "] (empty)" << std::endl;
}
// Implementation.
template <typename Type>
void print(const Type &a) {
os << a;
}
template <std::ranges::range R>
void print(const R &r) {
os << "[";
for(auto iter = std::ranges::cbegin(r); iter != std::ranges::cend(r); ++iter) {
if(iter != std::ranges::cbegin(r)) os << " ";
print(*iter);
}
os << "]";
}
template <typename... Types>
void print(const std::basic_string<Types...> &s) {
os << s;
}
void print(std::string_view sv) {
os << sv;
}
template <typename... Types>
void print(const std::stack<Types...> &st) {
std::stack<Types...> tmp(st);
os << "[";
for(bool first = true; !tmp.empty(); tmp.pop(), first = false) {
if(!first) os << " ";
print(tmp.top());
}
os << "]";
}
template <typename... Types>
void print(const std::queue<Types...> &que) {
std::queue<Types...> tmp(que);
os << "[";
for(bool first = true; !tmp.empty(); tmp.pop(), first = false) {
if(!first) os << " ";
print(tmp.front());
}
os << "]";
}
template <typename... Types>
void print(const std::priority_queue<Types...> &pque) {
std::priority_queue<Types...> tmp(pque);
os << "[";
for(bool first = true; !tmp.empty(); tmp.pop(), first = false) {
if(!first) os << " ";
print(tmp.top());
}
os << "]";
}
template <typename T, typename U>
void print(const std::pair<T, U> &p) {
os << "{";
print(p.first);
os << ", ";
print(p.second);
os << "}";
}
template <typename... Types>
void print(const std::tuple<Types...> &t) {
print_tuple(t, std::make_index_sequence<sizeof...(Types)>());
}
template <class Tuple, std::size_t... Idxes>
void print_tuple(const Tuple &t, std::index_sequence<Idxes...>) {
os << "{";
((os << (Idxes == 0 ? "" : ", "), print(std::get<Idxes>(t))), ...);
os << "}";
}
} // namespace debug
} // namespace algorithm
#else
#define debug(...) static_cast<void>(0)
#endif
#line 11 "verify/aoj-ITP1_1_A-popcount.test.cpp"
constexpr int naive_popcount(uint64_t bit) {
int res = 0;
while(bit) {
res++;
bit &= bit - 1;
}
return res;
}
int main() {
constexpr int t = 10000;
std::random_device seed;
std::mt19937_64 rng(seed());
static_assert(algorithm::popcount32(std::numeric_limits<uint32_t>::min()) == 0);
static_assert(algorithm::popcount32(std::numeric_limits<uint32_t>::max()) == 32);
static_assert(algorithm::popcount64(std::numeric_limits<uint64_t>::min()) == 0);
static_assert(algorithm::popcount64(std::numeric_limits<uint64_t>::max()) == 64);
std::uniform_int_distribution<uint32_t> uniform(std::numeric_limits<uint32_t>::min(),
std::numeric_limits<uint32_t>::max());
for(int i = 0; i < t; ++i) {
uint32_t arg = uniform(rng);
auto target = algorithm::popcount32(arg);
auto want = naive_popcount(arg);
debug(i, std::bitset<32>(arg), target, want);
assert(target == want);
}
std::uniform_int_distribution<uint64_t> uniform2(std::numeric_limits<uint64_t>::min(),
std::numeric_limits<uint64_t>::max());
for(int i = 0; i < t; ++i) {
uint64_t arg = uniform2(rng);
auto target = algorithm::popcount64(arg);
auto want = naive_popcount(arg);
debug(i, std::bitset<64>(arg), arg, target, want);
assert(target == want);
}
std::cout << "Hello World" << std::endl;
}