C++로 최대 K개의 세트 비트를 가진 X 이하의 가장 큰 수 찾기

이 튜토리얼에서는 주어진 수 x보다 작거나 같은 수 중에서, 최대 k개의 세트 비트(set bit, 1로 설정된 비트)만을 가지는 가장 큰 수를 찾는 프로그램을 작성해 보겠습니다.

핵심 아이디어는 간단합니다. x의 세트 비트 개수가 이미 k 이하라면 그대로 반환하면 되고, 그렇지 않다면 낮은 자리의 세트 비트부터 하나씩 제거하여 세트 비트 개수를 k개로 줄이는 것입니다.

문제 해결 접근 방법

• 숫자 x와 k를 초기화합니다.
• x에 포함된 세트 비트의 개수를 구합니다.
• (세트 비트 개수 − k)번 반복하는 루프를 실행하며, 매 반복마다 x & (x - 1) 연산으로 x를 업데이트합니다.
• 최종적으로 얻어진 x를 반환합니다.

x & (x - 1) 연산은 x에서 가장 낮은 자리의 세트 비트를 제거하는 널리 알려진 비트 조작 기법입니다. 따라서 이 연산을 (세트 비트 개수 − k)번 수행하면, 상위 자리의 비트들은 그대로 유지되면서 세트 비트가 정확히 k개 이하인 가장 큰 수를 얻을 수 있습니다.

예제 코드

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

int largestNumberWithKBits(int x, int k) {
    int set_bit_count = __builtin_popcount(x);
    if (set_bit_count <= k) {
        return x;
    }
    int diff = set_bit_count - k;
    for (int i = 0; i < diff; i++) {
        x &= (x - 1);
    }
    return x;
}

int main() {
    int x = 65, k = 2;
    cout << largestNumberWithKBits(x, k) << endl;
    return 0;
}

코드 설명

• __builtin_popcount(x): GCC에서 제공하는 내장 함수로, x의 이진 표현에서 1로 설정된 비트의 개수를 반환합니다.
• x의 세트 비트 개수가 k 이하라면 조건을 이미 만족하므로 x를 그대로 반환합니다.
• 그렇지 않은 경우, 초과분(diff)만큼 x &= (x - 1)을 반복하여 낮은 자리의 세트 비트를 차례대로 제거합니다.

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

65

x = 65는 이진수로 1000001₂이며, 세트 비트가 2개이므로 k = 2 조건을 이미 만족합니다. 따라서 별도의 비트 제거 없이 그대로 65가 출력됩니다.

마무리

이처럼 x & (x - 1) 연산만 활용하면 복잡한 탐색 없이도 O(log n) 시간 안에 원하는 답을 구할 수 있습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.