misc/test/bit_operation.test.cpp

• View this file on GitHub
• Last update: 2025-12-31 07:11:44+09:00
• Problem: https://judge.yosupo.jp/problem/aplusb

Depends on

• Bit Ceil (misc/bit_ceil.hpp)
• Countl Zero (misc/countl_zero.hpp)
• Countr Zero (misc/countr_zero.hpp)
• Lowbit (misc/lowbit.hpp)
• Popcount (misc/popcount.hpp)
• Topbit (misc/topbit.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#include <array>
#include <cassert>
#include <iostream>

#include "../bit_ceil.hpp"
#include "../countl_zero.hpp"
#include "../countr_zero.hpp"
#include "../lowbit.hpp"
#include "../popcount.hpp"
#include "../topbit.hpp"

void test1_bit_ceil() {
    const std::array<int, 8> input = {0, 1, 2, 3, 4, 5, 6, 7};
    const std::array<int, 8> expected = {1, 1, 2, 4, 4, 8, 8, 8};
    for (int i = 0; i < 8; i++) {
        assert(bit_ceil(input[i]) == expected[i]);
    }
}

void test2_countl_zero() {
    using u32 = unsigned int;
    const std::array<u32, 8> input = {0, 1, 2, 3, 4, 5, 6, 7};
    const std::array<int, 8> expected = {32, 31, 30, 30, 29, 29, 29, 29};
    for (int i = 0; i < 8; i++) {
        assert(countl_zero(input[i]) == expected[i]);
    }
}

void test3_countr_zero() {
    using u32 = unsigned int;
    const std::array<u32, 8> input = {0, 1, 2, 3, 4, 5, 6, 7};
    const std::array<int, 8> expected = {32, 0, 1, 0, 2, 0, 1, 0};
    for (int i = 0; i < 8; i++) {
        assert(countr_zero(input[i]) == expected[i]);
    }
}

void test4_popcount() {
    const std::array<int, 8> input = {0, 1, 2, 3, 4, 5, 6, 7};
    const std::array<int, 8> expected = {0, 1, 1, 2, 1, 2, 2, 3};
    for (int i = 0; i < 8; i++) {
        assert(popcount(input[i]) == expected[i]);
    }
}

void test5_topbit() {
    const std::array<int, 8> input = {0, 1, 2, 3, 4, 5, 6, 7};
    const std::array<int, 8> expected = {-1, 0, 1, 1, 2, 2, 2, 2};
    for (int i = 0; i < 8; i++) {
        assert(topbit(input[i]) == expected[i]);
    }
}

void test6_lowbit() {
    const std::array<int, 8> input = {0, 1, 2, 3, 4, 5, 6, 7};
    const std::array<int, 8> expected = {-1, 0, 1, 0, 2, 0, 1, 0};
    for (int i = 0; i < 8; i++) {
        assert(lowbit(input[i]) == expected[i]);
    }
}

int main() {
    test1_bit_ceil();
    test2_countl_zero();
    test3_countr_zero();
    test4_popcount();
    test5_topbit();
    test6_lowbit();
    int a, b;
    std::cin >> a >> b;
    std::cout << a + b << '\n';
    return 0;
}

#line 1 "misc/test/bit_operation.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#include <array>
#include <cassert>
#include <iostream>

#line 2 "misc/bit_ceil.hpp"

#line 4 "misc/bit_ceil.hpp"

#if __cplusplus >= 202002L
#include <bit>
#endif

// bit_ceil
// (0, 1, 2, 3, 4) -> (1, 1, 2, 4, 4)
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
unsigned int bit_ceil(unsigned int x) {
    unsigned int p = 1;
    while (p < x) p *= 2;
    return p;
}
unsigned long long int bit_ceil(unsigned long long int x) {
    unsigned long long int p = 1;
    while (p < x) p *= 2;
    return p;
}
#endif
int bit_ceil(int x) {
    assert(x >= 0);
    return bit_ceil((unsigned int)(x));
}
long long int bit_ceil(long long int x) {
    assert(x >= 0);
    return bit_ceil((unsigned long long int)(x));
}
#line 2 "misc/countl_zero.hpp"

#if __cplusplus >= 202002L
#include <bit>
#endif

// countl_zero
// (000, 001, 010, 011, 100) -> (32, 31, 30, 30, 29)
#if __cplusplus >= 202002L
using std::countl_zero;
#else
int countl_zero(unsigned int x) {
    return x == 0 ? 32 : __builtin_clz(x);
}
int countl_zero(unsigned long long int x) {
    return x == 0 ? 64 : __builtin_clzll(x);
}
#endif
int countl_zero(int x) { return countl_zero((unsigned int)(x)); }
int countl_zero(long long int x) {
    return countl_zero((unsigned long long int)(x));
}
#line 2 "misc/countr_zero.hpp"

#if __cplusplus >= 202002L
#include <bit>
#endif

// countr_zero
// (000, 001, 010, 011, 100) -> (32, 0, 1, 0, 2)
#if __cplusplus >= 202002L
using std::countr_zero;
#else
int countr_zero(unsigned int x) {
    return x == 0 ? 32 : __builtin_ctz(x);
}
int countr_zero(unsigned long long int x) {
    return x == 0 ? 64 : __builtin_ctzll(x);
}
#endif
int countr_zero(int x) { return countr_zero((unsigned int)(x)); }
int countr_zero(long long int x) {
    return countr_zero((unsigned long long int)(x));
}
#line 2 "misc/lowbit.hpp"

#line 4 "misc/lowbit.hpp"

// lowbit
// (000, 001, 010, 011, 100) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : countr_zero(x)); }
int lowbit(unsigned int x) { return (x == 0 ? -1 : countr_zero(x)); }
int lowbit(long long int x) { return (x == 0 ? -1 : countr_zero(x)); }
int lowbit(unsigned long long int x) { return (x == 0 ? -1 : countr_zero(x)); }
#line 2 "misc/popcount.hpp"

#if __cplusplus >= 202002L
#include <bit>
#endif

// popcount
// (000, 001, 010, 011, 100) -> (0, 1, 1, 2, 1)
#if __cplusplus >= 202002L
using std::popcount;
#else
int popcount(unsigned int x) { return __builtin_popcount(x); }
int popcount(unsigned long long int x) { return __builtin_popcountll(x); }
#endif
int popcount(int x) { return popcount((unsigned int)(x)); }
int popcount(long long int x) { return popcount((unsigned long long int)(x)); }
#line 2 "misc/topbit.hpp"

#line 4 "misc/topbit.hpp"

// topbit
// (000, 001, 010, 011, 100) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return 31 - countl_zero(x); }
int topbit(unsigned int x) { return 31 - countl_zero(x); }
int topbit(long long int x) { return 63 - countl_zero(x); }
int topbit(unsigned long long int x) { return 63 - countl_zero(x); }
#line 13 "misc/test/bit_operation.test.cpp"

void test1_bit_ceil() {
    const std::array<int, 8> input = {0, 1, 2, 3, 4, 5, 6, 7};
    const std::array<int, 8> expected = {1, 1, 2, 4, 4, 8, 8, 8};
    for (int i = 0; i < 8; i++) {
        assert(bit_ceil(input[i]) == expected[i]);
    }
}

void test2_countl_zero() {
    using u32 = unsigned int;
    const std::array<u32, 8> input = {0, 1, 2, 3, 4, 5, 6, 7};
    const std::array<int, 8> expected = {32, 31, 30, 30, 29, 29, 29, 29};
    for (int i = 0; i < 8; i++) {
        assert(countl_zero(input[i]) == expected[i]);
    }
}

void test3_countr_zero() {
    using u32 = unsigned int;
    const std::array<u32, 8> input = {0, 1, 2, 3, 4, 5, 6, 7};
    const std::array<int, 8> expected = {32, 0, 1, 0, 2, 0, 1, 0};
    for (int i = 0; i < 8; i++) {
        assert(countr_zero(input[i]) == expected[i]);
    }
}

void test4_popcount() {
    const std::array<int, 8> input = {0, 1, 2, 3, 4, 5, 6, 7};
    const std::array<int, 8> expected = {0, 1, 1, 2, 1, 2, 2, 3};
    for (int i = 0; i < 8; i++) {
        assert(popcount(input[i]) == expected[i]);
    }
}

void test5_topbit() {
    const std::array<int, 8> input = {0, 1, 2, 3, 4, 5, 6, 7};
    const std::array<int, 8> expected = {-1, 0, 1, 1, 2, 2, 2, 2};
    for (int i = 0; i < 8; i++) {
        assert(topbit(input[i]) == expected[i]);
    }
}

void test6_lowbit() {
    const std::array<int, 8> input = {0, 1, 2, 3, 4, 5, 6, 7};
    const std::array<int, 8> expected = {-1, 0, 1, 0, 2, 0, 1, 0};
    for (int i = 0; i < 8; i++) {
        assert(lowbit(input[i]) == expected[i]);
    }
}

int main() {
    test1_bit_ceil();
    test2_countl_zero();
    test3_countr_zero();
    test4_popcount();
    test5_topbit();
    test6_lowbit();
    int a, b;
    std::cin >> a >> b;
    std::cout << a + b << '\n';
    return 0;
}

Back to top page