“进制转换”编程题总结

在日常生活中我们一般使用十进制数字，而计算机使用的却是二进制。此外，常见的进制还有八进制、十六进制等。对于两个不同进制，应该如何进行相互转换呢？这里总结下该问题的解题思路。

对于一个P进制的数，如果要转换为Q进制（2 ≤ P , Q ≤ 16），可以分为两步：

（1）将P进制数x转换为十进制数y。

（2）将十进制数y转换为Q进制数z。

将P进制数x转换为十进制数y

一个P进制数$x=a_1 a_2 \dots a_n$，写成如下形式后，使用十进制的加法和乘法，就可以转换为十进制数y：
$$
y = a_1 \times P^{n-1} + a_2 \times p^{n-2} + \dots + a_{n-1} \times P + a_n
$$
这个公式可以用下面的代码实现：

int y = 0, product = 1;
while (x != 0) {
    y += (x % 10) * product;
    x /= 10;//每循环一次丢弃一位
    product *= p;
}

将十进制数y转换为Q进制数z

可以采用”除基取余法“。这里的“基”，是指要转换成的进制Q。因此除基取余的意思就是每次将待转换数除以Q，然后将得到的余数作为低位存储，而商则继续除以Q并继续进行上面的操作，直到商为0时，退出循环。此时，将所有位从后向前输出就可以得到z。

上述过程可以用下面的代码实现：

int z[20], i = 0;
do {
    z[i++] = y % Q;
    y /= Q;
} while (y != 0);

执行完后，数组z从高位i-1到低位0即为Q进制整数z。这里之所以采用do…while循环而不采用while循环，是因为当y恰好等于0时，while循环不会执行，导致结果出错。

参考文献

[1] 胡凡，曾磊.《算法笔记》[M].北京：机械工业出版社，2016