二進制與十六進制互轉 題解

簡潔題意

給一個最多 \(10^5\) 位、沒有前導零的十六進制或二進制數字串，轉成另一種進制輸出（十六進制位數字 \(10 \sim 15\) 用大寫 A ~ F），輸出不能有前導零。

解法

字串長到 \(10^5\) 位，任何內建整數型態都裝不下——不能先換算成整數再轉回去。好消息是這一對進制根本不需要換算。

關鍵是 \(2^4 = 16\)（15.2）：\(4\) 個二進制位恰好對應 \(1\) 個十六進制位，15.2 那張十六對照表就是全部的規則。整件事是純粹的「查表分組／攤開」，跟數值大小無關。

十六進制 → 二進制（\(t = 1\)）

每個十六進制位查表攤成 \(4\) 個二進制位，直接接起來。最高位那組可能以 \(0\) 開頭，最後去掉前導零即可（至少留一位，0 才印得出來）。

1F → 0001 1111 → 00011111 → 11111

二進制 → 十六進制（\(t = 2\)）

先在左邊補 \(0\) 補到長度是 \(4\) 的倍數，再每 \(4\) 位一組換回一個十六進制位（組內用 15.3 的累積式把 \(4\) 個位變回 \(0 \sim 15\) 的數值）。

11111（\(5\) 位）→ 補成 00011111（\(8\) 位）→ 0001 1111 → 1F

補零一定要補在左邊。從最左邊直接每 \(4\) 個一組分下去，等於把位值全部算錯。

常犯錯誤

  • 二進制轉十六進制時沒有左補 \(0\)（WA），直接從最左邊每 \(4\) 個一組。範例 2 會抓到這個錯
  • 十六進制轉二進制後忘記去前導零（WA），1F 印成 00011111。範例 1 會抓到這個錯
  • 想先把整個數轉成 long long 再轉回去（WA）：\(10^5\) 位遠遠超過 long long 的 \(19\) 位。範例 4 會抓到這個錯
  • 去前導零去過頭（WA），輸入 0 時印出空字串。去零迴圈的條件要保底至少留一位

參考程式碼

#include <iostream>
#include <string>
using namespace std;

// 15.2 的對照表：十六進制位 v 對應的 4 個二進制位
const string H2B[16] = {
    "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
    "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111",
};

// 進制位字元 <-> 數值（8.2）
int charToDigit(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    return c - 'A' + 10;
}
char digitToChar(int d) {
    if (d < 10) return '0' + d;
    return 'A' + (d - 10);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    string s;
    cin >> t >> s;

    string ans;
    if (t == 1) {
        // 十六進制 -> 二進制：每個十六進制位查表攤成 4 個二進制位
        for (char c : s) ans += H2B[charToDigit(c)];
    } else {
        // 二進制 -> 十六進制：左邊補 0 補到 4 的倍數，再每 4 位一組
        int pad = (4 - (int)s.size() % 4) % 4;
        string bits = string(pad, '0') + s;
        for (int i = 0; i < (int)bits.size(); i += 4) {
            int v = 0;
            for (int j = 0; j < 4; j++) v = v * 2 + (bits[i + j] - '0');   // 15.3 的累積式
            ans += digitToChar(v);
        }
    }

    int start = 0;
    while (start + 1 < (int)ans.size() && ans[start] == '0') start++;   // 去前導零，至少留一位
    cout << ans.substr(start) << '\n';
    return 0;
}

複雜度：\(O(|s|)\)。