C++에서 n개의 설정 비트와 m개의 미설정 비트를 가진 가장 큰 수 찾기

이 문제에서는 두 개의 정수 값 n과 m이 주어지며, 숫자의 이진 표현에서 n개의 설정 비트(set bit)와 m개의 미설정 비트(unset bit)를 가진 가장 큰 수를 찾는 것이 목표입니다.

문제 이해를 위한 예시

입력 : n = 3, m = 1
출력 : 14

설명 −

가장 큰 수는 상위 비트에 설정 비트 3개가 있고, 그 아래에 미설정 비트 1개가 위치한 형태입니다.
(1110)2 = 14

해결 접근 방식

이 문제를 해결하는 간단한 방법은 다음과 같습니다. 먼저 (n+m)개의 설정 비트로만 이루어진 수를 만든 뒤, 최하위 비트(LSB) 쪽부터 m개의 비트를 반전(toggle)시켜 끄는 것입니다.

(n+m)개의 설정 비트를 가진 수는 다음 비트 연산으로 손쉽게 만들 수 있습니다.

$$(1\ll(n+m))-1$$

여기서 (1 << (n+m))은 1을 왼쪽으로 (n+m)비트 시프트한 값이므로, 여기서 1을 빼면 하위 (n+m)비트가 모두 1인 수가 됩니다. 예를 들어 n+m이 7이라면 1111111₂, 즉 127이 됩니다.

다음으로, 하위 m개의 비트만 1인 마스크 (1 << m) - 1을 만들고, 앞에서 구한 수와 XOR(^) 연산을 수행합니다. XOR 연산은 서로 같은 비트가 만나면 0이 되기 때문에, 하위 m개의 비트가 0으로 반전되어 원하는 형태의 수를 얻을 수 있습니다.

예제 코드

아래 프로그램은 위에서 설명한 해결 방법의 동작을 보여줍니다.

#include <iostream>
using namespace std;
int findlargestNumber(int n, int m){
   int maxNum = (1 << (n + m)) - 1;
   if (m == 0)
      return maxNum;
   int number = (1 << m) - 1;
   return (maxNum ^ number);
}
int main(){
   int n = 5,
   m = 2;
   cout<<"설정 비트 "<<n<<"개와 미설정 비트 "<<m<<"개를 가진 가장 큰 수는 "<<findlargestNumber(n, m);
   return 0;
}

출력

설정 비트 5개와 미설정 비트 2개를 가진 가장 큰 수는 124

실행 결과를 살펴보면, n = 5, m = 2일 때 (n+m) = 7개의 설정 비트를 가진 127(1111111₂)에서 하위 2개의 비트를 반전시켜 124(1111100₂)를 얻습니다. 이 수는 상위 5개의 설정 비트와 하위 2개의 미설정 비트를 가지며, 주어진 조건을 만족하는 가장 큰 수입니다.