Population Count (popcount)
(algorithm/Others/popcount.hpp)

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Include: #include "algorithm/Others/popcount.hpp"

概要

与えられた非負整数値を2進数表記した際に1となっているビットの数を高速に求める． “popcount” は “population count” の略．

static_assert(algorithm::popcount32(5) == 2);
static_assert(algorithm::popcount64((1LL << 60) - 1) == 60);

参考文献

1. “Hamming weight”. Wikipedia. https://en.wikipedia.org/wiki/Hamming_weight.
2. zawawahoge. “ビットカウントする高速アルゴリズムをPythonで実装しながら詳しく解説してみる”. Qiita. https://qiita.com/zawawahoge/items/8bbd4c2319e7f7746266.

問題

• “D - Popcount and XOR”. AtCoder Beginner Contest 347. AtCoder. https://atcoder.jp/contests/abc347/tasks/abc347_d.

Verified with

• verify/aoj-ITP1_1_A-popcount.test.cpp

Code

#ifndef ALGORITHM_POPCOUNT_HPP
#define ALGORITHM_POPCOUNT_HPP 1

#include <cstdint>

namespace algorithm {

constexpr int popcount32(uint32_t bit) {
    bit -= (bit >> 1) & 0x5555'5555U;
    bit = (bit & 0x3333'3333U) + ((bit >> 2) & 0x3333'3333U);
    bit = (bit + (bit >> 4)) & 0x0f0f'0f0fU;
    bit += bit >> 8;
    bit += bit >> 16;
    return bit & 0x0000'003fU;
}

constexpr int popcount64(uint64_t bit) {
    bit -= (bit >> 1) & 0x5555'5555'5555'5555ULL;
    bit = (bit & 0x3333'3333'3333'3333ULL) + ((bit >> 2) & 0x3333'3333'3333'3333ULL);
    bit = (bit + (bit >> 4)) & 0x0f0f'0f0f'0f0f'0f0fULL;
    bit += bit >> 8;
    bit += bit >> 16;
    bit += bit >> 32;
    return bit & 0x0000'0000'0000'007fULL;
}

}  // namespace algorithm

#endif

#line 1 "algorithm/Others/popcount.hpp"



#include <cstdint>

namespace algorithm {

constexpr int popcount32(uint32_t bit) {
    bit -= (bit >> 1) & 0x5555'5555U;
    bit = (bit & 0x3333'3333U) + ((bit >> 2) & 0x3333'3333U);
    bit = (bit + (bit >> 4)) & 0x0f0f'0f0fU;
    bit += bit >> 8;
    bit += bit >> 16;
    return bit & 0x0000'003fU;
}

constexpr int popcount64(uint64_t bit) {
    bit -= (bit >> 1) & 0x5555'5555'5555'5555ULL;
    bit = (bit & 0x3333'3333'3333'3333ULL) + ((bit >> 2) & 0x3333'3333'3333'3333ULL);
    bit = (bit + (bit >> 4)) & 0x0f0f'0f0f'0f0f'0f0fULL;
    bit += bit >> 8;
    bit += bit >> 16;
    bit += bit >> 32;
    return bit & 0x0000'0000'0000'007fULL;
}

}  // namespace algorithm

Back to top page