C++에서 숫자의 K번째 세트 비트 위치 찾는 방법

이 문제에서는 두 개의 정수 N과 K가 주어지며, 우리의 목표는 숫자 N을 오른쪽부터 세었을 때 K번째 세트 비트(set bit)의 인덱스를 찾는 것입니다.

세트 비트는 숫자의 이진 표현을 통해 확인할 수 있습니다. 이진 표현에서 인덱싱은 오른쪽 끝자리를 0으로 시작하여 왼쪽 방향으로 진행됩니다.

예시 — 이진수 '011101'의 경우, 오른쪽부터 인덱스 0에는 1이 있고, 인덱스 1에는 0이 있으며, 그다음 자리들도 같은 방식으로 번호가 매겨집니다.

문제 이해를 위한 예시

입력 — N = 6, K = 2

출력 — 2

설명 — 6의 이진 표현은 0110입니다. 오른쪽에서 두 번째 세트 비트는 인덱스 2에 위치합니다.

해결 접근 방법

이 문제를 해결하려면 현재 비트가 설정되어 있는지 먼저 확인하고, 설정되어 있다면 K의 값을 하나 감소시킵니다. 매번 확인 후 숫자를 오른쪽으로 1비트씩 시프트하면 다음 비트를 얻을 수 있으며, 이때 시프트를 수행한 횟수도 함께 기록해야 합니다. K의 값이 0이 되는 순간, 지금까지 수행한 시프트 횟수가 곧 원하는 인덱스가 됩니다.

만약 모든 비트를 확인했는데도 K번째 세트 비트를 찾지 못했다면, 유효한 인덱스가 없음을 의미하는 -1을 반환하도록 처리합니다.

구현 예제

위에서 설명한 로직을 구현한 프로그램입니다.

#include <iostream>
using namespace std;
int FindIndexKthBit(int N, int K) {
    int index = 0;
    while (N) {
        if (N & 1)
            K--;
        if (!K)
            return index;
        index++;
        N = N >> 1;
    }
    return -1;
}
int main() {
    int N = 12, K = 2;
    cout << "The " << K << "th set bit of the number " << N << " is at index : \t";
    int index = FindIndexKthBit(N, K);
    if (index != -1)
        cout << index;
    else
        cout << "\nsorry no index found";
    return 0;
}

출력 결과

The 2th set bit of the number 12 is at index : 3

복잡도 분석

시간 복잡도: O(log N) — 숫자 N의 비트 길이만큼 반복하기 때문입니다.

공간 복잡도: O(1) — 추가적인 메모리 사용 없이 상수 공간만 필요합니다.