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

Đề bài

Cho số không dấu, tìm số lớn nhất có thể tạo bằng cách sắp xếp lại các bit của nó.

Ví dụ: 8 = 0b1000 → đưa bit 1 lên MSB → 0b1000...0 = 2³¹ = 2147483648 (32-bit).

Thuật toán

1. Đếm số bit 1: n = __builtin_popcount(num).
2. Tạo số có n bit 1 ở LSB: (1 << n) - 1.
3. Dịch trái (32 - n) vị trí để đưa các bit 1 lên MSB.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

unsigned getMaxNumber(unsigned num) {
    int n = __builtin_popcount(num);
    if (n == 32) return num; // tất cả bit 1
    unsigned res = (1u << n) - 1; // n bit 1 ở LSB
    return res << (32 - n);       // dịch lên MSB
}

int main() {
    unsigned n = 8;
    cout << "So lon nhat = " << getMaxNumber(n) << endl;
    return 0;
}

Kết quả

So lon nhat = 2147483648