Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 주어진 숫자의 세트 비트만으로 만들 수 있는 최소 숫자 구하기

문제 개요

부호 없는 정수(unsigned number)가 하나 주어졌을 때, 이 숫자가 가진 세트 비트(set bit, 1로 설정된 비트)의 개수를 그대로 활용해 만들 수 있는 최솟값을 구하는 것이 이번 문제의 목표입니다.

최소 숫자를 만들려면 주어진 세트 비트들을 모두 가장 낮은 자릿수 쪽에 몰아 배치하면 됩니다. 상위 자릿수에 비트가 남아 있을수록 값이 커지기 때문입니다.

예시

입력이 10이라면 정답은 3입니다.

  • 10의 이진 표현: 1010
  • 세트 비트의 개수: 2개
  • 2개의 세트 비트로 만들 수 있는 최소 숫자: 0011 → 10진수로 3

알고리즘 접근 방법

문제는 다음 두 단계로 간단히 해결할 수 있습니다.

  1. 주어진 숫자의 세트 비트 개수를 셉니다.
  2. 2^(세트 비트 개수) − 1을 계산합니다. 이 값이 곧 최소 숫자입니다.

그 이유는 간단합니다. 세트 비트가 k개라면, 이 비트들을 하위 k자리에 모두 배치한 값은 이진수로 '111...1'(k개)이 되고, 이는 2^k − 1과 같기 때문입니다.

C++ 구현 예제

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

// Brian Kernighan 방식으로 세트 비트 개수를 세는 함수
int getSetBits(int n) {
    int cnt = 0;
    while (n) {
        ++cnt;
        n = n & (n - 1); // 가장 낮은 위치의 세트 비트를 제거
    }
    return cnt;
}

int getMinNumber(int n) {
    int bits = getSetBits(n);
    return pow(2, bits) - 1;
}

int main() {
    int n = 10;
    cout << "Minimum number = " << getMinNumber(n) << endl;
    return 0;
}

코드 설명

getSetBits() 함수는 Brian Kernighan 알고리즘을 사용합니다. n & (n - 1) 연산을 반복하면 매번 가장 낮은 위치의 세트 비트가 하나씩 제거되므로, 루프가 도는 횟수가 곧 세트 비트의 개수가 됩니다. 이 방식은 전체 비트를 하나씩 검사하는 것보다 효율적입니다.

getMinNumber() 함수는 앞에서 구한 세트 비트 개수를 이용해 pow(2, bits) - 1, 즉 하위 비트가 모두 1로 채워진 값을 반환합니다.

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력을 얻습니다.

Minimum number = 3

시간 복잡도

세트 비트를 세는 과정이 전체 수행 시간을 지배하며, Brian Kernighan 알고리즘의 시간 복잡도는 세트 비트의 개수에 비례하므로 최악의 경우 O(log N)입니다. 전체적으로 매우 효율적인 해법입니다.