番外篇 - 关于进制

1. 什么是进制

我们通常都是基于数字10来表示数字，比如2157，千位为2、百位为1、十位为5、个位为7，由此，我们可以得出一个等式

2157 == 2 * 10^3 + 1 * 10^2 + 5 * 10^1 + 7 * 10^0

因为这种方法是基于10的幂，所以称以10为基底书写2157

姑且认为这种书写方法是得益于我们有10根手指。从某种意义上看，计算机只有2根手指，只能表示0和1，因此，计算机适用于基底为2的数制系统。 它使用2的幂而不是10的幂。以2为基底表示的数统称为 二进制数 ( binary number )， 二进制中的2和十进制中的10作用一样，都是基数，而2的幂则相当于十进制中的10的幂。例如：

1011 == 1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0

2. 数学中的十进制

本节中，我们假设自然数存在且满足皮亚诺公理。

1. 定义 数字：数字指 0 1 2 3 4 5 6 7 8 9 这十个符号其中的任意一个。
   把这些数字分别和某个自然数对应（++表示后继数）：
   • $0\equiv 0$
   • $1\equiv 0++$
   • $2\equiv 1++$
   • $3\equiv 2++$
   • $4\equiv 3++$
   • $5\equiv 4++$
   • $6\equiv 5++$
   • $7\equiv 6++$
   • $8\equiv 7++$
   • $9\equiv 8++$
2. 定义 $\mathrm{十}=9++$，避免循环论证。
3. 定义 十进制正整数：十进制正整数指由数字组成的字符串 $a_n{a}_{n-1}\dots a_0$，其中 $n$ 是一个自然数，并且数字 $a_n$ 不是 $0$。
   十进制正整数等同于某个正整数：$$a_n{a}_{n-1}\dots a_0=\sum _{i=0}^n{a}_i\times {\mathrm{十}}^i$$显然：$$10=0\times {\mathrm{十}}^0+1\times {\mathrm{十}}^1=\mathrm{十}$$
4. 十进制表示的唯一性和存在性，即每一个正整数 $m$ 都恰好等于一个十进制正整数：
   1. 存在性，即每一个正整数 $m$ 都至少等于一个十进制正整数。 运用数学归纳法，假设对于所有正整数 $m^{\prime }<m$，命题成立；希望证明对于 $m$ 命题也成立。
      易得：$m\ge \mathrm{十}$ 或 $m\in \{1,2,3,4,5,6,7,8,9\}$（为什么？）。
      1. 当 $m\in \{1,2,3,4,5,6,7,8,9\}$ 时：
         1. $m$ 显然等于唯一一个由单独一个数字组成的十进制正整数。
            （这其实说明对于 $m\in \{1,2,3,4,5,6,7,8,9\}$，存在性和唯一性都成立）
         2. 由两个或以上个数字组成的十进制数都不等于 $m$。因为如果不然，设 $a_n\dots a_0=m$，则$$a_n\dots a_0=\sum _{i=0}^n{a}_i\times {\mathrm{十}}^i\ge a_n\times {\mathrm{十}}^n\ge \mathrm{十}>m$$这与 $a_n\dots a_0=m$ 矛盾。
      2. 当 $m\ge \mathrm{十}$ 时：
         可得 $m=s\times \mathrm{十}+r$，其中 $s$ 是正整数，$r\in \{1,2,3,4,5,6,7,8,9\}$。
         由于 $s<m$，根据归纳假设，$s$ 有一个十进制表示。设为 $b_p\dots b_0$，则 $m$ 有一个十进制表示 $b_p\dots b_{0}r$。
      3. 由上面两种情况得存在性成立。
   2. 唯一性，即 $m$ 最多有一个十进制表示。
      同样运用数学归纳法，假设对于所有正整数 $m^{\prime }<m$，命题成立；希望证明对于 $m$ 命题也成立。
      1. 运用反证法，假设 $m$ 有两个不同的十进制表示 $a_n\dots a_0$，$b_m\dots b_0$，可以列出如下式子：
         $a_n\dots a_0=(a_n\dots a_1)\times \mathrm{十}+a_0$ ①
         $b_m\dots b_0=(b_m\dots b_1)\times \mathrm{十}+b_0$ ②
         ①②$⟹b_0-a_0=(a_n\dots a_1-b_m\dots b_1)\times \mathrm{十}$
      2. 上式右端是 $\mathrm{十}$ 的倍数，左端介于 $-\mathrm{十}$ 和 $\mathrm{十}$ 之间，所以只可能左右同时等于零。
      3. 这意味着 $a_n\dots a_1=b_m\dots b_1$ 且 $a_0=b_0$。
      4. 因为 $a_n\dots a_1<a_n\dots a_0$，根据归纳假设，$a_n\dots a_1$ 有唯一的二进制表示，所以 $n=m$ ，且对于 $i=1,\dots n$，$a_i=b_i$。
      5. 因此，$a_n\dots a_0$ 实际上和 $b_m\dots b_0$ 完全相同，和反证法的假设矛盾。所以命题对于 $m$ 成立。
      6. 结合命题对于 $1,2,3,4,5,6,7,8,9$ 成立（证存在性的第一条证过了），唯一性成立。

3. 各种进制的字面量表示

字面量 (Literal) 是指直接出现在程序中的数据，比如 10、3.14、'a' 等。

3.1 二进制

二进制字面量以 0b 或 0B 开头，后面跟着二进制数字（0 和 1）。例如：

int binary = 0b1010; // 二进制 1010，十进制 10

3.2 八进制

八进制字面量以 0 开头，后面跟着八进制数字（0-7）。例如：

int octal = 012; // 八进制 12，十进制 10

每个八进制位都对应一个 3 位二进制数 ( 即 3 个二进制位 )， 下图列出了八进制和二进制之间的对应关系：

注意：转换的时候不能省略中间的 0

十进制	八进制	对应二进制
0	0	000
1	1	001
2	2	010
3	3	011
4	4	100
5	5	101
6	6	110
7	7	111

例如：八进制值 012 对应的二进制值是 000001010 ；八进制值 077 对应的二进制值是 000111111 。

3.3 十进制

十进制字面量是默认的表示方法，不需要前缀。例如：

int decimal = 10; // 十进制 10

3.4 十六进制

十六进制一共有16个表示数字 0 ~ 15 ，但是由于没有单独的数 ( digit ，即 0~9 这样的单独数字) 来表示 10 ~ 15 ， 所以我们用字母 A ~ F ( a ~ f )来表示。

十六进制字面量以 0x 或 0X 开头，后面跟着十六进制数字（0-9 和 a-f 或 A-F）。例如：

int hexadecimal = 0xA; // 十六进制 A，十进制 10

每个十六进制位都对应一个 4 位二进制数 ( 即 4 个二进制位 )， 那么，两个十六进制位恰好对应一个 8 位字节，第一个十六进制位表示前4位，第二个十六进制位表示后4位。因此，十六进制很适合表示字节值。 下图列出了十六进制和二进制之间的对应关系：

十进制	十六进制	对应二进制
0	0	0000
1	1	0001
2	2	0010
3	3	0011
4	4	0100
5	5	0101
6	6	0110
7	7	0111
8	8	1000
9	9	1001
10	A	1010
11	B	1011
12	C	1100
13	D	1101
14	E	1110
15	F	1111

例如：十六进制值 0xC2 对应的二进制值是 11000010 ；十六进制值 0xFF 对应的二进制值是 11111111 。

参考资料：

Wikipedia - 进位制