进制转换

标签: c java | 发表时间:2015-01-04 22:25 | 作者:wangdai
出处:http://segmentfault.com/blogs

导言

进制转换是一道经典的题,基本概念不多说,像下面这样

  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;
}

相关 [进制转换] 推荐:

进制转换

- - SegmentFault 最新的文章
进制转换是一道经典的题,基本概念不多说,像下面这样. 12(10进制) <=> C(16进制) <=> 1100(2进制) <=> 14(8进制). 注意进制不同时,数值还是一样大的. 因此C(16进制)只是12(10进制)的另一种表示,而不是另一个数值. 其实我的意思是, 表示10进制外的其他进制时都应该用字符串.