C ++の[0、n]の範囲に1セットビットしかない数値の数

数値が与えられ、タスクは、0から指定された数値までの範囲の数値のカウントを計算することです。たとえば、numには1つのセットビットがあります

2進数のセットビットは1で表されます。整数値の2進数を計算するときは常に、0と1の組み合わせとして形成されます。したがって、数字1は、コンピューターの観点からはセットビットとして知られています。

入力 − int num =15

出力 − [0、15]の範囲に1セットビットしかない数値の数は− 4

説明 −指定された数は15であるため、範囲は0〜15です。次に、4桁を計算します

−

0-> 0000 =0セットビット、1-> 0001 =1セットビット、2-> 0010 =1セットビット、3-> 0011 =2セットビット、4-> 0100 =1セットビット、5-> 0101 =2セットビット、6-> 0110 =2セットビット、7-> 0111 =3セットビット、8-> 1000 =1セットビット、1-> 1001 =2セットビット、10-> 1010 =2セットビット、11 -> 1011 =3セットビット、12-> 1100 =2セットビット、13-> 1101 =3セットビット、14-> 1110 =3セットビット、15-> 1111=4セットビット。ここで、1セットビットの数値を選択します。それらは1、2、4、および8です。

入力 − int num =4

出力 − [0、15]の範囲に1セットビットしかない数値の数は− 3

説明 −指定された数は4であるため、範囲は0〜4です。次に、4桁のバイナリを計算します

−

0-> 0000 =0セットビット、1-> 0001 =1セットビット、2-> 0010 =1セットビット、3-> 0011 =2セットビット、4-> 0100=1セットビット。ここで、1セットビットの数字を選択します。それらは1、2、4です。

以下のプログラムで使用されているアプローチは次のとおりです

与えられた問題を解決するための複数のアプローチ、すなわちナイーブなアプローチと効率的なアプローチがあります。それでは、最初にナイーブなアプローチを見てみましょう。 。

• 数値を入力し、関数に渡してさらに処理します。

• 一時変数のカウントを取得して、ビットが正確に1に設定された範囲内の数値のカウントを格納します

• ループFORをiから1まで開始して番号まで

• ループ内で、設定されたビット数を返す関数「__builtin_popcount（i）」を使用して一時変数を設定します。

• IF temp =1を確認してから、カウントをインクリメントします

• 返品数

• 結果の印刷

効率的なアプローチ

• 数値を入力し、関数に渡してさらに処理します。

• 一時変数のカウントを取得して、ビットが正確に1に設定された範囲内の数値のカウントを格納します

• tempからtemp<=number

  までの間にループを開始します

• ループ内で、カウントを1ずつ増やし、tempをtemp*2として設定します

• 返品数

• 結果の印刷

例（素朴なアプローチ）

#include <iostream>
using namespace std;
//function to Count of numbers having only 1 set bit in the range [0, n]
int set_bits(int number){
   int count = 0;
   for (int i = 1; i <= number; i++){
      int temp = __builtin_popcount(i);
      if (temp == 1){
         count++;
      }
   }
   return count;
}
int main(){
   int number = 15;
   cout<<"Count of numbers having only 1 set bit in the range [0, "<<number<<"] are: "<<set_bits(number);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of numbers having only 1 set bit in the range [0, 15] are: 4

例（効率的なアプローチ）

#include <iostream>
using namespace std;
//function to Count of numbers having only 1 set bit in the range [0, n]
int set_bits(int number){
   int count = 0;
   int temp = 1;
   while(temp <= number){
      count++;
      temp = temp *2;
   }
   return count;
}
int main(){
   int number = 15;
   cout<<"Count of numbers having only 1 set bit in the range [0, "<<number<<"] are: "<<set_bits(number);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of numbers having only 1 set bit in the range [0, 15] are: 4