C++で指定範囲内の未セットビット（0ビット）の個数を数える方法

整数値 num と、left（左端）・right（右端）の2つの値で表される範囲が与えられたとします。まず対象となる数値を2進数に変換し、続いて左端の桁から右端の桁までループ処理を行い、その範囲内に含まれる「未セットビット（unset bit）」の個数を求めるのが本記事の課題です。

2進数における未セットビットとは、値が「0」になっているビットのことです。整数値を2進数へ変換すると、必ず0と1の組み合わせで表現されます。コンピュータの用語としては、この「0」にあたるビットが未セットビットと呼ばれます。

入出力例

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

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

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

説明: 数値42の2進表現は「101010」です。範囲は left = 1 の桁（ビットが1）から始まり、right = 6 の桁（ビットが0）で終わります。この範囲内には0が3つあるため、カウントは3となります。

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

• 整数型の変数に数値を入力するとともに、left と right の整数値で範囲を指定します。
• セットビットの合計数を保持するための unsigned int 型変数 count を宣言します。
• i を 1 << 7 で初期化し、i > 0 の間、i を i / 2 ずつ減らしながら繰り返す for ループを開始します。
• ループ内では各ビットを判定し、1であれば「1」を、0であれば「0」を出力します。これにより数値の8ビット表現が表示されます。
• i を left から right まで1ずつ増やしながら繰り返す for ループを開始します。
• ループ内で、指定範囲に含まれるビットの総数をカウントアップしていきます。
• 数値が0になるまで処理を続ける while ループで、数値全体のセットビット数を計算します。
• ループ内では count = count + (number & 1) としてセットビットを加算し、number >>= 1 で数値を1ビット右シフトします。
• 一時変数 a を ((1 << right) - 1) ^ ((1 << (left - 1)) - 1) として設定します。これは指定範囲だけを取り出すためのマスクになります。
• 続いて、count を count & a として更新します。
• 最後に、count を「範囲内のビット総数 − 範囲内のセットビット数」として計算すれば、未セットビットの個数が求まります。

コード例

#include<iostream>
using namespace std;
//範囲内の未セットビットの合計数を求める関数
unsigned int unset_bits(unsigned int number, unsigned int left, unsigned int right){
    unsigned int count = 0;
    unsigned int total_bits = 0;
    unsigned i;
    //8ビットの2進表現を表示
    cout<<"8-bit number of "<<number<<" is: ";
    for (i = 1 << 7; i > 0; i = i / 2){
        (number & i)? cout<<"1": cout<<"0";
    }
    //指定範囲内のビット数を計算
    for(i = left; i<=right; i++){
        total_bits++;
    }
    //数値全体のセットビット数を計算
    while (number){
        count += number & 1;
        number >>= 1;
    }
    //範囲内のセットビットを抽出するマスクを作成
    int a = ((1 << right) - 1) ^ ((1 << (left - 1)) - 1);
    count = count & a;
    //範囲内のビット総数からセットビット数を差し引く
    count = total_bits - count;
    cout<<"\nCount of total unset bits in a range are: "<<count;
}
int main(){
    unsigned int number = 80;
    unsigned int left = 1, right = 4;
    unset_bits(number, left, right);
    return 0;
}

出力

上記のコードを実行すると、次のような結果が出力されます。

8-bit number of 80 is: 01010000
Count of total unset bits in a range are: 2

まとめ

本記事では、C++を用いて整数の指定範囲内に存在する未セットビット（0ビット）の個数を求める方法を解説しました。ポイントは、((1 << right) - 1) ^ ((1 << (left - 1)) - 1) という式で範囲を抽出するマスクを作成し、ビット演算を組み合わせることで目的のビットだけを効率よく扱える点です。2進数の考え方とビット操作に慣れておくと、この種の問題はスムーズに解けるようになります。