문제 개요
이 문제에서는 하나의 숫자 N이 주어지며, 이 숫자에서 가장 오른쪽에 있는 설정된 비트(set bit)의 위치, 즉 인덱스를 출력하는 것이 과제입니다. 여기서 인덱스는 가장 오른쪽 비트(LSB)를 1번으로 간주하여 셉니다.
예시를 통해 문제를 이해해 보겠습니다.
- 입력 − 4
- 출력 − 3
- 설명 − 4의 이진수 표현은 100입니다. 가장 오른쪽 설정 비트는 오른쪽에서 세 번째 자리에 있으므로 인덱스는 3입니다.
해결 접근 방법
단순한 방법: 비트 시프트
가장 직관적인 해결책은 숫자를 한 비트씩 오른쪽으로 시프트하면서 설정된 비트를 만날 때까지 반복하는 것입니다. 하지만 이 방법은 숫자가 클 경우 설정 비트를 만나기까지 여러 번의 연산이 필요해 성능이 크게 떨어질 수 있습니다.
효율적인 방법: 부울 대수와 2의 보수 활용
훨씬 더 효율적인 방법은 부울 대수를 이용하는 것입니다. 절차는 다음과 같습니다.
- 먼저 숫자의 2의 보수(−N)를 계산합니다. 2의 보수는 모든 비트를 반전한 뒤 1을 더한 값으로, 그 결과 가장 오른쪽 설정 비트의 위치만 원래 숫자와 일치하게 됩니다.
- 원래 숫자와 그 2의 보수를 비트별 AND(&) 연산합니다. 그러면 가장 오른쪽 설정 비트 하나만 1로 남고 나머지 비트는 모두 0이 된 숫자를 얻을 수 있습니다.
- 마지막으로 이 값에 밑이 2인 로그(log₂)를 취하고 1을 더하면 원하는 비트의 인덱스를 구할 수 있습니다.
다소 복잡해 보일 수 있으므로, 실제 예시로 이 방법을 풀어 보겠습니다.
N = 10, 이진수 = 1010 2의 보수(−N) = 0110 1010 & 0110 = 0010 log₂(2) = 1 1 + 1 = 2 → 가장 오른쪽 설정 비트의 인덱스는 2
구현 예제
위에서 설명한 솔루션을 구현한 프로그램입니다.
#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 << "숫자 " << N << "의 가장 오른쪽 설정 비트 위치는 : ";
rightSetBit(N);
return 0;
}출력
숫자 10의 가장 오른쪽 설정 비트 위치는 : 2
복잡도 및 참고 사항
이 방법은 반복문 없이 상수 시간(O(1)) 안에 답을 구할 수 있어 매우 효율적입니다. 다만 N이 0인 경우에는 설정된 비트가 존재하지 않아 log₂(0)이 정의되지 않으므로, 실제 코드에서는 N이 0보다 큰지 먼저 확인하는 것이 안전합니다.