Tối đa hóa số không dấu bằng cách hoán đổi bit tại vị trí cực trị trong C++

Đề bài

Cho số không dấu. Tối đa hóa nó bằng cách hoán đổi bit tại các vị trí đối xứng: bit 0 ↔ bit 31, bit 1 ↔ bit 30, ... (giả sử 32-bit).

Ví dụ: 8 = 0b...00001000 → sau hoán đổi: 0b00010000...0 = 268435456 (bit 1 từ vị trí 3 chuyển lên vị trí 28).

Thuật toán

1. Duyệt cặp bit (i, 31-i) với i từ 0 đến 15.
2. Nếu bit thấp (i) = 1 và bit cao (31-i) = 0 → hoán đổi (XOR với mask có 1 tại hai vị trí đó).
3. Nếu bit thấp = 0, bit cao = 1 → giữ nguyên (đã tối ưu).
4. Nếu cả hai bằng nhau → không thay đổi.

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

#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;

ull getMaxNumber(ull num) {
    ull orig = num;
    int bits = sizeof(ull) * 8; // 64 trên hệ 64-bit, 32 trên 32-bit
    for (int i = 0; i < bits/2; ++i) {
        int low = (orig >> i) & 1;
        int high = (orig >> (bits - 1 - i)) & 1;
        if (low > high) {
            ull mask = (1ull << i) | (1ull << (bits - 1 - i));
            num ^= mask; // flip both bits
        }
    }
    return num;
}

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

Kết quả

So lon nhat = 268435456

Lưu ý: Kết quả phụ thuộc vào kích thước kiểu (32-bit vs 64-bit). Code dùng sizeof(ull)*8 để tự động thích ứng.