大数任意进制转换

大数任意进制转换

项目中有地方需要将 16 进制的大数转换成 10 进制的大数，实际在发现网上很多计算器在大数太大的时候会丢失精度（比如：js 中规定安全整数的范围是 -2^53 ~ 2^53，所以大于 9007199254740991 的数进制转换会存在精度问题），所以得自己按照逻辑实现一个 C 语言版本的大数进制转换，这其实是 oj 平台算法题里面的题目，因为曾经做过大数类的题目，所以实现起来还是比较简单的。

转换原理

大数和普通数据的转换原则都是 “模 n 取余法”，其中先余为低位，后余为高位。到这步可能就想要实现一个大数除法了，但是因为可见字符数量比较少，实际上除数并不可能是一个大数，目前能用的一般都是 2 - 62 进制，对应着 0-9，a-z，A-Z，即区分英文字母大小写。大数所使用的模 n 取余法和普通书使用的模 n 取余法原理是一样的但是形态是不一样的。

基本模 n 取余法：

10 进制数 12 转换为 2 进制 1100

计算过程：
12 / 2 = 6 ..... 余 0
6 / 2 = 3 ..... 余 0
3 / 2 = 1 ..... 余 1
1 / 2 = 0 ..... 余 1

按照先余为低位，后余为高位，则 2 进制是 1100。

大数模 n 取余法算法描述：

2 进制大数 1011 转换为 3 进制大数 102

计算过程：

先取最低位余数

1. 按次序从大数 1011 中取数，取出数为 1
2. 值 1 < 目标进制数 3，则商位为 0 余数为 1
3. 按次序从大数 1011 中取数，取出数为 0
4. 余数 1 乘上原进制数 2，加上取出数 0
5. 值 2 < 目标进制数 3，则商位为 0，余数为 2
6. 按次序从大数 1011 中取数，取出数为 1
7. 余数 2 乘上原进制数 2，加上取出数 1
8. 值 5 > 目标进制数 3，则商位为 1 余数为 2
9. 按次序从大数 1011 中取数，取出数为 1
10. 余数 2 乘上原进制数 2，加上取出数 1
11. 值 5 > 目标进制数 3，则商位为 1 余数为 2，将余数记录下来

重新计算商
12. 第一次计算后商为 0011，去除前置 0，作为新的大数，该值为 11
13. 将大数 11 按照取最低位余数步骤再次取最低位余数，新的商重新转换位大数，直至计算商小于目标进制数 3 结束。

1011 / 3 = 0011 ..... 余 2
0011 / 3 = 0001 ..... 余 0
0001 / 3 = 0000 ..... 余 1

数据处理
14. 此时得到余数位 201，按照先余为低位，后余为高位，对其反转变为 102。

-----------------------------------------
10 进制大数 12 转换为 2 进制大数 1100

计算过程：

先取最低位余数

1. 按次序从大数 12 中取数，取出数为 1
2. 值 1 < 目标进制数 2，则商位为 0 余数为 1
3. 按次序从大数 12 中取数，取出数为 2
4. 余数 1 乘上原进制数 10，加上取出数为 12
5. 值 12 > 目标进制数 2，则商位为 6，余数为 0，将余数记录下来

重新计算商
6. 第一次计算后商为 06，去除前置 0，作为新的大数，该值为 6
7. 将大数 6 按照取最低位余数步骤再次取最低位余数，新的商重新转换位大数，直至计算商小于目标进制数 2 结束。

12 / 2 = 6 ..... 余 0
6 / 2 = 3 ..... 余 0
3 / 2 = 1 ..... 余 1
1 / 2 = 0 ..... 余 1

数据处理
8. 此时得到余数位 0011，按照先余为低位，后余为高位，对其反转变为 1100。

代码实现

根据上面的算法描述就可以编写出精确的大数字串转换，上面描述的只是算法，实际上使用的时候还需要考虑制表符的问题，即可见字符 0-9，a-z，A-Z 的先后位置，这个可以根据需求来调整 a-z，A-Z 的先后位置。

实现代码：
制表符：”0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz”

#define BIG_NUMBER_CONVERT_BUFFER_SIZE 1024

static int getValue(char ch);
static void reverseStr(unsigned char* src, int len);

/*
大数字串进制转换。
注：
1. 转换复用了 srcData 空间，该字段数据会被改变
2. 输入字串区分大小写，按进制 11 - 36 以大写的英文字母表示，37 - 62 以小写英文字母表示
   即输入 16 进制，则字串中的英文字母必须为大写
3. 转换缓冲 buffer 默认为 1024，可用按照实际需求更改

params：
    srcData：传入的字串，需要以 '\0' 结尾
    destData：传出的字串，需要估计好大致空间
    srcBase：原字串进制，范围 2 - 62
    destBase：目标进制，范围 2 - 62
return：
    编码长度，出错返回负数
*/
int bigNumConvert(unsigned char* srcData, unsigned char* destData, int srcBase, int destBase) {

    char byteIndex[63] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    unsigned char buffer[BIG_NUMBER_CONVERT_BUFFER_SIZE] = { 0x00 };
    unsigned char *pbuffer = buffer;
    unsigned char* src = srcData;
    unsigned char* pos = srcData;
    unsigned char* dest = destData;
    int temp = 0;

    if (src == NULL
        || dest == NULL
        || (srcBase <= 1 || srcBase >= 62)
        || (destBase <= 1 || destBase >= 62)) {
        return -1;
    }

    while (*src) {
        while (*pos) {
            temp *= srcBase;
            temp += getValue(*pos++);
            if (temp < destBase) {
                *pbuffer++ = '0';
                continue;
            }
            else {
                *pbuffer++ = byteIndex[(temp / destBase)];
                temp %= destBase;
            }
        }
        *dest++ = byteIndex[temp];
        for (pos = buffer; pos < pbuffer && *pos == '0'; pos++);
        memcpy(src, pos, pbuffer - pos);
        src[pbuffer - pos] = 0;
        pos = src;
        pbuffer = buffer;
        temp = 0;
    }

    reverseStr(destData, dest - destData);
    destData[dest - destData] = 0x00;
    return dest - destData;
}

static int getValue(char ch) {
    if (ch >= '0'&&ch <= '9') {
        return ch - '0';
    }
    else if (ch >= 'A'&&ch <= 'Z') {
        return ch - 'A' + 10;
    }
    else {
        return ch - 'a' + 36;
    }
}

static void reverseStr(unsigned char* src, int len) {
    int i = 0, j = len - 1;
    unsigned char temp = 0;
    while (i < j) {
        temp = src[i];
        src[i++] = src[j];
        src[j--] = temp;
    }
}