This documentation is automatically generated by online-judge-tools/verification-helper
#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;
}