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

整数値 num と、left（左端）および right（右端）で指定される範囲が与えられます。まず対象の数値を2進数表現に変換し、次に左端の桁から右端の桁まで順に走査して、指定された範囲内に存在するセットビットの個数を計算します。

2進数におけるセットビットとは、「1」で表されるビットのことです。整数値を2進数に変換すると、必ず0と1の組み合わせで表現されます。コンピュータの用語では、この「1」に相当するビットをセットビットと呼びます。

入出力例

入力: int number = 50, left = 2, right = 5
出力: 範囲内のセットビットの合計数は 2

説明: 数値50の2進数表現は「110010」です。left = 2（ビットが1）から始まり、right = 5（ビットが1）で終わる範囲を調べると、その間のビットはすべて0であるため、セットビットの数は2になります。

入力: int number = 42, left = 3, right = 4
出力: 範囲内のセットビットの合計数は 1

説明: 数値42の2進数表現は「101010」です。left = 3 から right = 4 までの範囲内にはセットビットが1つだけ含まれるため、カウントは1になります。

プログラムで使用するアプローチ

• 整数型の変数に数値を入力し、left と right の整数値で範囲を指定します。
• セットビットの合計数を格納するための unsigned int 型変数 count を宣言します。
• i を 1 << 7 から開始し、i > 0 を満たす間、i = i / 2 で更新しながら FOR ループを実行します。
• ループ内では、num & i が真であれば「1」を、偽であれば「0」を出力します。
• 数値が0になるまで、ビットの合計数を計算する while ループを開始します。
• ループ内では count = count + (number & 1) としてカウントを加算し、number >>= 1 で右シフトしていきます。
• 一時変数 a に ((1 << right) - 1) ^ ((1 << (left - 1)) - 1) を設定して、範囲抽出用のマスクを作成します。
• count を count & a で更新し、最終的なカウントを求めます。
• 結果の count を出力します。

マスク生成のポイント

式 ((1 << right) - 1) ^ ((1 << (left - 1)) - 1) は、指定範囲だけを取り出すためのビットマスクを生成しています。(1 << right) - 1 は下位 right ビットがすべて1のマスクを作り、そこから下位 (left - 1) ビットがすべて1のマスクをXORで差し引くことで、left ビット目から right ビット目までだけが1になったマスクが得られます。これにより、範囲外のビットを除外したカウントが可能になります。

C++コード例

#include<iostream>
using namespace std;
// 範囲内の合計ビット数をカウントする関数
unsigned int bits(unsigned int number, unsigned int left, unsigned int right){
    unsigned int count = 0;
    unsigned i;
    // 8ビット表現を表示する
    cout<<"8-bit digits of "<<number<<" is: ";
    for (i = 1 << 7; i > 0; i = i / 2){
        (number & i)? cout<<"1": cout<<"0";
    }
    // 数値全体のセットビット数を計算する
    while (number){
        count += number & 1;
        number >>= 1;
    }
    // 指定範囲内のセットビットを計算する
    int a = ((1 << right) - 1) ^ ((1 << (left - 1)) - 1);
    count = count & a;
    cout<<"\nCount of total set bits in a range are: "<<count;
}
int main(){
    unsigned int number = 42;
    unsigned int left = 2, right = 5;
    bits(number, left, right);
    return 0;
}

出力結果

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

8-bit digits of 42 is: 00101010
Count of total set bits in a range are: 2