ACSL——进制转换

BZR

什么是进制？
进制是我们命名和表示数字的方式。n进制就是在这个数字系统中逢n进1。我们在日常生活中使用的数制被称为十进制数制，或以 10 为基数的数制，因为它逢10进1，基于 10 种不同的数字：0、1、2、……、8 和 9。数的基数会作为数字的下标写在数字后面。例如，十进制数“一万两千三百四十五”写作 12345_10。如果没有基数或明确的上下文，就会假定一个数字是基于 10 的。（很明显）
在CS中，除了十进制之外，还有另外三种常见的数制被广泛使用：二进制、八进制和十六进制。二进制数非常重要，因为这是计算机中存储数字的方式。八进制和十六进制被用于以一种用户友好的方式表示二进制数。（0～9以上的数位就用大写字母A～Z依次表示。）
进制转换
下面我将针对2、8、10、16这四个较为常用且在ACSL short problems中出现的这四个进制进行讨论。
那么，要进行进制转换，要先理解位权：一个数的每一位都有对应的位权。一个数的位权从0开始，从右到左，每一位递增1。

一、二进制转其他进制
先聊一聊二进制转其他进制，主要的方法就是化为按权展开式。
1. 二进制转十进制：将二进制数的位数乘以2的位权次幂并相加，计算结果就是对应这个二进制数的十进制数。
例如：10110（B）转十进制，= 1 * 2^4 + 0 * 2^3 + 1 * 2^2 + 1 * 2^1 + 0 * 2^0 = 16 + 0 + 4 + 2 + 0 = 22（D）。
2. 二进制转八进制：从右到左，三位为一组，不够三位的在前面补0（不影响计算结果），然后每组分别按权展开，即可得到对应的八进制数。
还是拿刚才的例子：10 110（B），转八进制。后三位是110，计算时就分别按权展开：1 * 2^2 + 1 * 2^1 + 0 * 2^0 = 6；前面只有两位，向前补一个0，010，按权展开：0 * 2^2 + 1 * 2^1 + 0 * 2^0 = 2，所以10110（B） = 26（O）。（注意最后排列顺序是从高位组向低位组）
3. 二进制转十六进制：从右到左，四位为一组，不够四位的在前面补0（不影响计算结果），然后每组分别按权展开，即可得到对应的十六进制数。
这回举一个长一点的例子：1 1101 1010（B），转十六进制。后四位是1010，按权展开：1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 0 * 2^0 = 10 = A；往前四位1101，按权展开：1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0 = 13 = D；最后只剩一个1了，1 * 2^0 = 1，所以最后111011010（B） = 1DA（H）。

二、其他进制转二进制
说完二进制转其他，那就不得不说其他进制转二进制了，基础算法就是短除。
1. 十进制转二进制：除2取余，倒序排列——将十进制数连续除以2，记下每一次除的余数（我个人写在除法竖式的右侧），最后从下往上（从除法顺序的后往先）排列，即可得到对应的二进制数。
例：26（D）转二进制，短除：
26÷2=13……0
13÷2=6……1
6÷2=3……0
3÷2=1……1
1÷2=0……1
倒序排列，所以 26（D） = 11010（B）。
2. 八进制转二进制：将要转换的八进制数的每一位分别进行短除（÷2），取短除后的余数，倒序排列。八进制数中的每一位除后都要得出一个三位二进制数（不够三位的在前面补0），最后把得到的若干个三位二进制数从原先八进制数位数的左到右排列，即可得到对应的二进制数。
听上去有点绕口？举个例子就明白了：74（O）转二进制，拆分后短除：
第一位：7
7÷2=3……1
3÷2=1……1
1÷2=0……1
-> 7（O）= 111（B）
第二位：4
4÷2=2……0
2÷2=1……0
1÷2=0……1
-> 3（O）= 100（B）
连起来，所以 75（O）= 111100（B）。
3. 十六进制转二进制：将要转换的十六进制数的每一位分别进行短除（÷2），取短除后的余数，倒序排列。十六进制数中的每一位除后都要得出一个四位二进制数（不够四位的在前面补0），最后把得到的若干个四位二进制数从原先十六进制数位数的左到右排列，即可得到对应的二进制数。
老规矩，举个例子：5C2（H）
第一位：5
5÷2=2……1
2÷2=1……0
1÷2=0……1
（补0）-> 5（H）= 0101（B）
第二位：C
12÷2=6……0
6÷2=3……0
3÷2=1……1
1÷2=0……1
-> C（H）= 1100（B）
第三位：2
2÷2=1……0
1÷2=0……1
（补0）-> 2（H）= 0010（B）
连起来，所以 5C2（H）= 101 1100 0010（B）

三、八进制转十进制 / 十进制转八进制
即使你不知道如何把八进制转成十进制，或者把十进制转成八进制，也可以通过把二进制当一个中间量、间接转换来完成：

八进制 -> 二进制 -> 十进制
十进制 -> 二进制 -> 八进制

当然，这个做法很明显麻烦了许多，下面看一下如何八进制直接转十进制：
方法与二进制转十进制雷同，采用按权展开：将八进制数的位数乘以8的位权次幂并相加，计算结果就是对应这个八进制数的十进制数。
例如：273（O）转十进制，= 2 * 8^2 + 7 * 8^1 + 3 * 8^0 = 128 + 56 + 3 = 187（D）。

而十进制直接转八进制和十进制转二进制的方法一样：除8取余，倒序排列——将十进制数连续除以8，记下每一次除的余数，最后从下往上（从除法顺序的后往先）排列，即可得到对应的八进制数。
例如：78（D）转八进制
78÷8=9……6
9÷8=1……1
1÷8=0……1
所以 78（D）= 116（O）。

四、十六进制转十进制 / 十进制转十六进制
间接转换就不用多说了，拿二进制当中间量。

十六进制直接转十进制和二进制、八进制转十进制的方法也一样，将十六进制数的位数乘以16的位权次幂并相加，计算结果就是对应这个十六进制数的十进制数。
例如：1AD8（H）转十进制，= 1 * 16^3 + 10 * 16^2 + 13 * 16^1 + 8 * 16^0 = 4096 + 2560 + 208 + 8 = 6872（D）。

十进制转十六进制，方法没有丝毫区别：除8取余，倒序排列。
还要例子吗？还是举一个吧......：123（D）转十六进制
123÷16=7……11
7÷16=0……7
所以 123（D）= 7B（H）。

BZR

搞点儿题？
话不多说，直接上题目（此题来自2001-02 ACSL Senior Division Contest #1 Short Problems No.1）：

Solve for X_8:

BAD_16 = X_8 + 465_8 - 447_8

解：我们可以观察到方程左侧是一个十六进制数，右侧均是八进制数，先把十六进制数化成八进制数（我个人没啥好算法，间接转化）：
先将 BAD（H） 转二进制：
第一位：B（=11）
11÷2=5......1
5÷2=2......1
2÷2=1......0
1÷2=0......1
-> B（H） = 1011（B）
第二位：A（=10）
10÷2=5......0
5÷2=2......1
2÷2=1......0
1÷2=0......1
-> A（H） = 1010（B）
第三位：D（=13）
13÷2=6......1
6÷2=3......0
3÷2=1......1
1÷2=0......1
-> D（H） = 1101（B）
连起来，所以 BAD（H） = 1011 1010 1101（B）。

接下来，再将得到的二进制数转为八进制：
101110101101（B）三位一组：101 110 101 101，每一组分别按权展开：
101（B） = 1 * 2^2 + 0 * 2^1 + 1 * 2^0 = 5（O）
101（B） = 5（O）
110（B） = 1 * 2^2 + 1 * 2^1 + 0 * 2^0 = 6（O）
101（B） = 5（O）
所以 101110101101（B） = 5655（O）

经过一番转换，我们可以得出方程的左边是八进制下的5655。现在，方程变为5655（O） = X（O） + 465（O） - 447（O）。

移项：X（O） = 5655（O） - 465（O） + 447（O）

接下来要处理的就是八进制下的加减。(当然，如果你不嫌麻烦，把它们全部转成十进制再进行加减也是可以的，转十进制的方法也可以用作验算。）非十进制的加减法与十进制类似，但进位和借位的原则是基于当前进制的基数。八进制加减就是逢8进1，借1加8。如果你口算不好，可以尝试列竖式，简单又直观。

先来化简 5655（O） - 465（O）好了。

  5 6 5 5

-    4 6 5

------------

   5 1 7 0

第1位：5 - 5 = 0

第2位：5 - 6，不够减，向第3位借位，八进制下借一位加8，(5 + 8) - 6 = 7

第3位：6被借了1，变成5，- 4 = 1

最后一位5直接拉下来，所以最终结果为5170（O）。

接下来求 5170（O） + 447（O）

   5 1 7 0

+   4 4 7

-----1------

   5 6 3 7

第1位：0 + 7 = 7

第2位：7 + 4 = 11 > 8，进1，变成3

第3位：1 + 4 = 5，5 + 1 = 6

最后一位5拉下来，所以最终结果为5637（O）。

综上所述，X = 5637。原方程就解出来了！

再来一道？下题来自相同卷子的Short Problems No.2：

How many 1's are in the binary representation of the following hexadecimal sum?

59A_16 + B28D6_16 + E3E_16

就是问：下面十六进制算式的结果的二进制表达含有多少个1？

有两种大的解题思路：

1. 将题目中所有十六进制数转成二进制数，相加之后统计。

2. 先将十六进制数相加，再将结果转成二进制进行统计。

一般来说，第二种的效率会更高一些，原因是二进制数很长，相加容易晕......

那么，就用第二种方法解：

十六进制相加（逢16进1）：

  B 2 8 D 6

        5 9 A

+      E 3 E

-----1-1--1----

   B 3 C A E

结果为 B3CAE（H）。

现在要将B3CAE（H）转二进制：

第一位：B（=11）

11÷2=5......1
5÷2=2......1
2÷2=1......0
1÷2=0......1
-> B（H） = 1011（B）

第二位：3

3÷2=1......1

1÷2=0......1

（补0）-> 3（H） = 0011（B）

第三位：C（=12）

12÷2=6......0

6÷2=3......0

3÷2=1......1

1÷2=0......1

-> C（H） = 1100（B）

第四位：A（=10）

10÷2=5......0

5÷2=2......1

2÷2=1......0

1÷2=0......1

-> A（H） = 1010（B）

第五位：E（=14）

14÷2=7......0

7÷2=3......1

3÷2=1......1

1÷2=0......1

-> E（H） = 1110（B）

拼起来，所以 B3CAE（H） = 1011 0011 1100 1010 1110（B）

最后数一数有多少个“1”，即可得到答案：12个。