C++ 二進制整數轉十進制：遞歸算法、位權原理與完整實現

二進制轉十進制是計算機科學基礎課程核心內容，也是面試高頻手寫算法。本文從位權數學原理出發，推導遞歸與迭代兩種算法，提供完整 C++ 實現，並延伸討論任意進制轉換、大整數處理、編譯期計算與現代 C++ 標準庫方案。

一、數學原理：位權展開

二進制數 b_{n-1} b_{n-2} ... b_1 b_0 (每位 b_i ∈ {0,1}) 的十進制值：

Value = Σ_{i=0}^{n-1} b_i × 2^i
      = b_0×2^0 + b_1×2^1 + b_2×2^2 + ... + b_{n-1}×2^{n-1}

範例：101₂ → 5₁₀

位權:  2²  2¹  2⁰
二進制: 1   0   1
計算:  1×4 + 0×2 + 1×1 = 4 + 0 + 1 = 5

二、遞歸算法推導

核心洞察

設 B(n) 為 n 位二進制數的十進制值，考慮最低位：

B(n) = (高位部分值) × 2 + 最低位值
     = B(n-1) × 2 + b_0

遞歸定義

bin2dec(0) = 0
bin2dec(x) = bin2dec(x / 10) * 2 + (x % 10)   // x 為十進制整數形式的二進制數

執行追蹤：101

bin2dec(101)
= bin2dec(10) * 2 + 1
= (bin2dec(1) * 2 + 0) * 2 + 1
= ((bin2dec(0) * 2 + 1) * 2 + 0) * 2 + 1
= ((0 * 2 + 1) * 2 + 0) * 2 + 1
= (1 * 2 + 0) * 2 + 1
= 2 * 2 + 1
= 5

三、C++ 完整實現

1. 遞歸版本 (原文算法)

#include <iostream>
#include <stdexcept>
#include <climits>

long long bin2decRecursive(int binary) {
    // 輸入驗證：確保只包含 0/1
    int temp = binary;
    while (temp > 0) {
        int digit = temp % 10;
        if (digit != 0 && digit != 1) 
            throw std::invalid_argument("Input contains non-binary digits");
        temp /= 10;
    }
    
    if (binary == 0) return 0;
    return bin2decRecursive(binary / 10) * 2 + (binary % 10);
}

2. 迭代版本 (效能更優、無棧溢出風險)

long long bin2decIterative(int binary) {
    long long result = 0;
    long long power = 1;  // 2^0
    
    while (binary > 0) {
        int digit = binary % 10;
        if (digit != 0 && digit != 1) 
            throw std::invalid_argument("Non-binary digit");
        result += digit * power;
        power <<= 1;  // power *= 2
        binary /= 10;
    }
    return result;
}

3. 字串輸入版本 (支援任意長度、前導零)

#include <string>
#include <cctype>

long long bin2decString(const std::string& binaryStr) {
    long long result = 0;
    for (char ch : binaryStr) {
        if (ch != '0' && ch != '1') 
            throw std::invalid_argument("Invalid binary string");
        result = (result << 1) + (ch - '0');  // result * 2 + digit
    }
    return result;
}

4. 完整測試程式

int main() {
    std::cout << "請輸入一個二進制數: ";
    std::string input;
    std::cin >> input;
    
    try {
        // 方法 1: 字串版本 (推薦)
        long long decimal = bin2decString(input);
        std::cout << "十進制結果: " << decimal << '\n';
        
        // 方法 2: 整數版本 (若輸入較小)
        if (input.length() <= 10) {  // int 範圍內
            int binaryInt = std::stoi(input);
            std::cout << "遞歸結果: " << bin2decRecursive(binaryInt) << '\n';
            std::cout << "迭代結果: " << bin2decIterative(binaryInt) << '\n';
        }
    } catch (const std::exception& e) {
        std::cerr << "錯誤: " << e.what() << '\n';
    }
    return 0;
}

四、效能與限制分析

溢出邊界

• int (32 位)：最大二進制 1111111111111111111111111111111 (31 位) → 2,147,483,647
• long long (64 位)：最大 63 位二進制 → 9,223,372,036,854,775,807
• 超過範圍需用大整數庫 (Boost.Multiprecision, GMP) 或自實現

五、擴展：任意進制轉十進制通用算法

通用位權公式

Value = Σ digit_i × base^i

通用迭代實現

long long anyBaseToDec(const std::string& str, int base) {
    if (base < 2 || base > 36) throw std::invalid_argument("Base 2-36");
    
    long long result = 0;
    for (char ch : str) {
        int digit;
        if (ch >= '0' && ch <= '9') digit = ch - '0';
        else if (ch >= 'A' && ch <= 'Z') digit = ch - 'A' + 10;
        else if (ch >= 'a' && ch <= 'z') digit = ch - 'a' + 10;
        else throw std::invalid_argument("Invalid character");
        
        if (digit >= base) throw std::invalid_argument("Digit >= base");
        result = result * base + digit;
    }
    return result;
}

六、現代 C++ 標準庫方案

C++11 stoi/stoll (支援基數)

#include <string>

int main() {
    std::string bin = "101010";
    int dec = std::stoi(bin, nullptr, 2);   // 基數 2
    long long dec2 = std::stoll(bin, nullptr, 2);
    std::cout << dec << '\n';  // 42
}

C++17 std::from_chars (高效能、無異常、無區域相關)

#include <charconv>
#include <string_view>

int main() {
    std::string bin = "101010";
    int value = 0;
    auto result = std::from_chars(bin.data(), bin.data() + bin.size(), value, 2);
    if (result.ec == std::errc()) {
        std::cout << value << '\n';  // 42
    }
}

C++20 格式化輸出

#include <format>
#include <bitset>

int main() {
    int dec = 42;
    std::cout << std::format("二進制: {:b}\n", dec);  // 101010
    std::cout << std::format("八進制: {:o}\n", dec);  // 52
    std::cout << std::format("十六進制: {:x}\n", dec); // 2a
    
    // 編譯期位運算
    constexpr std::bitset<8> bits(42);
    std::cout << bits << '\n';  // 00101010
}

七、編譯期計算 (模板元編程)

// C++11 constexpr 遞歸
constexpr long long bin2decConstexpr(long long binary) {
    return binary == 0 ? 0 : bin2decConstexpr(binary / 10) * 2 + binary % 10;
}

// C++14 變長模板編譯期字串解析
template <char... Chars>
constexpr long long bin2decLiteral() {
    long long result = 0;
    (void)std::initializer_list<int>{ 
        (result = result * 2 + (Chars - '0'), 0)... 
    };
    return result;
}

// 使用
constexpr auto val = bin2decLiteral<'1','0','1','0','1','0'>();  // 編譯期計算 42
static_assert(val == 42);

八、面試高頻考點總結

1. 手寫遞歸/迭代轉換：邊界條件、輸入驗證、溢出處理
2. 位權原理：Σ b_i × 2^i 及其遞歸形式 f(n) = f(n-1)×2 + b_0
3. 字串 vs 整數輸入：字串支援任意長度、前導零、易驗證
4. 標準庫函數：stoi(s, nullptr, 2), from_chars, bitset
5. 編譯期計算：constexpr、模板元編程、用戶定義字面量
6. 大整數擴展：向量/字串模擬、Boost.Multiprecision cpp_int

九、總結

二進制轉十進制的核心是**位權展開**與**霍納法則** (Horner's Method) 的遞歸形式：

result = ((b_{n-1} × 2 + b_{n-2}) × 2 + ... ) × 2 + b_0

工程選擇指南：

• ✅ **生產代碼**：std::from_chars (C++17) 或 stoll(s, nullptr, 2) (C++11)
• ✅ **嵌入式/無標準庫**：迭代版本 result = result * 2 + digit
• ✅ **教學/面試**：遞歸版本展示數學歸納法思維
• ✅ **編譯期需求**：constexpr 函數或模板元編程
• ✅ **超大整數**：Boost.Multiprecision cpp_int 或自實現大整數類

掌握進制轉換的數學本質、算法變體與標準庫工具，不僅能應對面試考察，更能在協議解析、編譯器開發、嵌入式程式設計、密碼學等領域靈活處理各種數值表示轉換需求。