This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub toyama1710/cpp_library
#define PROBLEM \ "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" #include <bits/stdc++.h> #include "../../bit/clz.hpp" #include "../../bit/ctz.hpp" #include "../../bit/lsb.hpp" #include "../../bit/msb.hpp" #include "../../bit/pop_count.hpp" #include "../../util/xorshift.hpp" #define _overload(_1, _2, _3, _4, name, ...) name #define _rep1(Itr, N) _rep3(Itr, 0, N, 1) #define _rep2(Itr, a, b) _rep3(Itr, a, b, 1) #define _rep3(Itr, a, b, step) for (i64 Itr = a; Itr < b; Itr += step) #define repeat(...) _overload(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__) #define rep(...) repeat(__VA_ARGS__) #define ALL(X) begin(X), end(X) using namespace std; using i64 = int64_t; using u64 = uint64_t; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); xorshift64 rnd64(1); xorshift32 rnd32(1); rep(i, 1 << 25) { u64 bit64 = rnd64(); unsigned bit32 = rnd32(); assert(ctz32_(bit32) == __builtin_ctz(bit32)); assert(ctz64(bit64) == __builtin_ctzll(bit64)); assert(clz32_(bit32) == __builtin_clz(bit32)); assert(clz64(bit64) == __builtin_clzll(bit64)); assert(popcnt32_(bit32) == __builtin_popcount(bit32)); assert(popcnt64_(bit64) == __builtin_popcountll(bit64)); assert(msb32_(bit32) == 1u << (31 - __builtin_clz(bit32))); assert(msb64_(bit64) == 1ull << (63 - __builtin_clzll(bit64))); } rep(i, 32) { assert(msb32_(rnd32() | (1u << i)) >= 1u << i); assert(msb64_(rnd64() | (1ull << i)) >= 1ull << i); assert(ctz32_(1u << i) == i); assert(ctz32_(3u << i) == i); assert(ctz32_(21u << i) == i); assert(clz32_(1u << i) == 31 - i); } rep(i, 64) { assert(msb64_(rnd32() | (1ull << i)) >= 1ull << i); assert(msb64_(rnd64() | (1ull << i)) >= 1ull << i); assert(ctz64_(1ull << i) == i); assert(ctz64_(3ull << i) == i); assert(ctz64_(21ull << i) == i); assert(clz64_(1ull << i) == 63 - i); } cout << "Hello World" << endl; return 0; }
#line 1 "test/aoj/bits.test.cpp" #define PROBLEM \ "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" #include <bits/stdc++.h> #line 1 "bit/clz.hpp" #line 5 "bit/clz.hpp" inline int clz32_(uint32_t bit) { static const int table[] = { 31, 30, 29, 25, 28, 20, 24, 15, 27, 17, 19, 10, 23, 8, 14, 5, 0, 26, 21, 16, 18, 11, 9, 6, 1, 22, 12, 7, 2, 13, 3, 4, }; static const uint32_t de_bruijn = 0x04653adf; bit |= bit >> 1; bit |= bit >> 2; bit |= bit >> 4; bit |= bit >> 8; bit |= bit >> 16; bit ^= bit >> 1; return table[(bit * de_bruijn) >> 27]; }; inline int clz32(uint32_t bit) { if (bit == 0) return 32; #ifdef __has_builtin return __builtin_clz(bit); #else return clz32_(bit); #endif }; inline int clz64_(uint64_t bit) { static const int table[] = { 63, 62, 61, 56, 60, 50, 55, 44, 59, 38, 49, 35, 54, 29, 43, 23, 58, 46, 37, 25, 48, 17, 34, 15, 53, 32, 28, 9, 42, 13, 22, 6, 0, 57, 51, 45, 39, 36, 30, 24, 47, 26, 18, 16, 33, 10, 14, 7, 1, 52, 40, 31, 27, 19, 11, 8, 2, 41, 20, 12, 3, 21, 4, 5, }; static const uint64_t de_bruijn = 0x0218a392cd3d5dbfull; bit |= bit >> 1; bit |= bit >> 2; bit |= bit >> 4; bit |= bit >> 8; bit |= bit >> 16; bit |= bit >> 32; bit ^= bit >> 1; return table[(bit * de_bruijn) >> 58]; }; inline int clz64(uint64_t bit) { if (bit == 0) return 64; #ifdef __has_builtin return __builtin_clzll(bit); #else return clz64_(bit); #endif }; #line 1 "bit/ctz.hpp" #line 5 "bit/ctz.hpp" inline int ctz32_(uint32_t bit) { static const int table[] = { 0, 1, 2, 6, 3, 11, 7, 16, 4, 14, 12, 21, 8, 23, 17, 26, 31, 5, 10, 15, 13, 20, 22, 25, 30, 9, 19, 24, 29, 18, 28, 27, }; static const uint32_t de_bruijn = 0x04653adf; bit &= ~bit + 1; return table[(bit * de_bruijn) >> 27]; }; inline int ctz32(uint32_t bit) { if (bit == 0) return 32; #ifdef __has_builtin return __builtin_ctz(bit); #else return ctz32_(bit); #endif }; inline int ctz64_(uint64_t bit) { static const int table[] = { 0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26, 38, 15, 46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, 33, 39, 16, 37, 45, 47, 30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43, 51, 60, 42, 59, 58, }; static const uint64_t de_bruijn = 0x0218a392cd3d5dbfull; bit &= ~bit + 1; return table[(bit * de_bruijn) >> 58]; }; inline int ctz64(uint64_t bit) { if (bit == 0) return 64; #ifdef __has_builtin return __builtin_ctzll(bit); #else return ctz64_(bit); #endif }; #line 1 "bit/lsb.hpp" #line 5 "bit/lsb.hpp" inline uint64_t lsb32(uint32_t bits) { return bits & (~bits + 1); }; inline uint64_t lsb64(uint64_t bits) { return bits & (~bits + 1); }; #line 1 "bit/msb.hpp" #line 5 "bit/msb.hpp" inline uint32_t msb32_(uint32_t bit) { bit |= bit >> 1; bit |= bit >> 2; bit |= bit >> 4; bit |= bit >> 8; bit |= bit >> 16; return bit ^ (bit >> 1); }; inline uint32_t msb32(uint32_t x) { if (x == 0) return 0; #ifdef __has_builtin return 1u << (31 - __builtin_clz(x)); #else return msb32_(x); #endif }; inline uint64_t msb64_(uint64_t bit) { bit |= bit >> 1; bit |= bit >> 2; bit |= bit >> 4; bit |= bit >> 8; bit |= bit >> 16; bit |= bit >> 32; return bit ^ (bit >> 1); }; inline uint64_t msb64(uint64_t x) { if (x == 0) return 0; #ifdef __has_builtin return 1ull << (63 - __builtin_clzll(x)); #else return msb64_(x); #endif }; #line 1 "bit/pop_count.hpp" #line 5 "bit/pop_count.hpp" inline int popcnt64_(uint64_t bits) { bits = (bits & 0x5555555555555555) + (bits >> 1 & 0x5555555555555555); bits = (bits & 0x3333333333333333) + (bits >> 2 & 0x3333333333333333); bits = (bits & 0x0f0f0f0f0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f0f0f0f0f); bits = (bits & 0x00ff00ff00ff00ff) + (bits >> 8 & 0x00ff00ff00ff00ff); bits = (bits & 0x0000ffff0000ffff) + (bits >> 16 & 0x0000ffff0000ffff); bits = (bits & 0x00000000ffffffff) + (bits >> 32 & 0x00000000ffffffff); return bits; }; inline int popcnt64(uint64_t bits) { #ifdef __has_builtin return __builtin_popcountll(bits); #else return popcnt64_(bits); #endif }; inline int popcnt32_(uint32_t bits) { bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555); bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333); bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f); bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff); bits = (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff); return bits; }; inline int popcnt32(uint32_t bits) { #ifdef __has_builtin return __builtin_popcount(bits); #else return popcnt32_(bits); #endif }; #line 1 "util/xorshift.hpp" #line 5 "util/xorshift.hpp" struct xorshift32 { uint32_t seed; xorshift32(uint32_t seed = 1710) : seed(seed){}; void set_seed(uint32_t s) { seed = s; }; uint32_t gen() { seed = seed ^ (seed << 13); seed = seed ^ (seed >> 17); seed = seed ^ (seed << 5); return seed; }; uint32_t operator()() { return gen(); }; }; struct xorshift64 { uint64_t seed; xorshift64(uint64_t seed = 1710) : seed(seed){}; void set_seed(uint64_t s) { seed = s; }; uint64_t gen() { seed = seed ^ (seed << 13); seed = seed ^ (seed >> 7); seed = seed ^ (seed << 17); return seed; }; uint64_t operator()() { return gen(); }; }; #line 12 "test/aoj/bits.test.cpp" #define _overload(_1, _2, _3, _4, name, ...) name #define _rep1(Itr, N) _rep3(Itr, 0, N, 1) #define _rep2(Itr, a, b) _rep3(Itr, a, b, 1) #define _rep3(Itr, a, b, step) for (i64 Itr = a; Itr < b; Itr += step) #define repeat(...) _overload(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__) #define rep(...) repeat(__VA_ARGS__) #define ALL(X) begin(X), end(X) using namespace std; using i64 = int64_t; using u64 = uint64_t; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); xorshift64 rnd64(1); xorshift32 rnd32(1); rep(i, 1 << 25) { u64 bit64 = rnd64(); unsigned bit32 = rnd32(); assert(ctz32_(bit32) == __builtin_ctz(bit32)); assert(ctz64(bit64) == __builtin_ctzll(bit64)); assert(clz32_(bit32) == __builtin_clz(bit32)); assert(clz64(bit64) == __builtin_clzll(bit64)); assert(popcnt32_(bit32) == __builtin_popcount(bit32)); assert(popcnt64_(bit64) == __builtin_popcountll(bit64)); assert(msb32_(bit32) == 1u << (31 - __builtin_clz(bit32))); assert(msb64_(bit64) == 1ull << (63 - __builtin_clzll(bit64))); } rep(i, 32) { assert(msb32_(rnd32() | (1u << i)) >= 1u << i); assert(msb64_(rnd64() | (1ull << i)) >= 1ull << i); assert(ctz32_(1u << i) == i); assert(ctz32_(3u << i) == i); assert(ctz32_(21u << i) == i); assert(clz32_(1u << i) == 31 - i); } rep(i, 64) { assert(msb64_(rnd32() | (1ull << i)) >= 1ull << i); assert(msb64_(rnd64() | (1ull << i)) >= 1ull << i); assert(ctz64_(1ull << i) == i); assert(ctz64_(3ull << i) == i); assert(ctz64_(21ull << i) == i); assert(clz64_(1ull << i) == 63 - i); } cout << "Hello World" << endl; return 0; }