Pythonで指定範囲内のセットビット数をカウントする方法

正の整数を2進数に変換すると、値が「1」になっているビット（セットビット）がいくつか存在します。セットビットとは、2進数表現において1として表されるビットのことです。この記事では、数値を2進数に変換した後、指定した範囲内にあるセットビットの数を取得する方法を2つ紹介します。

bin関数とスライスを使う方法

以下の例では、まずbin関数を使って数値の2進数表現を取得します。次にスライス操作で「0b」という接頭辞を取り除き、文字列を反転させた上で、指定された範囲（l桁目からr桁目まで）に含まれる「1」の個数をカウントします。

サンプルコード

def SetBits_cnt(n, l, r):
    bin_val = bin(n)

    # 変換結果に付く「0b」の接頭辞を削除
    bin_val = bin_val[2:]
    print(bin_val)

    # 文字列を反転
    bin_val = bin_val[-1::-1]

    # インデックス l-1 から r までのセットビット「1」をカウント
    print(len([bin_val[i] for i in range(l - 1, r) if bin_val[i] == '1']))

SetBits_cnt(83, 1, 6)

実行結果

上記のコードを実行すると、以下の出力が得られます。

1010011
3

ビット演算を使う方法

ビット演算子を利用することでもセットビットを求められます。以下の例では、まず指定範囲に対応するマスクをビット演算で作成し、元の数値とのANDを取ります。その結果を、セットビットのみを数える関数に渡してカウントします。

ここで使われている n &= (n - 1) というテクニックは、各ループで最下位のセットビットを1つずつ消去していくことで効率的にビット数を数えられる、よく知られたアルゴリズムです。

サンプルコード

def trackBitsInRange(n, l, r):
    # ビット演算子を使用して範囲のマスクを作成
    bit_num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1)
    # ビット演算後にセットビットをカウント
    return trackSetBits(n & bit_num)

def trackSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count = count + 1
    return count

print(trackBitsInRange(83, 1, 6))

実行結果

上記のコードを実行すると、以下の出力が得られます。

3

どちらの方法でも、数値83（2進数で1010011）の1桁目から6桁目までの範囲に含まれるセットビットが3個であることを確認できます。コードのシンプルさを重視するならbin関数を使った方法が、処理速度やメモリ効率を重視するならビット演算を使った方法がおすすめです。