C++で整数のセットビット数をカウントする方法

はじめに

整数値 num が与えられたとき、その数をまず2進数に変換し、さらにセットビット（値が1になっているビット）の総数を求めることを考えます。

セットビットとは

2進数におけるセットビットとは、値が「1」であるビットのことです。整数を2進数で表現すると、0と1の組み合わせになりますが、コンピュータの世界ではこの「1」のことをセットビットと呼びます。

入力・出力の例

入力： int number = 50
出力： セットビットの総数は 3
説明： 50 の2進表現は 110010 です。8桁で表すと先頭に0が2つ追加されて 00110010 となります。したがって、セットビットの総数は 3 です。

入力： int number = 10
出力： セットビットの総数は 2
説明： 10 の2進表現は8桁で 00001010 となり、先頭には4つの0が並びます。したがって、セットビットの総数は 2 です。

プログラムのアプローチ

• 整数型の変数に数値を入力します。
• セットビットの総数を格納するため、unsigned int 型の変数 count を宣言します。
• i = 1 << 7 から始めて、i > 0 の間 i = i / 2 として繰り返す for ループを作成します。
• ループ内で number & i が真であれば 1 を、偽であれば 0 を表示します。これにより8ビットの2進表現が出力されます。
• number が 0 になるまで処理を続ける while ループで、セットビットの総数をカウントします。
• ループ内では count += number & 1 として最下位ビットを加算し、number >>= 1 で右シフトして次のビットへ移動します。
• 最後に count を表示します。

サンプルコード

#include<iostream>
using namespace std;
// 数値のセットビットの総数をカウントする
unsigned int bits(unsigned int number){
    unsigned int count = 0;
    unsigned i;
    // 8ビットの2進表現を表示
    cout<<"8-bit digits of "<<number<<" is: ";
    for (i = 1 << 7; i > 0; i = i / 2){
        (number & i)? cout<<"1": cout<<"0";
    }
    // セットビットの総数を計算
    while (number){
        count += number & 1;
        number >>= 1;
    }
    cout<<"\nCount of total set bits in a number are: "<<count;
}
int main(){
    int number = 50;
    bits(number);
    return 0;
}

実行結果

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

8-bit digits of 50 is: 00110010
Count of total set bits in a number are: 3

補足：もっと簡単にカウントする方法

自前でループを書かなくても、コンパイラ組み込み関数や標準ライブラリを利用できます。

• GCC / Clang では __builtin_popcount(number) を使うことで、1行でセットビット数を取得できます。
• C++20 以降では、ヘッダー <bit> の std::popcount(number) が標準機能として利用可能です。
• また、Brian Kernighan のアルゴリズム（n &= n - 1 を n が 0 になるまで繰り返す）を使うと、セットビットの数だけループが回るため、より効率的にカウントできます。

用途や環境に応じて、これらの手法を選択すると良いでしょう。