C++에서 가장 오른쪽 세트 비트의 위치

이 문제에서 숫자 N이 주어집니다. 우리의 임무는 숫자의 가장 오른쪽에 설정된 비트의 인덱스를 인쇄하는 것입니다.

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

입력 - 4

출력 - 3

설명 - 4의 바이너리는 100이고, 가장 오른쪽에 설정된 비트의 인덱스는 3입니다.

이 문제를 해결하기 위해 간단한 솔루션은 설정된 비트가 발생할 때까지 숫자를 이동하는 것이지만 숫자가 크면 많은 계산이 필요할 수 있습니다.

보다 효율적인 솔루션은 부울 대수를 사용하는 것입니다. 이를 위해 먼저 숫자의 2의 보수를 계산합니다. 이렇게 하면 숫자의 모든 비트가 뒤집혀서 첫 번째 세트 비트가 그대로 유지됩니다. 그런 다음 숫자의 비트 단위 &를 계산하고 2의 보수입니다. 이것은 단지 하나의 세트 비트와 우리가 원하는 위치를 가진 숫자가 될 것입니다. 해는 숫자 +1의 log2로 주어집니다.

이 방법을 사용하여 예제를 해결해 보겠습니다.

N= 10 , binary = 1010
2’s complement, 0101
1010 & 0101 = 0010
log2(2) = 1
1+1 = 2 which is the given index.

예시

솔루션 구현을 보여주는 프로그램,

#include <iostream>
#include <math.h>
using namespace std;
void rightSetBit(int N) {
   int bitIndex = log2(N & -N)+1;
   cout<<bitIndex;
}
int main() {
   int N = 10;
   cout<<"The rightmost Set bit of the number "<<N<<" is : ";
   rightSetBit(N);
   return 0;
}

출력

The rightmost Set bit of the number 10 is : 2