如何在C++中无外部库将超大数字字符串转为std::vector<bool>二进制？

问题描述 #

需要将任意长度（可达数千位）的十进制数字字符串转换为std::vector<bool>存储的二进制表示（例如"12345"对应{1,1,0,0,0,0,0,0,1,1,1,0,0,1}），但现有实现仅对"0"-"9"的单数字输入有效：

• 输入"10"-"19"时结果偏差2（如"10"应得{1,0,1,0}，实际得到{1,0,0,0}）
• 输入"20"-"29"时偏差进一步增大（如"20"应得{1,0,1,0,0}，实际得到{1,0,0,0,0}）

限制条件：不能将字符串转换为int/long long等内置数值类型，禁止使用Boost等外部库。

原实现代码 #

std::vector<bool> stringToBinary(std::string num) {
        std::vector<bool> bin;
        int n = ceil(log2(pow(10, num.size())));
        for (int i = 0; i < num.size(); i++) {
            int x = num[i] - '0';
            std::vector<bool> bits;
            while (x > 0) {
                bits.push_back(x % 2);
                x /= 2;
            }
            std::reverse(bits.begin(), bits.end());
            int m = bits.size();
            for (int j = 0; j < n - 4 * i - m; j++) {
                bin.push_back(false);
            }
            for (int j = 0; j < m; j++) {
                bin.push_back(bits[j]);
            }
        }
        while (bin.size() > 1 && bin.front() == false) {
            bin.erase(bin.begin());
        }
        return bin;
    }

问题根源 #

原代码核心逻辑错误：它将每个十进制数字单独转成二进制后补位拼接，相当于把"10"拆成"1"和"0"的二进制片段拼接（得到1000），而非计算整个十进制数"10"的真实二进制值1010，完全偏离需求。

正确实现方案 #

采用模拟十进制转二进制的经典流程：反复将十进制数除以2取余数，直到数为0，最后反转余数序列得到正确二进制。由于输入是超大数字字符串，需手动模拟十进制字符串的除法操作。

#include <vector>
#include <string>
#include <algorithm>

std::vector<bool> stringToBinary(std::string num) {
    std::vector<bool> bin;
    // 处理特殊输入："0"
    if (num == "0") {
        bin.push_back(false);
        return bin;
    }

    while (num != "0") {
        int remainder = 0;
        std::string new_num;
        // 模拟十进制字符串除以2的过程
        for (char c : num) {
            int digit = c - '0';
            int current = remainder * 10 + digit;
            int quotient = current / 2;
            remainder = current % 2;
            // 避免生成前导零，仅当已有内容或商不为0时添加
            if (!new_num.empty() || quotient != 0) {
                new_num.push_back(quotient + '0');
            }
        }
        // 余数是当前二进制的最低位，先存入向量
        bin.push_back(remainder == 1);
        // 更新num为除法后的商，若商为空则设为"0"
        num = new_num.empty() ? "0" : new_num;
    }

    // 反转向量，得到从高位到低位的二进制顺序
    std::reverse(bin.begin(), bin.end());
    return bin;
}

代码说明 #

1. 模拟除法：遍历数字字符串的每个字符，结合前一位的余数计算当前位的商和新余数，商组成新的数字字符串（即除以2后的结果）。
2. 收集余数：每次除法得到的余数是二进制的最低位，先存入向量，最后反转得到高位在前的正确顺序。
3. 特殊处理：单独处理输入"0"的情况，避免返回空向量；同时在生成新数字字符串时跳过前导零，保证后续计算的正确性。

验证示例 #

• 输入"10"：经过四次除法得到余数序列[0,1,0,1]，反转后得到[1,0,1,0]，符合预期。
• 输入"20"：五次除法得到余数序列[0,0,1,0,1]，反转后得到[1,0,1,0,0]，符合预期。

内容的提问来源于stack exchange，提问作者Liam Goss