Pythonで整数の2進表現に含まれる1のビット数を数える方法

ある整数 n が与えられたとき、その数を2進数で表した際に含まれる「1」のビット（セットビット）の個数を求めることを考えます。この問題は「ポピュレーションカウント」や「ハミング重み」と呼ばれることもあり、ビット演算の基礎を学ぶのに最適な題材です。

問題の例

例えば、入力が 12 の場合を考えてみましょう。12 を2進数で表すと 1100 となり、「1」のビットは2個含まれています。したがって、出力は 2 になります。

解法のアプローチ

この問題は、次の手順で解くことができます。

• カウンター変数 count を 0 で初期化する
• n が 0 になるまで以下を繰り返す
  • n の最下位ビット（n AND 1）を count に加算する
  • n を右に1ビットシフトする（n ÷ 2 の切り捨てと同等）
• count を返す

ポイントは「n & 1」というビットAND演算です。これは n の最下位ビットが 1 なら 1、0 なら 0 を返すため、各桁が 1 かどうかを効率的に判定できます。また、「n >>= 1」による右シフトで数値を半分にしながら、すべてのビットを先頭から順に調べていきます。

実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, n):
        count = 0
        while (n):
            count += n & 1
            n >>= 1
        return count

ob = Solution()
print(ob.solve(12))

入力

12

出力

2

補足：より簡単な代替手段

Pythonでは、組み込みメソッドを使って同じ結果をより簡潔に得ることもできます。

• bin(n).count('1') — 2進数の文字列に変換してから「1」の出現回数を数える方法
• n.bit_count() — Python 3.10 以降で利用可能な、セットビット数を直接返すメソッド

ただし、ビット演算による上記の実装方法は、アルゴリズムの仕組みを理解するうえで重要です。計算量は O(log n)（ビット長に比例）であり、非常に効率的です。