C++で32ビット符号なし2進数のセットビット（1の個数）を数える方法

32ビットの符号なし2進数が与えられたとき、その中に含まれる「セットビット」、つまり「1」が何個あるかを数えるのが本記事のテーマです。

問題の例

入力：

N = 00000000000000100111

出力：

4

説明： 与えられた符号なし2進数に含まれるセットビット（1）の合計は4個です。したがって、答えとして「4」を返します。

解き方のアプローチ

この問題は、与えられた32ビットの符号なし2進数の中に「1」がいくつ現れるかを数えるものです。

C++では、ビット数を数えるための便利な手段が標準およびコンパイラ拡張として用意されています。代表的な方法は次の2つです。

• std::bitset の count() メンバ関数： 数値を bitset<32> に変換し、count() を呼び出すだけでセットビットの個数が取得できます。標準ライブラリのみで動作するため、環境を選ばないのが利点です。
• __builtin_popcount(n) 関数： GCC / Clang で使える組み込み関数で、引数 n に含まれる「1」の個数を返します。ハードウェア命令を利用するため非常に高速です。

処理の流れは以下のとおりです。

• 2進数 N を入力として受け取ります。
• 関数 count1Bits(uint32_t n) が32ビットの符号なし整数を受け取り、その中の「1」の個数を返します。
• 内部では bitset の count() または __builtin_popcount(n) を呼び出して結果を取得します。

実装例

#include <bits/stdc++.h>
using namespace std;

int count1Bits(uint32_t n) {
    return bitset<32>(n).count();
}

int main() {
    // 2進数リテラル（0b接頭辞）で 00000000000000100111 を表現
    uint32_t N = 0b00000000000000100111;
    cout << count1Bits(N) << endl;
    return 0;
}

上記のコードを実行すると、次の出力が得られます。

出力

4

与えられた数には「1」が4個含まれているため、出力は「4」になります。

補足：__builtin_popcount を使う場合

GCC系コンパイラを使用している場合は、次のように書くこともできます。

int count1Bits(uint32_t n) {
    return __builtin_popcount(n);
}

C++20以降では、標準ライブラリの std::popcount（ヘッダー <bit>）も利用でき、より移植性の高いコードを書けます。用途や環境に応じて最適な方法を選びましょう。