Pythonで整数のセットビット（1の数）をカウントする方法

この記事では、与えられた整数の2進数表現に含まれる「1」の個数（セットビット数）をカウントするPythonプログラムについて解説します。

問題定義

整数 n が与えられたとき、その2進数表現の中に「1」がいくつ現れるかを求めます。この操作は一般にポピュレーションカウント（popcount）と呼ばれ、ビット演算やアルゴリズムの基礎を学ぶうえで重要なテーマです。

例えば n = 15 の場合、2進数表現は 1111 となるため、セットビットの数は 4 になります。

方法1：素朴なアプローチ（ループ処理）

最も基本的な方法は、整数を右シフトしながら最下位ビットが1かどうかを順番に確認していくものです。

サンプルコード

# ビットをカウントする関数
def count(n):
    count = 0
    while (n):
        count += n & 1   # 最下位ビットが1なら加算
        n >>= 1          # 右に1ビットシフト
    return count

# メイン処理
n = 15
print("セットビットの数 :", count(n))

実行結果

セットビットの数 : 4

方法2：再帰的なアプローチ

同じロジックは再帰を使っても実装できます。ベースケースとして n が 0 のときに 0 を返し、それ以外では最下位ビットの値と、右シフトした値に対する再帰呼び出しの結果を足し合わせます。

サンプルコード

# 再帰による実装
def count(n):
    # ベースケース
    if (n == 0):
        return 0
    else:
        # 最下位ビットがセットされているか確認
        return (n & 1) + count(n >> 1)

# メイン処理
n = 15
print("セットビットの数 :", count(n))

実行結果

セットビットの数 : 4

補足：Python 3.10以降の組み込み関数

Python 3.10 以降では、標準ライブラリの組み込みメソッド int.bit_count() を使うことで、セットビットの数を一行で取得できます。

n = 15
print(n.bit_count())  # 出力: 4

また、bin(n).count("1") のように2進数文字列に変換して数える方法もよく知られています。実務ではこれらの組み込み機能を利用するのが簡潔で高速です。

まとめ

この記事では、ループと再帰という2つのアプローチを用いて、整数に含まれるセットビットの数をカウントするPythonプログラムを作成しました。どちらの方法も計算量は O(log n) であり、ビット演算の基本的な考え方を理解するのに適した例題です。さらに、Python 3.10以降では bit_count() メソッドを使えばより簡単に実現できることも紹介しました。