การเข้ารหัสตัวเลขใน C++

ให้จำนวนเต็มไม่ติดลบ n ต้องการหารูปแบบเข้ารหัสตามตารางด้านล่าง:

ตัวอย่าง: 23 → "1000", 54 → "10111"

ขั้นตอนการแก้ปัญหา

1. สร้างฟังก์ชันช่วย bin(n, k) แปลง n เป็นบाइनารี ความยาว k บิต (เติม 0 ด้านหน้า)
2. ฟังก์ชันหลัก encode(n):
   • กรณีฐาน: n=0 → "", n=1 → "0", n=2 → "1"
   • x = floor(log2(n))
   • ถ้า 2^(x+1) - 1 == n (คือ n เป็น 2^k - 1) ให้คืนสตริง '0' ยาว x+1 ตัว
   • มิฉะนั้น คืน bin(n - 2^x + 1, x)

ตัวอย่างโค้ด C++

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

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

int main() {
    Solution ob;
    cout << ob.encode(23) << endl;
    cout << ob.encode(56) << endl;
}

Input

23 54

Output

1000 11001