C++로 숫자의 이진 표현에서 길이 n 이상의 연속된 1 찾기

문제 개요

두 개의 정수 x와 n이 주어졌을 때, x의 32비트 이진 표현에서 길이가 n 이상인 첫 번째 연속된 1의 구간을 찾아 그 시작 위치를 반환하는 것이 목표입니다. 만약 조건을 만족하는 구간이 존재하지 않는다면 -1을 반환합니다.

예를 들어 x = 35, n = 2라고 하면 결과는 31이 됩니다. 35를 32비트 정수로 나타내면 다음과 같습니다.

00000000000000000000000000100011

맨 왼쪽 비트를 인덱스 0으로 볼 때, 길이가 2인 연속된 1은 인덱스 31에서 시작하므로 정답은 31입니다.

접근 방법

이 문제는 선행 0(leading zero)의 개수를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

x의 선행 0 개수를 구한 뒤, 그만큼 왼쪽 시프트하여 최상위 1을 맨 앞으로 이동시킵니다.
x의 모든 비트를 반전한(~x) 값의 선행 0 개수를 구하면, 이는 곧 맨 앞에 있는 연속된 1의 길이와 같습니다.
그 길이가 n 이상이면 현재 위치를 반환하고, 그렇지 않으면 다시 시프트하여 다음 1의 구간을 검사합니다.
x가 0이 될 때까지 반복하며, 끝까지 찾지 못하면 -1을 반환합니다.

구현 예제

#include<iostream>
using namespace std;

int leadingZeroCount(int x) {
    unsigned y;
    int n;
    n = 32;
    for (int i = 16; i > 1; i = i / 2) {
        y = x >> i;
        if (y != 0) {
            n -= i;
            x = y;
        }
    }
    y = x >> 1;
    if (y != 0)
        return n - 2;
    return n - x;
}

int consecutiveOnePosition(unsigned x, int n) {
    int k, p;
    p = 0;
    while (x != 0) {
        k = leadingZeroCount(x);
        x = x << k;
        p = p + k;
        k = leadingZeroCount(~x);
        if (k >= n)
            return p + 1;
        x = x << k;
        p = p + k;
    }
    return -1;
}

int main() {
    int x = 35;
    int n = 2;
    cout << "Consecutive 1s of length " << n << " is starting from index: " << consecutiveOnePosition(x, n);
}

코드 설명

leadingZeroCount() 함수는 이진 탐색 방식으로 선행 0의 개수를 계산합니다. 카운터를 32로 초기화한 후 16, 8, 4, 2비트씩 오른쪽으로 시프트하며 값이 0이 아닌지 확인함으로써, 최상위 1비트의 위치를 빠르게 좁혀 나갑니다.

consecutiveOnePosition() 함수는 앞서 설명한 알고리즘 그대로 동작합니다. 선행 0만큼 시프트하여 1의 구간 시작점을 찾고, 비트 반전을 통해 해당 구간의 길이를 측정한 뒤 n과 비교합니다.

실행 결과

Consecutive 1s of length 2 is starting from index: 31

x = 35의 이진 표현에서 길이 2짜리 연속된 1은 인덱스 31에서 시작하므로, 프로그램은 31을 출력합니다.

복잡도 분석

선행 0 계산은 최대 5번의 시프트·비교 연산으로 완료되므로 사실상 상수 시간(O(1))입니다. 전체 탐색 역시 검사해야 할 비트 그룹의 수에 비례하며, 32비트 정수 기준으로 최대 16개 그룹만 확인하면 되므로 전체 시간 복잡도 또한 O(1)로 볼 수 있습니다.