C++에서 유일한 세트 비트의 위치 찾기

이 문제에서 우리는 이진 표현에서 단 하나의 세트 비트를 갖는 숫자 N이 주어집니다. 우리의 임무는 유일한 세트 비트의 위치를 ​​찾는 것입니다. 숫자에 설정된 비트가 하나만 있으면 숫자의 위치를 ​​반환하고 그렇지 않으면 잘못된 숫자를 인쇄합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

N = 32

출력

6

설명

Binary representation of the number is 10000.

솔루션 접근 방식

계속 진행하기 전에 알아야 할 한 가지 사실은 숫자가 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

문제를 해결하는 또 다른 방법은 수학 공식을 사용하는 것입니다. 우리는 알고 있습니다.

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