整数のセットビット（1のビット）を数えるC/C++プログラム

本記事では、整数を2進数で表したときに「1」となっているビット（セットビット）の個数を数える方法を解説します。セットビットとは、数値のバイナリ表現における1のビットのことです。たとえば、13は2進数で「1101」と表されるため、セットビットは3個になります。

この問題を解くには、数値を右シフトしながら最下位ビット（LSb）を調べ、1であればカウントを増やします。これを数値が0になるまで繰り返すことで、セットビットの総数を求められます。

アルゴリズム

countSetBit()

begin
    count := 0
    while n is not 0, do
        if LSb of n is set, then
            count := count + 1
        end if
        n := n after shifting 1 bit to right
    done
    return count
end

実装例

以下は、CおよびC++で動作する実装例です。ビット演算子 & で最下位ビットを判定し、>> で1ビットずつ右にずらしていきます。

#include<iostream>
using namespace std;
int count_set_bit(int n) {
    int count = 0;
    while(n != 0) {
        if(n & 1 == 1) {
            count++;
        }
        n = n >> 1; //右へ1ビットシフト
    }
    return count;
}
int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    cout << "Number of set bits: " << count_set_bit(n);
}

出力例

Enter a number: 29
Number of set bits: 4

入力した値が29の場合、2進数では「11101」となるため、セットビットは4個と正しく出力されます。

計算量について

この手法では、数値が0になるまで1ビットずつ確認するため、時間計算量はビット長に比例するO(log n)となります。より高速に処理したい場合は、GCC/Clangで利用できる組み込み関数 __builtin_popcount(n) を使う方法や、Brian Kernighanのアルゴリズム（最も右にある1のビットを順に消去していく手法）を使うと、セットビットの数だけしかループが回らないため効率的です。