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

C++로 k개의 설정 비트를 가진 최대 숫자를 만들기 위한 최소 비트 뒤집기 횟수

문제 설명

두 개의 정수 n과 k가 주어졌을 때, n의 비트를 뒤집어 결과 숫자가 정확히 k개의 설정 비트(set bit, 값이 1인 비트)를 갖도록 만들면서 n을 최대화하기 위해 필요한 최소 뒤집기 횟수를 구하는 문제입니다.

단, 입력은 반드시 k < n의 비트 수라는 조건을 만족해야 합니다.

예제

  • n = 9, k = 2라고 가정합니다.
  • 9의 이진 표현은 1001이며, 총 4비트로 구성되어 있습니다.
  • 4자리 이진수 중 2개의 설정 비트를 가지는 가장 큰 수는 1100, 즉 십진수 12입니다.
  • 1001을 1100으로 변환하려면 두 비트만 뒤집으면 되므로 정답은 2입니다.

알고리즘

핵심 아이디어는 간단합니다. n과 비트 길이가 같으면서 k개의 설정 비트를 가지는 가장 큰 수를 먼저 만든 뒤, 그 수와 n을 XOR 연산하여 서로 다른 비트의 개수를 세면 그것이 곧 최소 뒤집기 횟수가 됩니다.

  1. n의 비트 수를 계산합니다. math 라이브러리의 log2 함수를 활용할 수 있습니다.
    bitCount = log2(n) + 1;
  2. 하위 k비트가 모두 1인 수를 만듭니다.
    maxNum = pow(2, k) - 1; // 예: k = 2 → 11₂ = 3
  3. n과 같은 비트 길이를 갖도록 왼쪽 시프트합니다. 이렇게 하면 1들이 최상위 비트 쪽에 배치되어 해당 조건에서 가능한 최댓값이 됩니다.
    maxNum = maxNum << (bitCount - k); // 예: 11 << 2 = 1100₂ = 12
  4. XOR 결과의 설정 비트를 셉니다. n ^ maxNum에서 1인 비트의 개수가 곧 최소 뒤집기 횟수입니다.

C++ 구현

#include <iostream>
#include <cmath>
using namespace std;

// n의 설정 비트(1인 비트) 개수를 세는 함수
int getSetBits(int n){
    int cnt = 0;
    while (n) {
        ++cnt;
        n = n & (n - 1); // 가장 낮은 자리의 1비트를 하나씩 제거
    }
    return cnt;
}

int minFlipsRequired(int n, int k){
    int bitCount, maxNum, flipCount;
    bitCount = log2(n) + 1;              // n의 전체 비트 수
    maxNum = pow(2, k) - 1;              // 하위 k비트가 모두 1인 수
    maxNum = maxNum << (bitCount - k);   // n과 같은 길이의 최댓값으로 변환
    flipCount = n ^ maxNum;              // XOR로 서로 다른 비트 확인
    return getSetBits(flipCount);
}

int main(){
    cout << "Minimum required flips: " << minFlipsRequired(9, 2) << "\n";
    return 0;
}

실행 결과

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

Minimum required flips: 2

동작 과정 상세 분석 (n = 9, k = 2)

  1. bitCount = log2(9) + 1 ≈ 3.17 + 1 → 4
  2. maxNum = pow(2, 2) - 1 = 3 (이진수 11)
  3. maxNum = 3 << (4 - 2) = 12 (이진수 1100)
  4. flipCount = 9 ^ 12 = 1001₂ ^ 1100₂ = 0101₂ = 5
  5. getSetBits(5) = 2 → 최종 답은 2

복잡도 분석

시간 복잡도: O(log n) — 설정 비트 개수를 세는 과정에서 최대 비트 수만큼 반복하기 때문입니다.

공간 복잡도: O(1) — 별도의 추가 메모리를 사용하지 않습니다.