任意进制大数转换

问题描述：将用字符串表示的M进制大数，转化为用字符串表示的N进制大数。1<M,N<=62;字符串的取值为[0-9a-zA-Z]，例如B表示数字37。

1、受位数限制的方案

关于此问题，最简单的实现方式是先将M进制的大数转化为long long类型的10进制整数，然后再辗转相除求出，N进制的大数字符串。

void reverse(string& srcNum){
    size_t i = 0, j = srcNum.size() - 1;
    char temp = 0;
    while (i < j){
        temp = srcNum[i];
        srcNum[i++] = srcNum[j];
        srcNum[j--] = temp;
    }
}

string m2n_constrait(int srcBase, int desBase, string srcNum){
    if (srcBase > 62 || srcBase < 2 || desBase > 62 || desBase < 2)
        return "";
    char flag[63] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    string desNum;
    long long midNum = 0, temp = 0;
    for (size_t i = 0; i < srcNum.size(); ++i){
        if (srcNum[i] >= '0' && srcNum[i] <= '9')
            temp = srcNum[i] - '0';
        else if (srcNum[i] >= 'a' && srcNum[i] <= 'z')
            temp = srcNum[i] - 'a' + 10;
        else if (srcNum[i] >= 'A' && srcNum[i] <= 'Z')
            temp = srcNum[i] - 'A' + 36;
        else return "";
        midNum = midNum * srcBase + temp;
    }   
    while (midNum){
        desNum.push_back(flag[midNum % desBase]);
        midNum /= desBase;
    }
    reverse(desNum);
    return desNum;
}

2、通用方案

此方案直接对原数据，用目标进制n直接进行辗转相除，取商和取余，逐步求解每一位最终结果。实现起来较为复杂，下面以一个简单的例子来说明其详细过程：要求将32进制的45转化为9进制的数字

• 判断4是否大于9，不是，所以不进行辗转除
• 4*32 + 5 = 133，此时大于9， 由于 133 mod 9 = 7, 133 / 9 = 14 （即e）；将e转至中间结果
• 第一轮循环结束，将上一步的余数7存至最终结果，进行下一轮转化（此时转化e）
• 判断e是否大于9，将e / 9 = 1， e mod 9 = 5；将1存至中间变量
• 第二轮循环结束，将上一步的余数5存至最终结果，进行下一轮转化（此时转化1）
• 判断1是否大于9，由于1小于9，不再有中间结果
• 第三轮循环结束，将上一步的余数1存至最终结果
• 将最终结果751逆序，得到最终结果157

void reverse(string& srcNum){
    size_t i = 0, j = srcNum.size() - 1;
    char temp = 0;
    while (i < j){
        temp = srcNum[i];
        srcNum[i++] = srcNum[j];
        srcNum[j--] = temp;
    }
}
bool isZero(string& srcNum){
    for (size_t i = 0; i<srcNum.size(); ++i){
        if (srcNum[i] != '0')
            return false;
    }
    return true;
}
string m2n(int srcBase, int desBase, string srcNum){
    if (srcBase > 62 || srcBase < 2 || desBase > 62 || desBase < 2)
        return "";
    char flag[63] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    string desNum, midNum;
    long long temp = 0, carry = 0;
    while (!srcNum.empty() && !isZero(srcNum) ){
        for (size_t i = 0; i < srcNum.size(); ++i){
            if (srcNum[i] >= '0' && srcNum[i] <= '9')
                temp = srcNum[i] - '0';
            else if (srcNum[i] >= 'a' && srcNum[i] <= 'z')
                temp = srcNum[i] - 'a' + 10;
            else if (srcNum[i] >= 'A' && srcNum[i] <= 'Z')
                temp = srcNum[i] - 'A' + 36;
            else return "";
            carry = carry * srcBase + temp;
            if (carry / desBase != 0 || i == srcNum.size() - 1){
                midNum.push_back(flag[carry / desBase]);
                carry %= desBase;
            }
        }
        desNum.push_back(flag[carry]);
        srcNum = midNum;
        carry = 0;
        midNum.clear();
    }
    reverse(desNum);
    return desNum;
}