大数任意进制转换
大数任意进制转换
项目中有地方需要将 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;
}
}