C++ 비트 재배열로 만들 수 있는 최대 수 구하기

문제 개요

부호 없는 정수(unsigned number)가 주어졌을 때, 해당 숫자가 가진 비트들을 재배열하여 만들 수 있는 최대의 수를 구하는 문제입니다.

예를 들어 입력값이 8이라면 이 수의 이진수 표현은 다음과 같습니다.

00000000000000000000000000001000

이 수를 최대화하려면 가장 상위 비트(MSB)부터 1을 채워야 합니다. 즉, 기존에 1로 설정된 비트들을 모두 왼쪽 끝으로 몰아 넣으면 됩니다. 그 결과 값은 2147483648이 되며, 이진수 표현은 다음과 같습니다.

10000000000000000000000000000000

알고리즘 접근 방법

핵심 아이디어는 간단합니다. 1로 설정된 비트의 개수만 세면, 나머지는 그 비트들을 상위 자리에 배치하는 것뿐입니다. 알고리즘은 다음 세 단계로 구성됩니다.

1. 주어진 수의 이진 표현에서 1로 설정된 비트(set bit)의 개수 n을 셉니다.
2. 하위 n개의 비트가 모두 1인 수를 만듭니다. (예: n=3이면 0b111)
3. 그 수를 왼쪽으로 (32 − n)비트만큼 시프트하여 상위 자리로 옮깁니다.

이 방식이 성립하는 이유는, 같은 개수의 1비트를 가진 수 중에서는 1들이 가장 높은 자릿수에 위치할 때 값이 최대가 되기 때문입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
unsigned getMaxNumber(unsigned num){
    int n = __builtin_popcount(num);
    if (n == 32) {
        return num;
    }
    unsigned result = (1 << n) - 1;
    return (result << (32 - n));
}
int main(){
    unsigned n = 8;
    cout << "Maximum number = " << getMaxNumber(n) << endl;
    return 0;
}

코드 설명

• __builtin_popcount(num): GCC 계열 컴파일러에서 제공하는 내장 함수로, 정수에서 1로 설정된 비트의 개수를 빠르게 반환합니다.
• (1 << n) - 1: 하위 n비트가 모두 1인 마스크를 생성합니다. 예를 들어 n이 8이면 0b11111111(255)이 됩니다.
• << (32 - n): 마스크를 왼쪽 끝으로 밀어 올려 MSB부터 1이 채워지도록 합니다.
• n이 32인 경우(모든 비트가 1)에는 이미 최댓값이므로 원래 값을 그대로 반환합니다.

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Maximum number = 2147483648

마무리

이 문제는 복잡한 정렬이나 조합 탐색 없이도 비트 개수 세기(popcount)와 시프트 연산 두 가지만으로 O(1)에 가까운 속도로 해결할 수 있습니다. 비트 조작 문제의 대표적인 패턴 중 하나이므로 코딩 테스트 준비에도 유용하게 활용할 수 있습니다.