Tối đa hóa số lượng bằng cách sắp xếp lại các bit trong C ++

Tuyên bố vấn đề

Cho một số không dấu, hãy tìm số tối đa có thể được tạo thành bằng cách sử dụng các bit của số không dấu đã cho

Nếu số đầu vào là 8 thì biểu diễn nhị phân của nó là−

00000000000000000000000000001000

Để tối đa hóa nó, hãy đặt MSB thành 1. Sau đó, số trở thành 2147483648 có biểu diễn nhị phân là−

10000000000000000000000000000000

Thuật toán

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)

Ví dụ

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

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau−

Maximum number = 2147483648