ビット数のカウント

概要

整数をビットで表現したときに立っているビットを数える．__builtin_popcount でもいいが log 時間がかかる．匿名先生によると 16 ビット分前計算するのが最善らしい．

実装

template <typename T>
inline int pop_count(T n) {
    static int dp[0xFFFF];
    if (dp[1] == 0) {
        for (int i = 0; i < 0xFFFF; i++) dp[i] = dp[i / 2] + i % 2;
    }
    static_assert(std::is_integral<T>(), "T must be integer");
    constexpr int sect = sizeof(T) / 2;
    int res = 0;
    for (int i = 0; i < sect; ++i) {
        res += dp[n & 0xFFFF];
        n >>= 16;
    }
    return res;
}