软件设计师学习-码制

1. 原理

底层原理，经典计算机体系结构框架中只有加法器，因此，减法需要等价替换成加法。此处有两种思路：

• 引入了负数的概念，将减法改写成加相反数
• 考虑模运算和同余，可以将减数溢出为正数再相加

有此也就引出了反码和补码的概念。

1. 负数

负数和正数，需要用符号区分，因此牺牲一位作为符号位，将最高位定为符号位，1 表示负号，0 表示正号，此编码方式表示的机器数叫做原码。

2. 原码（True Form）

写出部分十进制数的原码，并进行一些运算：

码值 |  -3  |  -2  |  -1  |  -0  |  +0  |  +1  |  +2  |  +3  
原码 | 1011 | 1010 | 1001 | 1000 | 0000 | 0001 | 0010 | 0011 

+1 add +1 => 0001 add 0001 = 0010 => +2
+0 add -0 => 0000 add 1000 = 1000 => -0
+1 add -1 => 0001 add 1001 = 1010 => -2
+1 add -2 => 0001 add 1010 = 1011 => -3
-1 add -1 => 1001 add 1001 = 0010 => +2 (舍弃溢出位)

此处有几个问题：

• 0 有正负两个
• 负负相加时，结果异常
• 正负相加时，结果异常

为了解决符号位问题，引入了反码和补码。

3. 反码（1’s Complement Code）

负数是一个正数的相反数，可以考虑用一个正数按位取反来表示负数。

码值 |  -3  |  -2  |  -1  |  -0  |  +0  |  +1  |  +2  |  +3  
原码 | 1011 | 1010 | 1001 | 1000 | 0000 | 0001 | 0010 | 0011 
反码 | 1100 | 1101 | 1110 | 1111 | 0000 | 0001 | 0010 | 0011 

+1 add +1 => 0001 add 0001 = 0010 => +2
+0 add -0 => 0000 add 1000 = 1000 => -0
+1 add -1 => 0001 add 1110 = 1111 => -0
+1 add -2 => 0001 add 1101 = 1110 => -1
-1 add -1 => 1110 add 1110 = 1100 => -3 (舍弃溢出位)

此处有几个问题：

• 0 有正负两个
• 负负相加时，结果异常

4. 补码（2’s Complement Code）

补码可以简单类别为常见的时钟，对于常见的范围是 0 到 12 的时钟而言，10 点减去 3 小时：

• 10 - 3 = 7，即往回数到 7
• 10 - 3 => 10 + (12 - 3) = 19 => 7，即往后数，超过 12 后，仍回到 7

超出 12 再减去 12 就是取模，7 和 19 就是同余数（7≡19(mod 12)）。

对于 4bit 而言，最大容量为 2⁴=16（即 1 0000），因此，负数可以重新表示为 1 0000 减去其绝对值：

码值 |  -3  |  -2  |  -1  |  -0  | + 0  |  +1  |  +2  |  +3  
原码 | 1011 | 1010 | 1001 | 1000 | 0000 | 0001 | 0010 | 0011 
反码 | 1100 | 1101 | 1110 | 1111 | 0000 | 0001 | 0010 | 0011 
补码 | 1101 | 1110 | 1111 |      | 0000 | 0001 | 0010 | 0011 

+1 add +1 => 0001 add 0001 = 0010 => +2
 0 add  0 => 0000 add 0000 = 0000 =>  0
+1 add -1 => 0001 add 1111 = 0000 =>  0 (舍弃溢出位)
+1 add -2 => 0001 add 1110 = 1111 => -1 
-1 add -1 => 1111 add 1111 = 1110 => -2 (舍弃溢出位)

5. 定义

若 X 是纯整数，则

$\begin{aligned} & [X]_{TF} =\begin{cases} X & 0\leqslant X\ \leqslant 2^{n-1} -1 \\ 2^{n-1} + |X| & -\left( 2^{n-1} -1\right) \leqslant X\leqslant 0 \end{cases}\\ & [X]_{1C} =\begin{cases} X & 0\leqslant X\ \leqslant 2^{n-1} -1 \\ 2^{n} - 1 + X & -\left( 2^{n-1} -1\right) \leqslant X\leqslant 0 \end{cases}\\ & [X]_{2C} =\begin{cases} X & 0\leqslant X\ \leqslant 2^{n-1} -1 \\ 2^{n} + X & \left( 2^{n} -1\right) \leqslant X\leqslant 0 \end{cases} \end{aligned}$

6. 反码和补码

反码和补码，从定义来看是没有关系的，但是由于 负数的反码+绝对值+1 = 10000 ，而 负数的补码+绝对值 = 10000，因此，负数的补码等于反码加一。

2. 总结

只使用加法器，并不是不能制造减法器，只是为了可以使用通用电路来完成尽量多的计算，而补码的发明，则极大地提高了运算效率。

由于补码的使用，原码和反码用来表示 -0 的 1000 0000 ，规定用来表示 -128，从而造成所有整数类型能够表示的负数都比正数多一个，如下，Java 的基本数据类型的占用空间和取值范围：

类型	符号	占用空间	最小值	最大值	默认值
整数	byte	1 byte	$-2^7$ ($-128$)	$2^7 - 1$ ($127$)	$0$
	short	2 bytes	$-2^{15}$	$2^{15} - 1$	$0$
	int	4 bytes	$-2^{31}$	$2^{31} - 1$	$0$
	long	8 bytes	$-2^{63}$	$2^{63} - 1$	$0$
浮点数	float	4 bytes	$1.175 \times 10^{-38}$	$3.403 \times 10^{38}$	$0.0f$
	double	8 bytes	$2.225 \times 10^{-308}$	$1.798 \times 10^{308}$	$0.0$
字符	char	2 bytes	$0$	$2^{16} - 1$	$0$
布尔	bool	1 byte	$\text{false}$	$\text{true}$	$\text{false}$