test/unittest/bit.test.cpp

• View this file on GitHub
• Last update: 2026-10-13 06:02:01+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A

Depends on

• ビット演算 (src/base/bit.hpp)

Code

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

// bit.hpp の関数を愚直な実装とランダムに比較する
// 問題の入力は使わず、すべて一致したら Hello World を出力する

#include <iostream>
#include <random>
#include <string>

#include "../../src/base/bit.hpp"

bool ok = true;

void check(bool cond, const char* what) {
    if (!cond) {
        if (ok) std::cerr << "failed: " << what << std::endl;
        ok = false;
    }
}

int main() {
    std::mt19937_64 rng(314);

    for (int rep = 0; rep < 100000 && ok; rep++) {
        // 0 以上の long long (ビット数もばらつかせる)
        int width = rng() % 63 + 1;
        long long a = (long long)(rng() >> (64 - width));

        int pc = 0, clz = 0, ctz = 0;
        for (int i = 0; i < 63; i++) pc += a >> i & 1;
        for (int i = 63; i >= 0 && !(a >> i & 1); i--) clz++;
        for (int i = 0; i < 64 && !(a >> i & 1); i++) ctz++;
        check(popcount(a) == pc, "popcount");
        if (a > 0) {
            check(countl_zero(a) == clz, "countl_zero");
            check(countr_zero(a) == ctz, "countr_zero");
        }

        // btoll: 2 進数の文字列 (上位桁から)
        std::string s;
        for (int i = width - 1; i >= 0; i--) s += (a >> i & 1) ? '1' : '0';
        check(btoll(s) == a, "btoll");
        // 1 を表す文字を指定する
        std::string t = s;
        for (char& c : t) c = (c == '1') ? '#' : '.';
        check(btoll(t, '#') == a, "btoll(s, one)");
    }

    // 決まった値
    check(popcount(0) == 0 && popcount((1LL << 62) - 1) == 62, "popcount 境界");
    check(countl_zero(1) == 63 && countr_zero(1LL << 62) == 62, "countl_zero / countr_zero 境界");
    check(btoll("") == 0 && btoll("0") == 0 && btoll("101") == 5, "btoll 決まった値");

    if (ok) std::cout << "Hello World" << std::endl;
}

#line 1 "test/unittest/bit.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

// bit.hpp の関数を愚直な実装とランダムに比較する
// 問題の入力は使わず、すべて一致したら Hello World を出力する

#include <iostream>
#include <random>
#include <string>

#line 2 "src/base/bit.hpp"

/**
 * @file bit.hpp
 * @brief ビット演算
 */

#include <cassert>
#line 10 "src/base/bit.hpp"
#include <vector>

/**
 * @brief 2進数の文字列をlong longにする
 */
inline long long btoll(std::string s, char one = '1') {
    long long res = 0;
    for (char c : s) {
        res <<= 1;
        if (c == one) ++res;
    }
    return res;
}

#if __cplusplus < 202000L

/**
 * @brief 立っているビットを数える
 * __builtin_popcountll
 */
inline int popcount(long long a) {
    assert(a >= 0);
    return __builtin_popcountll((unsigned long long)a);
}
/**
 * @brief 左から連続した0のビットを数える
 * __builtin_clzll
 */
inline int countl_zero(long long a) {
    assert(a >= 0);
    return __builtin_clzll((unsigned long long)a);
}
/**
 * @brief 右から連続した0のビットを数える
 * __builtin_ctzll
 */
inline int countr_zero(long long a) {
    assert(a >= 0);
    return __builtin_ctzll((unsigned long long)a);
}

#else

#include <bit>
#define BIT_FUNC_EXPAND(func)                      \
    inline constexpr long long func(long long a) { \
        assert(a >= 0);                            \
        return std::func((unsigned long long)a);   \
    }

/**
 * @brief 立っているビットを数える
 */
BIT_FUNC_EXPAND(popcount)
/**
 * @brief 左から連続した0のビットを数える
 */
BIT_FUNC_EXPAND(countl_zero)
/**
 * @brief 左から連続した1のビットを数える
 */
BIT_FUNC_EXPAND(countl_one)
/**
 * @brief 右から連続した0のビットを数える
 */
BIT_FUNC_EXPAND(countr_zero)
/**
 * @brief 右から連続した1のビットを数える
 */
BIT_FUNC_EXPAND(countr_one)
/**
 * @brief 整数値を2の累乗値に切り上げる
 */
BIT_FUNC_EXPAND(bit_ceil)
/**
 * @brief 整数値を2の累乗値に切り下げる
 */
BIT_FUNC_EXPAND(bit_floor)
/**
 * @brief 値を表現するために必要なビット幅を求める
 */
BIT_FUNC_EXPAND(bit_width)

#endif
#line 11 "test/unittest/bit.test.cpp"

bool ok = true;

void check(bool cond, const char* what) {
    if (!cond) {
        if (ok) std::cerr << "failed: " << what << std::endl;
        ok = false;
    }
}

int main() {
    std::mt19937_64 rng(314);

    for (int rep = 0; rep < 100000 && ok; rep++) {
        // 0 以上の long long (ビット数もばらつかせる)
        int width = rng() % 63 + 1;
        long long a = (long long)(rng() >> (64 - width));

        int pc = 0, clz = 0, ctz = 0;
        for (int i = 0; i < 63; i++) pc += a >> i & 1;
        for (int i = 63; i >= 0 && !(a >> i & 1); i--) clz++;
        for (int i = 0; i < 64 && !(a >> i & 1); i++) ctz++;
        check(popcount(a) == pc, "popcount");
        if (a > 0) {
            check(countl_zero(a) == clz, "countl_zero");
            check(countr_zero(a) == ctz, "countr_zero");
        }

        // btoll: 2 進数の文字列 (上位桁から)
        std::string s;
        for (int i = width - 1; i >= 0; i--) s += (a >> i & 1) ? '1' : '0';
        check(btoll(s) == a, "btoll");
        // 1 を表す文字を指定する
        std::string t = s;
        for (char& c : t) c = (c == '1') ? '#' : '.';
        check(btoll(t, '#') == a, "btoll(s, one)");
    }

    // 決まった値
    check(popcount(0) == 0 && popcount((1LL << 62) - 1) == 62, "popcount 境界");
    check(countl_zero(1) == 63 && countr_zero(1LL << 62) == 62, "countl_zero / countr_zero 境界");
    check(btoll("") == 0 && btoll("0") == 0 && btoll("101") == 5, "btoll 決まった値");

    if (ok) std::cout << "Hello World" << std::endl;
}

Back to top page