【Python】1からnまでの全整数に含まれるセットビットの総数をカウントする方法

正の整数 n が与えられたとき、1 から n までの各数値を2進表現に変換し、それぞれに含まれる「セットビット（値が1になっているビット）」の総数をカウントするプログラムを作成してみましょう。

セットビットとは？

2進数において「1」となっているビットのことをセットビットと呼びます。例えば、数値 3 を2進数で表すと 11 となり、セットビットは 2 個あります。本記事では、1 から n までのすべての整数についてこのセットビット数を合計します。

実行例

Input : n=3
Output : 4

n = 3 の場合を確認してみます。

• 1 → 1 ：セットビット 1 個
• 2 → 10 ：セットビット 1 個
• 3 → 11 ：セットビット 2 個

合計は 1 + 1 + 2 = 4 となり、期待どおりの出力が得られます。

アルゴリズム

Step 1: 正の整数 n を入力として受け取る。
Step 2: 各数値を2進形式に変換する。
Step 3: カウンター変数を 0 で初期化する。
Step 4: 1 から n までの各要素についてセットビット数を求めて加算する。
Step 5: 合計値を表示する。

サンプルコード

# 1からnまでのすべての数のセットビットを
# カウントするPythonプログラム
def countbits(n):
    # カウンターを初期化
    c = 0
    for i in range(1, n + 1):
        c += bitsetcount(i)
    return c

def bitsetcount(x):
    if x <= 0:
        return 0
    return (0 if int(x % 2) == 0 else 1) + bitsetcount(int(x / 2))

# ドライバープログラム
n = int(input("nの値を入力してください: "))
print("セットビットの合計数:", countbits(n))

コードの解説

• countbits(n)：1 から n までの各整数に対して bitsetcount() を呼び出し、結果を累積して返すメイン関数です。
• bitsetcount(x)：再帰を用いてセットビット数を数える補助関数です。x % 2 で最下位ビットが 1 かどうかを判定し、x / 2 で次のビットへ移動します。x が 0 以下になった時点で再帰を終了します。

実行結果

nの値を入力してください: 10
セットビットの合計数: 17

n = 10 の場合、各数値のセットビット数は以下のとおりです。

これらを合計すると 17 となり、プログラムの出力と一致します。

まとめ

このように、単純なループと再帰的なビットカウント関数を組み合わせることで、1 から n までの全整数に含まれるセットビットの総数を簡単に求めることができます。ビット演算の基礎理解にも役立つので、ぜひ手元で動かして挙動を確かめてみてください。