cpp_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub toyama1710/cpp_library

:heavy_check_mark: test/aoj/bits.test.cpp

Depends on

Code

#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;
}
Back to top page