进制转换

进制，也就是满X进一。其本质上是对于计数的简写。比如原来要表示一个数，只能用若干个小棒来表示。进制的出现，就相当于出现了代表一定数值的小棒的出现。这也就是位权：满X进一中的X。

（摘自百度百科）进制转换是人们利用符号来计数的方法。进制转换由一组数码符号和两个基本因素“基数”与“位权”构成。基数是指，进位计数制中所采用的数码（数制中用来表示“量”的符号）的个数。位权是指，进位制中每一固定位置对应的单位值。

理解了进制的本质后，我们就可以着手用数学工具去实现进制转换了。

短除法

首先以十进制为例。规定//为带余数除法，我们规定一个正整数123，那么：

123 // 10 = 12......3
12  // 10 = 1 ......2
1   // 10 = 0 ......1

观察。可以得到，三次除法的余数分别是3，2，1.对应个位，十位，百位。为什么呢？因为

123（10）=1*10^2+2*10^1+3*10^0

所以，每次得到的余数，就是对应位的数。显然，此结论对于N进制都成立。

下面，我们用编程实现这个算法。

/* Dec2Bin - by xeonds */
#include <stdio.h>

int base_dec_2_bin_convert(int num);

int main(void)
{
    int i;

    scanf("%d", &i);
    if (i <= 512 && i >= -512)
        printf("dec:%d  bin:%d\n", i, base_dec_2_bin_convert(i));
    else
        puts("Out of range.");

    return 0;
}

int base_dec_2_bin_convert(int num)
{
    int result = 0, i = 1;

    while (num > 0)
    {
        result += num % 2 * i;
        num = (num - num % 2) / 2;
        i *= 10;
    }

    return result;
}

算法核心部分是最后几行。num % 2 * i是计算最后一位并乘10，便于用int表示。num = (num - num % 2) / 2是将num减去余数并除以位权。

用[[Python|Python]]的话还可以写得更短些：

#!/usr/bin/python

def base_10_to_2(number):
    result = ''
    while number:
        number, rest = divmod(number, 2)
        result = str(rest) + result
    return result

更进一步，我们可以实现任意进制转换：

def base_n_convert(number, letters):
    length = len(letters)
    result = ''
    while number:
        number, rest = divmod(number-1, length)
        result = letters[rest] + result
    return result

其实这是我写的一个密码字典生成器。效率暂且不论，其原理也是进制转换。这里的number是待转换的十进制数，letters是待转换的N进制数的所有字符，比如十进制是0_{9，十六进制是0}F。

上面实现的，都是10进制转其他进制。其他进制转十进制很简单，只需要将各个位乘以其位权，求和即可得到其十进制表示。其原因很简单，我们的数学体系是建立在十进制的，所以对于十进制环境下的各种运算都很熟悉。这个方法对于任意进制转p进制其实都适用，不过这需要编写相应进制的四则运算算法，相对麻烦一些。

任意进制和任意进制的互转，可直接也可间接。间接，即将p进制数先转换为10进制等中间进制，再将其转换为q进制。直接，即利用对应规则进行转换。如二进制和十六进制互转，便可利用有限个对应规则实现快速互转。

小结

和栈机制一样，进制转换是很多技术的基础。某些时候利用它，或许会获得意想不到的奇效。

同时，作为算法的源泉，数学真的很重要。