이 문제에서는 이진 표현상 세트 비트(set bit)가 단 하나만 존재하는 숫자 N이 주어집니다. 우리의 목표는 이 유일한 세트 비트의 위치를 찾는 것입니다. 만약 숫자에 세트 비트가 하나뿐이라면 그 위치를 반환하고, 그렇지 않다면 '잘못된 숫자'임을 출력해야 합니다.
예시를 통해 문제를 이해해 보겠습니다.
입력
N = 32
출력
6
설명
숫자 32의 이진 표현은 10000입니다.
해결 접근 방식
본격적으로 살펴보기 전에 알아두어야 할 핵심 사실이 있습니다. 바로 어떤 수가 2의 거듭제곱일 때만 세트 비트가 정확히 하나 존재한다는 점입니다. 그 외의 경우에는 세트 비트가 반드시 두 개 이상입니다.
가장 간단한 방법은 가장 오른쪽 비트부터 시작해 각 비트의 값을 확인하는 것입니다. 루프를 사용하여 해당 비트가 설정되어 있는지 여부를 검사할 수 있습니다.
이 해결 방법의 동작을 보여주는 프로그램입니다.
예제 코드
#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 findPositionOfSetBit(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 "<<findPositionOfSetBit(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 findPositionOfSetBit(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 "<<findPositionOfSetBit(n);
return 0;
}출력 결과
The position of the number 64 is 7
마지막으로 수학 공식을 활용하는 방법도 있습니다. 다음과 같은 관계식을 이용하면 됩니다.
2<sup>i</sup> = n (여기서 n은 주어진 숫자, i는 세트 비트의 위치) i의 값은 다음 공식으로 구할 수 있습니다. i = log<sub>2</sub>(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 findPositionOfSetBit(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 "<<findPositionOfSetBit(n);
return 0;
}출력 결과
The position of the number 64 is 7
세 가지 방법 모두 유효하지만, 로그 공식을 활용한 마지막 방법이 O(log n)의 시간 복잡도로 가장 효율적입니다. 다만 부동소수점 연산의 정밀도 문제를 고려하면, 실무에서는 비트 연산 기반의 첫 번째와 두 번째 방법이 더 안정적인 선택이 될 수 있습니다.