C++ 實現十進制轉任意進制 (2-36) 通用算法：除基取餘法與字符映射表

十進制整數轉任意進制 (2-36) 的核心算法是**除基取餘，逆序輸出**。本文給出完整、健壯的 C++ 實現：支持負數、0、大數、自定義字符集、標準庫風格接口，並分析邊界情況與優化方向。

算法原理：除基取餘法

將十進制數 N 反覆除以目標進制 base，記錄餘數，直到商為 0。餘數序列**逆序**即為目標進制表示。

十進制 11 → 二進制 (base=2)          十進制 11 → 三進制 (base=3)
11 / 2 = 5 ... 1                       11 / 3 = 3 ... 2
 5 / 2 = 2 ... 1                        3 / 3 = 1 ... 0
 2 / 2 = 1 ... 0                        1 / 3 = 0 ... 1
 1 / 2 = 0 ... 1
餘數逆序: 1011                         餘數逆序: 102 (1×9+0×3+2=11)

通用實現 (C++17)

#include <string>
#include <algorithm>
#include <stdexcept>
#include <cstdint>

std::string ToBase(int64_t value, int base, const std::string& digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ") {
    if (base < 2 || base > static_cast<int>(digits.size()))
        throw std::invalid_argument("base out of range [2, digits.size()]");

    if (value == 0) return "0";

    bool negative = value < 0;
    // 處理 INT64_MIN 絕對值溢出：用無符號運算
    uint64_t n = negative ? static_cast<uint64_t>(-(value + 1)) + 1 : static_cast<uint64_t>(value);

    std::string result;
    while (n > 0) {
        result.push_back(digits[static_cast<size_t>(n % base)]);
        n /= base;
    }
    if (negative) result.push_back('-');
    std::reverse(result.begin(), result.end());
    return result;
}

// 便捷重載：默認 0-9A-Z 支持至 36 進制
std::string ToBase(int64_t value, int base) {
    return ToBase(value, base);
}

關鍵細節解析

測試驗證

#include <iostream>
int main() {
    auto test = [](int64_t v, int b) {
        std::string s = ToBase(v, b);
        // 反向驗證：std::stoll(s, nullptr, b) 應等於 v (base≤36)
        std::cout << v << " (10) = " << s << " (" << b << ")\n";
    };

    test(11, 2);    // 1011
    test(11, 3);    // 102
    test(17, 8);    // 21
    test(100, 16);  // 64
    test(32, 4);    // 200
    test(-255, 16); // -FF
    test(0, 2);     // 0
    test(INT64_MAX, 36); // 大數測試

    return 0;
}

進階：任意精度大整數 (Boost.Multiprecision)

#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;

std::string ToBaseBig(cpp_int value, int base) {
    const std::string digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    if (base < 2 || base > 36) throw std::invalid_argument("base");
    if (value == 0) return "0";
    bool neg = value < 0;
    if (neg) value = -value;
    std::string res;
    while (value > 0) {
        res.push_back(digits[static_cast<size_t>((value % base).convert_to<int>())]);
        value /= base;
    }
    if (neg) res.push_back('-');
    std::reverse(res.begin(), res.end());
    return res;
}

標準庫替代方案 (C++11+)

• std::bitset：固定寬度二進制輸出。
• std::to_string + std::stoll(str, nullptr, base)：僅限 2-36 進制解析，**無標準庫函數直接生成任意進制字符串**。
• printf 族：%x (16)、%o (8)、**無通用進制格式符**。

**結論**：手寫 ToBase 是通用、可控、無依賴的最佳選擇。

常見面試變體

1. **不使用除法/取模**：位運算實現 2/4/8/16 進制 (移位 + 掩碼)。
2. **遞歸寫法**：void print(int n, int b) { if (n/b) print(n/b, b); putchar(digits[n%b]); }。
3. **浮點數轉進制**：整數部分餘數法，小數部分**乘基取整**法。