Mã hóa số nguyên trong C++

Mô tả bài toán

Cho số nguyên không âm n, mã hóa thành chuỗi nhị phân đặc biệt theo quy tắc:

Ví dụ: 23 → "1000", 54 → "10111" (trong bài gốc có lỗi in ra 11001 cho 54).

Giải thuật

Đây thực chất là mã hóa số nhị phân có độ dài biến đổi (giống Elias gamma coding).

1. Nếu n = 0 trả về rỗng; n = 1 trả về "0"; n = 2 trả về "1".
2. Tìm x = floor(log2(n)).
3. Nếu n = 2^(x+1) - 1 (dạng 2^k - 1), trả về chuỗi x+1 ký tự '0'.
4. Ngược lại, mã hóa n - 2^x + 1 thành nhị phân độ dài x bit (đệm 0 đầu nếu cần).

Cài đặt C++

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

class Solution {
    string bin(int n, int len) {
        string res;
        while (n > 0) {
            res.push_back('0' + (n & 1));
            n >>= 1;
        }
        reverse(res.begin(), res.end());
        while (res.size() < len) res = '0' + res;
        return res;
    }
public:
    string encode(int n) {
        if (n == 0) return "";
        if (n == 1) return "0";
        if (n == 2) return "1";
        int x = 31 - __builtin_clz(n); // floor(log2(n))
        if ((1 << (x+1)) - 1 == n) {
            return string(x+1, '0');
        }
        return bin(n - (1 << x) + 1, x);
    }
};

int main() {
    Solution ob;
    cout << ob.encode(23) << ' ' << ob.encode(54); // 1000 10111
    return 0;
}

Độ phức tạp

• Thời gian: O(log n).
• Không gian: O(log n) cho chuỗi kết quả.