C++ 비트 연산으로 이진 표현에서 인접한 두 1 사이의 최대 0 개수 구하기

문제 개요

하나의 정수 n이 주어졌을 때, n의 이진 표현에서 서로 인접한 두 개의 1 사이에 존재하는 0의 최대 개수를 구하는 것이 이번 문제의 목표입니다. 만약 이진 표현에 1이 두 개 미만으로 존재한다면 -1을 반환해야 합니다.

예시

입력값이 35라고 가정해 보겠습니다. 35의 이진 표현은 다음과 같습니다.

00100011

위 이진수에서 가장 오른쪽의 두 1은 서로 붙어 있어 사이의 0이 없지만, 그 앞의 1과의 사이에는 0이 3개 존재합니다. 따라서 정답은 3이 됩니다.

알고리즘 접근 방법

이 문제는 비트 시프트 연산자를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 n의 이진 표현에서 각 1의 위치를 찾아내고, 인접한 두 1의 위치 차이를 최대화하는 것입니다.

n이 0이거나 2의 거듭제곱이면 -1을 반환합니다. (1이 아예 없거나 하나만 존재하기 때문입니다.)
변수 prev에 가장 오른쪽에 있는 첫 번째 1의 위치를 저장합니다. 이 값은 직전에 발견한 1의 위치를 계속 추적합니다.
변수 cur는 prev 바로 다음에 나오는 1의 위치를 저장합니다.
cur - prev - 1을 계산하면 두 인접한 1 사이의 0 개수가 됩니다. 이 값을 기존 최댓값과 비교하여 갱신하고, 다음 반복을 위해 prev = cur으로 설정합니다.
보조 변수 setBit가 n의 모든 비트를 왼쪽부터 차례로 스캔하며, 현재 비트가 0인지 1인지 판별하는 역할을 합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

int getMaxZeros(int n) {
    // 0이거나 2의 거듭제곱이면 1이 두 개 미만이므로 -1 반환
    if (n == 0 || ((n & (n - 1)) == 0)) {
        return -1;
    }
    int setBit = 1;
    int prev = 0;
    int i;
    // 가장 오른쪽 1의 위치 찾기
    for (i = 1; i < sizeof(int) * 8; ++i) {
        ++prev;
        if ((n & setBit) == setBit) {
            setBit = setBit << 1;
            break;
        }
        setBit = setBit << 1;
    }
    int maxZeros = INT_MIN;
    int cur = prev;
    // 나머지 비트를 스캔하며 인접한 1 사이의 0 개수 최댓값 갱신
    for (int j = i + 1; j <= sizeof(int) * 8; ++j) {
        ++cur;
        if ((n & setBit) == setBit) {
            if (maxZeros < (cur - prev - 1)) {
                maxZeros = cur - prev - 1;
                prev = cur;
            }
        }
        setBit = setBit << 1;
    }
    return maxZeros;
}

int main() {
    int n = 35;
    cout << "Maximum zeros = " << getMaxZeros(n) << endl;
    return 0;
}

참고: 2의 거듭제곱 판별 조건에서 (n & (n - 1)) == 0처럼 괄호를 반드시 명시해야 합니다. C++에서는 비교 연산자(==)가 비트 AND 연산자(&)보다 우선순위가 높기 때문에, 괄호를 생략하면 의도와 다르게 해석되어 거듭제곱 판별이 올바르게 동작하지 않습니다.

실행 결과

Maximum zeros = 3

동작 원리 정리

입력값 35(이진수 00100011)의 경우, 코드는 다음 순서로 동작합니다.

첫 번째 루프에서 가장 오른쪽 1의 위치(prev = 1)를 찾습니다.
두 번째 루프에서 다음 1을 만날 때마다 cur - prev - 1로 두 1 사이의 0 개수를 계산합니다.
붙어 있는 두 1 사이는 0개, 그 앞 1과의 사이는 3개이므로 최종적으로 3이 반환됩니다.

이 알고리즘은 정수의 전체 비트를 한 번만 순회하므로 시간 복잡도는 O(비트 수), 즉 O(log n)이며, 추가 배열 없이 상수 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다.