如何从任意大的任意基地转换为另一个

Question

我想要做的是将一个字符串从一个"字母"转换为另一个,就像在基数之间转换数字,但更抽象和任意数字.

例如,将"255"从字母"0123456789"转换为字母"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".

这适用于小字母,但我希望能够使用base 26(所有大写字母)或base 52(大写和小写)或base 62(大写,小写和数字),以及可能超过a的值百位数.从理论上讲,上面的算法可以用于这样的字母表,但是,在实践中,我遇到了整数溢出,因为当你开始做62 ^ 100时数字变得如此之快.

我想知道的是,如果有一个算法来做这样的转换而不必跟上这样巨大的整数？也许是在处理整个输入字符串之前开始输出结果的方法？

我的直觉告诉我,这可能是可能的,但我的数学技能缺乏.任何帮助,将不胜感激.

StackOverflow上有一些类似的问题,但似乎没有一个正是我正在寻找的.

Answer 1

以任意基数存储数字的通用方法是将其存储为整数数组。至少，一个数字将由一个基数和代表该基数中不同数字的 int 数组（或短或长，取决于您想要的基数范围）来表示。

接下来，您需要在该任意基数上实现乘法。

之后就可以实现转换了（提示：如果x是旧基数，则在新基数中计算x，x^2，x^3，...，然后将旧基数中的数字相应地乘以这些数字，然后将它们加起来）。