如何将任意大的进制转换为另一个进制

Question

我想做的是将一个字符串从一种“字母表”转换为另一种，就像在不同进制之间转换数字一样，但更抽象且具有任意数字。

例如，将来自字母表“0123456789”的“255”转换为字母表“0123456789ABCDEF”将得到“FF”。一种方法是将输入字符串转换为整数，然后再转换回来。如下所示：（伪代码）

int decode(string input, string alphabet) {
  int value = 0;
  for(i = 0; i < input.length; i++) {
    int index = alphabet.indexOf(input[i]);
    value += index * pow(alphabet.length, input.length - i - 1);
  }
  return value;
}

string encode(int value, string alphabet) {
  string encoded = "";
  while(value > 0) {
    int index = value % alphabet.length;
    encoded = alphabet[index] + encoded;
    value = floor(value / alphabet.length);
  }
  return encoded;
}

这样，decode("255", "0123456789")返回整数255，encode(255, "0123456789ABCDEF")返回"FF"。

这对于小字母表有效，但我想使用基础26（所有大写字母）或基础52（大写和小写）或基础62（大写，小写和数字），以及可能超过一百位数的值。理论上，上面的算法可以用于这样的字母表，但实际上，当您开始执行62 ^ 100时，数字变得如此之大，因此会遇到整数溢出问题。

我想知道是否有一种算法可以进行这样的转换，而不必跟踪如此巨大的整数？也许有一种方法可以在整个输入字符串被处理之前开始输出结果？

我的直觉告诉我这可能是可能的，但我的数学技能不足。任何帮助都将不胜感激。

这里有几个类似的问题，但没有一个完全符合我的要求。

- Erik R.

---

如果您想将其存储为整数，则需要使用“bigint”数学库（例如Boost.Multiprecision）。此外，std::strtol()可以处理最多36进制（数字加字母，不区分大小写），但要注意溢出。 - metal

为什么需要一次转换整个字符串，而不是单个字符？这是优化的尝试吗？ - Tyler Durden

好问题。我相信有一个数学公式可以解决它，但问题是它是否可行。 - Hot Licks

如果你能找到一个（相对较小的）值V，其中V = base1的N1次方且V = base2的N2次方，其中所有值都是整数，那么你可以分部完成它。 - Hot Licks

Answer 1

一种在任意进制下存储数字的通用方法是将其作为整数数组存储。最少需要使用一个基数和整数数组（或短整型或长整型，具体取决于所需基数的范围）来表示该基数下不同数字。

接下来，您需要在该任意进制下实现乘法。

之后，您可以实现转换（提示：如果x是旧基数，则计算新基数下的x、x^2、x^3等。之后，根据这些数字相应地乘以旧基数中的数字，再将它们相加）。

- ElKamina

Answer 2

类似Java的伪代码：

ArbitraryBaseNumber source = new ArbitraryBaseNumber(11,"103A"); 
ArbitraryBaseNumber target = new ArbitraryBaseNumber(3,"0");

for(int digit : base3Num.getDigitListAsIntegers()) { // [1,0,3,10]
    target.incrementBy(digit);
    if(not final digit) {
        target.multiplyBy(source.base);
    }
}

当然，仍然存在的挑战是实现ArbitraryBaseNumber，具有“incrementBy（int）”和“multiplyBy（int）”方法。 本质上，在代码中执行的内容与学童在纸上进行加法和长乘法时所做的完全相同。 搜索Google，你会找到例子。

- slim