Pythonで数値の1ビット数（ハミング重み）を数える方法

符号なし整数 n が与えられたとき、その2進表現に含まれる「1」の個数を求めることを考えます。この個数はハミング重み（Hamming Weight）とも呼ばれます。

例えば、数値が 000000101101 の場合、2進表現中の「1」は4つあるため、結果は 4 となります。

解法のアプローチ

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

• 数値を2進数の文字列に変換する
• カウンタ変数 count を 0 で初期化する
• 2進数文字列の各文字 e について処理を行う
  • 文字が「1」であれば、count を 1 増やす
• 最後に count を返す

実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        n = str(bin(n))
        one_count = 0
        for i in n:
            if i == "1":
                one_count += 1
        return one_count

num = int("000000101101", 2)
ob1 = Solution()
print(ob1.hammingWeight(num))

入力

num = "000000101101"

出力

4

より簡潔な書き方

Pythonでは、文字列の count() メソッドを使うことで、上記のループ処理を1行にまとめることもできます。

def hammingWeight(n):
    return bin(n).count("1")

さらに、Python 3.10以降では、整数型に組み込みの bit_count() メソッドが追加されており、これを使えば最もシンプルに記述できます。

def hammingWeight(n):
    return n.bit_count()

状況に応じて、可読性とパフォーマンスのバランスを考慮して最適な方法を選びましょう。