整数のセットビットをカウントするC/C++プログラム

セットビットのカウントとは

セットビットのカウントとは、与えられた整数を2進数で表現したときに含まれる「1」の個数を数えることを意味します。これを実現する方法はいくつかありますが、ここでは整数のバイナリ表現を対象に、各ビットを走査して1の数を数える基本的な手法を紹介します。

たとえば、入力として17を与えた場合、17の2進表現は「10001」であり、1が2つ含まれるため、出力は2になります。

入力：正の整数を入力してください：6
出力：2

アルゴリズムの解説

6の2進表現は「110」であり、セットビット（1になっているビット）は2つ存在します。

この反復的なアプローチでは、1ビットにつき1回の反復が必要になります。数値のすべてのビットを順番に調べていき、セットされているビットがなくなった時点で反復を終了します。最悪の場合、最上位ビットだけが立っている32ビットの数値では、32回のループが発生します。この解決策は最もシンプルで、1のビットがまばらに存在し、下位ビット側に集中している場合に特に有効です。

処理の流れ

• カウンタ変数を0で初期化します。
• 数値が0になるまで、以下の操作を繰り返します。
• 「n & 1」で最下位ビットが1かどうかを判定し、1であればカウンタを増加させます。
• 「n >>= 1」で数値を1ビット右シフトし、次のビットへ移動します。

サンプルコード

#include <stdio.h>

int main(void) {
    unsigned int n = 34;
    int c;

    for (c = 0; n; n >>= 1) {
        c += n & 1;
    }

    printf("%d\n", c);
    return 0;
}

このプログラムでは、n = 34（2進表現は「100010」）としているため、実行すると「2」が出力されます。変数cは1の個数を格納するカウンタであり、ループのたびに最下位ビットを判定しながら右シフトを繰り返すことで、すべてのビットを効率的に走査できます。