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

• View this file on GitHub
• Last update: 2026-10-12 19:23:31+09:00
• Include: #include "src/base/bit.hpp"

ビット演算の関数です。引数は long long で、負の値を渡すと assert で落ちます。

btoll("1011");          // 11
btoll("#.#", '#');      // 5 ('#' を 1 とみなす)
popcount(13);           // 3
countl_zero(1);         // 63
countr_zero(8);         // 3

関数

関数	説明	C++17	C++20
btoll(s, one = '1')	2 進数の文字列を long long にする。文字 one を 1、それ以外を 0 とみなす	✓	✓
popcount(a)	立っているビットの数	✓	✓
countl_zero(a)	上位 (64 ビット中) から連続する 0 の数	✓	✓
countr_zero(a)	下位から連続する 0 の数	✓	✓
countl_one(a)	上位から連続する 1 の数		✓
countr_one(a)	下位から連続する 1 の数		✓
bit_ceil(a)	a 以上の最小の 2 の累乗		✓
bit_floor(a)	a 以下の最大の 2 の累乗		✓
bit_width(a)	a を表すのに必要なビット数		✓

C++17 では __builtin_* で実装しているので、countl_zero(0) と countr_zero(0) は未定義動作です。C++20 では <bit> の std:: 版を呼びます。

Verified with

• test/aoj/itp2-10-c.test.cpp
• test/unittest/bit.test.cpp

Code

#pragma once

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

#include <cassert>
#include <string>
#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 2 "src/base/bit.hpp"

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

#include <cassert>
#include <string>
#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

Back to top page