Số nhỏ nhất dùng các bit set của số cho trước trong C++

Đề bài

Cho một số không dấu, tìm số nhỏ nhất có thể tạo bằng cách sử dụng các bit của số không dấu cho trước.

Ví dụ

Nếu đầu vào = 10 thì đáp án là 3

Biểu diễn nhị phân của 10 là 1010 và số nhỏ nhất với 2 bit set là 0011 tức 3

Thuật toán

1. Đếm số bit set.
2. (Số bit set) ^ 2 - 1 biểu thị số nhỏ nhất.

Ví dụ mã C++

#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 << "Số nhỏ nhất = " << getMinNumber(n) << endl;
    return 0;
}

Khi biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra sau

Đầu ra

Số nhỏ nhất = 3