C++로 세트 비트 개수가 같은 다음으로 큰 수 찾는 방법

문제 소개

숫자 n이 주어졌을 때, n보다 크면서 이진수 표현상 세트 비트(set bit)의 개수가 n과 동일한 수를 찾는 것이 목표입니다.

여기서 세트 비트란 이진수 표현에서 값이 1인 비트를 의미합니다. 예를 들어, 124의 이진수 표현은 1111100이며, 세트 비트의 개수는 5개입니다.

간단한 예시를 통해 문제를 확인해 보겠습니다.

입력

출력

143의 이진수 표현은 10001111로, 역시 세트 비트가 5개입니다. 즉, 124보다 크면서 세트 비트 개수가 같은 가장 작은 수가 143입니다.

알고리즘

숫자 n을 초기화합니다.
주어진 수의 세트 비트 개수를 계산하는 함수를 작성합니다.
반복 변수를 n + 1로 초기화합니다.
무한 루프를 실행합니다.
- 현재 숫자의 세트 비트 개수가 n의 세트 비트 개수와 같은지 확인합니다.
- 조건을 만족하는 수를 찾으면 해당 값을 반환합니다.
- 찾지 못했다면 숫자를 1씩 증가시키며 반복합니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

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

// 세트 비트(1)의 개수를 계산하는 함수
int getSetBitsCount(int n) {
    int count = 0;
    while (n) {
        if (n % 2 == 1) {
            count += 1;
        }
        n /= 2;
    }
    return count;
}

// 세트 비트 개수가 같으면서 더 큰 다음 수를 찾는 함수
int getNextGreaterElementWithSameSetBits(int n) {
    int setBitsCount = getSetBitsCount(n);
    int i = n + 1;
    while (true) {
        if (setBitsCount == getSetBitsCount(i)) {
            return i;
        }
        i += 1;
    }
}

int main() {
    int n = 124;
    cout << getNextGreaterElementWithSameSetBits(n) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

동작 원리 설명

getSetBitsCount 함수는 숫자를 2로 나누어 가며 나머지가 1일 때마다 카운트를 증가시켜 세트 비트의 총 개수를 구합니다.

getNextGreaterElementWithSameSetBits 함수는 먼저 n의 세트 비트 개수를 저장한 뒤, n+1부터 시작해 조건을 만족하는 수를 찾을 때까지 하나씩 검사합니다. 조건에 맞는 첫 번째 수가 곧 정답이 됩니다.

이 방법은 직관적이고 구현이 간단하지만, 최악의 경우 시간 복잡도가 커질 수 있습니다. 비트 연산을 활용한 최적화 기법(예: 오른쪽 끝의 01 패턴을 10으로 바꾸고 하위 비트를 재배치하는 방법)을 사용하면 더 빠르게 답을 구할 수 있습니다.