c - 如何将给定基数中任意长度整数的字符串表示形式转换为十进制？

Question

我想知道如何将字符串表示的某个基数 b 中的任意长度整数转换为基数 10 的字符串表示形式。

举个例子，如果我发送字符串“4552”，并且还发送它以 8 为基数，我想将此字符串转换为以 10 为基数并返回该字符串，但我不能使用 atoi 或 strtol 因为如果我发送 312434324324324324324324 这是不可能的，我首先认为你可以像经典的递归算法一样使用使用数字 % 10 递归直到最后一个数字，然后反向将数字放入字符串中。

无论如何，我实际上有点迷失了，我不知道这怎么可能，如果你们有任何提示或方法我可以做到这一点。我向您提供了我的函数的原型(prototype)，以便您了解基础知识，谢谢。

char *to_base_10(char *nb, int base)
{
    int size = my_strlen(nb);
}

Answer 1

对于长度为 L 且包含基本 b 数字的无符号数字字符串 n，“笔和纸” “解决方案是:

n_dec = n₀ x b^L-1 + n₁ x b ^L-2 + ... + n_L-1 x b⁰

(其中 n₀ 是最重要的 - 即左侧 - 数字，n_L-1 最低有效数字 - 即下标与 C 数组顺序相同)。

因此将其分解为您需要实现任意长度整数操作的操作:

• 求幂 (x^y)
• 乘法
• 添加

由于最粗略的(我建议您从这里开始)乘法可以通过重复加法来执行，求幂可以通过重复乘法来执行，因此您只需要实现加法。性能改进，例如长乘法和平方求幂可能要等到您掌握基础知识之后(并确定简单的解决方案甚至太慢)。

因此，“笔和纸”的加法解决方案相对简单(对于A + B，将数字从n = LSD 迭代到MSD+1，执行A _n + B_n + Carry_n-1)，并且可以在代码中实现任意长度的字符串。

由此，通过重复加法(最初)实现乘法，然后通过重复乘法实现乘幂。

然后最终通过从 n _{迭代实现上面的转十进制表达式 ndec = ...使用您的任意长度整数运算从0}到n_L-1。

验证一些短测试字符串，然后在必要时通过更复杂的乘法和求幂方法进行优化，根据原始验证测试数据测试此改进。