Cirry's Blog

最近再看《hello 算法》这本书，我是强烈推荐想入门算法的人也去看一下的。

书中有关于原码、反码、补码的说明，我又加深了一下理解。

基本概念

原码：我们将数字的二进制表示的最高位视为符号位，其中0表示正数，1表示负数，其余位表示数字的值。
反码：正数的反码与其原码相同，负数的反码是对其原码除符号位外的所有位取反。
补码：正数的补码与其原码相同，负数的补码是在其反码的基础上加1。

这里我们只讨论有符号位的数，也就是说一个字节对应的8个比特里的，其中的第一个比特位用来表示符号。

然而这样一个字节，它的取值范围应该是1111 1111到0000 0000再到0111 1111，对应的大小范围是从-127 -> 127，而实际的大小范围是-128 -> 127，为什么后面再说。

假设只有原码

如果只有原码的情况下会遇到什么问题：

在原码中：0000 0001 表示1，0111 1111 表示 127，1000 0001 表示-1， 1111 1111表示 -127。

用 0111 1111 来举例，它的十进制结果是:

$$ 0111\ 1111$$ $$ = 1\times 2^6 + 1 \times 2^5 + 1\times 2^4 + 1 \times 2^3 + 1\times 2^2 + 1 \times 2^1 + 1\times 2^0 $$ $$ = 64 + 32 + 16 + 8 + 4 + 2 + 1 $$ $$ = 127 $$

用 1010 0100 来举例，它的十进制结果是:

$$ 1010\ 0100 $$ $$ = -1 \times ( 0 \times 2^6 + 1 \times 2^5 + 0 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 0 \times 2^0 ) $$ $$ = -1 \times ( 0 + 32 + 0 + 0 + 4 + 0 +0)$$ $$ = -36 $$

原码在表示上是没有问题的，但是在计算上很复杂，比如 1 + (-2)

$$ 1 + (-2) $$ $$ = 0000\ 0001(原码) + 1000\ 0010(原码) $$ $$ = 1000\ 0011(原码) $$ $$ = -( 1 \times 2^1 + 1 \times 2^0) $$ $$ = -3 $$

所以在原码的表示中，加减问题需要注意的事项很多，详细的步骤应该如下：

确定被减数和减数的符号。
比较被减数和减数的大小，决定是进行直接减法还是交换顺序并取负。
根据符号决定具体操作：
- 如果符号相同，则执行减法。
- 如果符号不同，则执行加法。
确定结果的符号。

示例1：计算7-5

表示被减数和减数：被减数7的原码是：0000 0111，正数，符号位为0。减数5的原码是：0000 0101，正数，符号位为0。
符号相同且7>5，执行减法 0000 0111 - 0000 0101 = 0000 0010，结果为 2 (十进制，正数，符号位为0)。

示例2：计算5-7

表示被减数和减数：被减数5的原码是：0000 0101，正数，符号位为0。减数7的原码是：0000 0111，正数，符号位为0。

只有原码和反码

反码的规则：正数的反码与其原码相同，负数的反码是对其原码除符号位外的所有位取反。

再来看同样的计算规则 1 + (-2)

$$ 1 + (-2) $$ $$ = 0000\ 0001(原码) + 1000\ 0010(原码) $$ $$ = 0000\ 0001(反码) + 1111\ 1101(反码) $$ $$ = 1111\ 1110(反码) $$ $$ = 1000\ 0001(反码) $$ $$ = -(1 \times 2^0) $$ $$ = -1 $$

这里有一个问题，为什么用反码可以解决负数加减的问题。

再来看反码的规律，按位取反。如果把8bit看成无符号位，它的取值范围应该是0000 0000 ~ 1111 1111，即0 ~ 255。

-2 的原码是 1000 0010, 对应的反码是 1111 1101，这个反码对应的无符号十进制是 253，也就是说用-2 + 255 = 253 的二进制表示就是-2的反码。

你可以理解255为一圈，取反就是+255的简便运算。用钟表来表示（12个小时为一圈），现在的时间是10点，往后减两个小时 10 - 2 = 8 ，和 10 + (-2 + 12)是一样的。

$$ 1\ +\ (-2) $$ $$ =\ 1\ +\ 253 $$ $$=\ 0000\ 0001(原码)\ +\ 1111\ 1101(反码) $$ $$ =\ 1111\ 1110(反码) $$ $$ =\ 1000\ 0001(原码) $$ $$ =\ -1 $$

$$ 3\ +\ (-2) $$ $$ =\ 3\ +\ 253 $$ $$ =\ 0000\ 0011(原码)\ +\ 1111\ 1101(反码) $$ $$ =\ 1\ 0000\ 0000(进位) $$ $$ =\ 256 $$ $$ = 0000\ 0000\ +\ 1 $$ $$ =\ 0000\ 0001 $$ $$ =\ 1 $$

在反码中，如果有进位，需要将进位加到结果的最低位，这个理解为，256 - 255 超出了 1，溢出的1加在尾部就好了。

从上面可以看出只有原码和反码，对于数据溢出处理是麻烦的。还有一个问题，就是1000 0000和0000 0000用来表示正零和负零是重复了，在代码中带来了不必要的判断。

为了解决上面的问题，就引出了补码。