Số tối thiểu sử dụng tập hợp các bit của một số nhất định trong C ++

Tuyên bố vấn đề

Cho một số không dấu, hãy tìm số tối thiểu 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.

Ví dụ

Nếu input =10 thì câu trả lời sẽ là 3

Biểu diễn nhị phân của 10 là 1010 và số tối thiểu có 2 bit đặt là 0011, tức là 3

Thuật toán

1. Count the number of set bits.
2. (Number of set bits) ^ 2 – 1 represents the minimized number)

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int getSetBits(int n) {
   int cnt = 0;
   while (n) {
      ++cnt;
      n = n & (n - 1);
   }
   return cnt;
}
int getMinNumber(int n){
   int bits = getSetBits(n);
   return pow(2, bits) - 1;
}
int main() {
   int n = 10;
   cout << "Minimum number = " << getMinNumber(n) << endl;
   return 0;
   return 0;
}

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

Đầu ra

Minimum number = 3