C++で唯一の設定ビットの位置を検索します

この問題では、2進表現に1つのセットビットしかない数Nが与えられます。私たちの仕事は、唯一のセットビットの位置を見つけることです。数値に設定ビットが1つしかない場合は、数値の位置を返します。それ以外の場合は、無効な数値を出力します。

問題を理解するために例を見てみましょう

入力

N = 32

出力

6

説明

Binary representation of the number is 10000.

ソリューションアプローチ

先に進む前に知っておくべき1つの事実は、2の累乗の場合、その数は1セットビットしかないということです。それ以外の場合は、より多くのセットビット数があります。

簡単な解決策は、右端のビットから始めて、ビットの値をチェックすることです。ループを使用して、設定されているかどうかを確認します。

ソリューションの動作を説明するプログラム

例

#include <iostream>
using namespace std;
bool isPowerOfTwo(unsigned n) {
   if(n>0) {
      while(n%2 == 0)
      n/=2;
      if(n == 1)
         return true;
   }
   if(n == 0 || n != 1)
      return false;
   return false;
}
int findPostionOfSetBit(unsigned n) {
   unsigned i = 1, position = 1;
   while (!(i & n)) {
      i = i << 1;
      ++position;
   }
   return position;
}
int main(void){
   int n = 64;
   if(!isPowerOfTwo(n))
      cout<<"Invalid Number!";
   else
      cout<<"The position of the number "<<n<<" is "<<findPostionOfSetBit(n);
   return 0;
}

出力

The position of the number 64 is 7

この問題を解決する別の方法は、シフト操作を使用して、数値を0になるまで右にシフトすることです。最後に0に到達するために行われるシフトの数は、設定されたビットの位置です。

ソリューションの動作を説明するプログラム

例

#include <iostream>
using namespace std;
bool isPowerOfTwo(unsigned n) {
   if(n>0) {
      while(n%2 == 0)
         n/=2;
      if(n == 1)
         return true;
   }
   if(n == 0 || n != 1)
      return false;
   return false;
}
int findPostionOfSetBit(unsigned n) {
   unsigned position = 0;
   while (n) {
      n = n >> 1;
      ++position;
   }
   return position;
}
int main(void){
   int n = 64;
   if(!isPowerOfTwo(n))
      cout<<"Invalid Number!";
   else
      cout<<"The position of the number "<<n<<" is
      "<<findPostionOfSetBit(n);
   return 0;
}

出力

The position of the number 64 is 7

この問題を解決するもう1つの方法は、数式を使用することです。私たちはそれを知っています、

2i = n, where n is the number
and i is the position of the number
The values of i here can be found using the formula,
i = log2(n)

ソリューションの動作を説明するプログラム

例

#include <iostream>
#include <math.h>
using namespace std;
bool isPowerOfTwo(unsigned n) {
   if(n>0) {
      while(n%2 == 0)
         n/=2;
      if(n == 1)
         return true;
   }
   if(n == 0 || n != 1)
      return false;
   return false;
}
int findPostionOfSetBit(unsigned n) {
   unsigned position = log2(n) + 1; ;
   return position;
}
int main(void){
   int n = 64;
   if(!isPowerOfTwo(n))
      cout<<"Invalid Number!";
   else
      cout<<"The position of the number "<<n<<" is "<<findPostionOfSetBit(n);
   return 0;
}

出力

The position of the number 64 is 7