进制转换
导言
进制转换是一道经典的题,基本概念不多说,像下面这样
12(10进制) <=> C(16进制) <=> 1100(2进制) <=> 14(8进制)
注意进制不同时,数值还是一样大的。因此C(16进制)只是12(10进制)的另一种表示,而不是另一个数值。其实我的意思是, 表示10进制外的其他进制时都应该用字符串。
因此一般有两种情况
1. 10进制整数转换为其他进制字符串
2. 其他进制字符串转换为10进制整数
对于10进制整数转换为8进制或16进制字符串时,C和Java里都有偷懒的办法
/* C */
int num = 12;
char oct_str[100];
char hex_str[100];
sprintf(oct_str, "%o", num); /* oct_str == "14" */
sprintf(hex_str, "%x", num); /* hex_str == "C" */
/* or printf */
// Java
int num = 12;
String octStr = Integer.toOctalString(num); // octStr == "14"
String hexStr = Integer.toHexString(num); // hexStr == "C"
对于其他进制字符串转换为10进制整数,Java已经提供了完美的方法。
// Java
int num = Integer.parseInt("C", 16); // num == 12
当然,这并不是我们想要的,我们希望自己实现一个进制转换的函数。
10进制整数转换为其他进制字符串
先举个栗子——我们是怎么把111(10进制)转换为157(8进制)的呢,其实就是一般的除法。
1. 比111小的最大的8的幂次是64
2. 111 / 64 = 1 ... 47
3. 47 / 8 = 5 ... 7
4. 7 / 1 = 7 ... 0
把3次除法的商连起来就是157(8进制)
算法上的思路跟这个完全一样(如果下面这段看着难受请直接看代码)
1. 假设要被转换的10进制数是num,进制是base,转换结果是result
2. 找到比num小的最大的base^n
3. result的第i位为num / base^(n-i)的商
4. num = num % base^(n-i),即余数作为下一轮的被除数
5. i++并回到第3部除非除数等于0
/* C */
char *itos(int num, int base, char *dest)
{
int i, divisor = 1;
char *table = "0123456789ABCDEF";
while (divisor * base <= num) {
divisor *= base;
}
for (i = 0; divisor >= 1; i++, divisor /= base) {
dest[i] = table[num/divisor];
num %= divisor;
}
dest[i] = 0;
return dest;
}
等等你说C语言的这个版本有个问题,为什么要传个 char *dest
进去呢?我该怎么调用呢?
正确的调用姿势是下面这样的,至于为什么,请看我将来要写的一篇文章——C语言中的字符串与指针。
char str[100];
itos(255, 16, str);
printf("%s", str); /* prints "FF" */
Java版本的代码
// Java
public static String itos(int num, int base) {
int divisor = 1;
byte[] table = "0123456789ABCDEF".getBytes();
String result = "";
while (divisor * base <= num) {
divisor *= base;
}
for (; divisor >= 1; divisor /= base) {
result += (char) table[num/divisor];
num %= divisor;
}
return result;
}
其他进制字符串转换为10进制整数
这个就比较简单了,用一个表达式就是(假设字符串是a,有n位)
T[n] = a[0]*base^(n-1) + a[1]*base^(n-2) + ... + a[n-2]*base + a[n-1]
转化成迭代的式子就是
T[0] = 0
T[i+1] = base*T[i] + a[i]
转化成程序就是
/* C */
int stoi(const char *src, int base)
{
int i, digit, result = 0;
for (i = 0; i < strlen(src); i++) {
if (src[i] >= 'a') {
digit = src[i] - 'a' + 10;
} else if (src[i] >= 'A') {
digit = src[i] - 'A' + 10;
} else {
digit = src[i] - '0';
}
result = base*result + digit;
}
return result;
}
// Java
public static int stoi(String src, int base) {
int digit, result = 0;
for (int i = 0; i < src.length(); i++) {
char c = src.charAt(i);
if (c >= 'a') {
digit = c - 'a' + 10;
} else if (c >= 'A') {
digit = c - 'A' + 10;
} else {
digit = c - '0';
}
result = base*result + digit;
}
return result;
}