test/own/Random_popcount.test.cpp

• View this file on GitHub
• Last update: 2021-02-04 23:15:35+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A

Depends on

• src/Random.hpp
• src/popcount.hpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

#include "../../src/Random.hpp"
#include "../../src/popcount.hpp"

#include <cassert>
#include <iostream>
#include <iomanip>

using namespace std;
using lint = long long;

struct init {
    init() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
    }
} init_;

inline int test(lint x) {
    long long count = 0;
    __asm__ volatile("POPCNT %1, %0;"
    :"=r"(count)
    :"r"(x)
    :
    );
    return count;
}

int main() {

    // meaning of magic numbers
//    cout << hex;
//    cout << 0b0101010101010101010101010101010101010101010101010101010101010101 << '\n';
//    cout << 0b0011001100110011001100110011001100110011001100110011001100110011 << '\n';
//    cout << 0b0000111100001111000011110000111100001111000011110000111100001111 << '\n';
//    cout << 0b0000000011111111000000001111111100000000111111110000000011111111 << '\n';
//    cout << 0b0000000000000000111111111111111100000000000000001111111111111111 << '\n';
//    cout << 0b0000000000000000000000000000000011111111111111111111111111111111 << '\n';

    // random test
    Random ran;
    for (int i = 0; i < 100000000; i++) {
        lint n = ran(0, numeric_limits<lint>::max());
        assert(test(n) == popcount(n));
    }

    cout << "Hello World\n";

    return 0;
}

#line 1 "test/own/Random_popcount.test.cpp"

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

#line 2 "src/Random.hpp"

#include <cassert>
#include <algorithm>
#include <random>
#include <chrono>
#include <vector>
#include <unordered_map>

using namespace std;
using lint = long long;

struct Random {
    unsigned int seed;
    mt19937 mt;
    explicit Random(unsigned int s = chrono::steady_clock::now().time_since_epoch().count()) : seed(s), mt(seed) {}

    lint operator()(const lint &rand_min, const lint &rand_max) {
        uniform_int_distribution <lint> dist(rand_min, rand_max);
        return dist(mt);
    }
    lint operator()(const lint &rand_max) { return (*this)(0LL, rand_max); }

    [[nodiscard]] vector<lint> uniq_vec(const int &sz, const lint &rand_min, lint rand_max) {

        vector<lint> res(sz);
        unordered_map <lint, lint> memo;
        for (int i = 0; i < sz; i++, rand_max--) {

            lint rand_val = (*this)(rand_min, rand_max);

            // If rand_max hasn't been replaced yet, fill it with rand_max
            if (memo.find(rand_max) == memo.end()) memo[rand_max] = rand_max;

            auto val_itr = memo.find(rand_val);
            if (val_itr == memo.end()) { // replace rand_val with rand_max
                memo[rand_val] = memo[rand_max];
            }
            else { // If rand_val has already been replaced
                rand_val = val_itr->second;
                val_itr->second = memo[rand_max];
            }

            res[i] = rand_val;
        }
        return res;
    }
    template<class Ite>
    void shuf(Ite first, Ite last) { shuffle(first, last, mt); }

    string random_string(const int &max_len, const string list = "abcdefghijklmnopqrstuvwxyz") {
        assert(!list.empty());
        int size = (int)(*this)(1, max_len);
        string res(size, 0);
        generate(res.begin(), res.end(), [this, &list]() { return list[(*this)((int)list.size() - 1)]; });
        return res;
    }

};
#line 2 "src/popcount.hpp"

using lint = long long;

inline int popcount(lint n) {
    n = (n & 0x5555555555555555) + (n >> 1 & 0x5555555555555555);
    n = (n & 0x3333333333333333) + (n >> 2 & 0x3333333333333333);
    n = (n & 0x0f0f0f0f0f0f0f0f) + (n >> 4 & 0x0f0f0f0f0f0f0f0f);
    n = (n & 0x00ff00ff00ff00ff) + (n >> 8 & 0x00ff00ff00ff00ff);
    n = (n & 0x0000ffff0000ffff) + (n >> 16 & 0x0000ffff0000ffff);
    n = (n & 0x00000000ffffffff) + (n >> 32 & 0x00000000ffffffff);
    return n;
}
#line 6 "test/own/Random_popcount.test.cpp"

#line 8 "test/own/Random_popcount.test.cpp"
#include <iostream>
#include <iomanip>

using namespace std;
using lint = long long;

struct init {
    init() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
    }
} init_;

inline int test(lint x) {
    long long count = 0;
    __asm__ volatile("POPCNT %1, %0;"
    :"=r"(count)
    :"r"(x)
    :
    );
    return count;
}

int main() {

    // meaning of magic numbers
//    cout << hex;
//    cout << 0b0101010101010101010101010101010101010101010101010101010101010101 << '\n';
//    cout << 0b0011001100110011001100110011001100110011001100110011001100110011 << '\n';
//    cout << 0b0000111100001111000011110000111100001111000011110000111100001111 << '\n';
//    cout << 0b0000000011111111000000001111111100000000111111110000000011111111 << '\n';
//    cout << 0b0000000000000000111111111111111100000000000000001111111111111111 << '\n';
//    cout << 0b0000000000000000000000000000000011111111111111111111111111111111 << '\n';

    // random test
    Random ran;
    for (int i = 0; i < 100000000; i++) {
        lint n = ran(0, numeric_limits<lint>::max());
        assert(test(n) == popcount(n));
    }

    cout << "Hello World\n";

    return 0;
}

Back to top page