C++에서 비트를 재배열하여 수 최대화

문제 설명

부호 없는 숫자가 주어졌을 때 주어진 부호 없는 숫자의 비트를 사용하여 만들 수 있는 최대 수를 구하십시오.

입력 숫자가 8이면 이진 표현은 다음과 같습니다.

00000000000000000000000000001000

최대화하려면 MSB를 1로 설정합니다. 그러면 숫자는 2147483648이 되고 이진 표현은 -

10000000000000000000000000000000

알고리즘

1. Count number of set bits in the binary representation of a given number
2. Find a number with n least significant set bits
3. shift the number left by (32 – n)

예시

#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;
}

출력

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다-

Maximum number = 2147483648