原码, 反码, 补码

在 32 位机器上，int 的范围是 [-2^31, 2^31-1]，为什么正数和负数的范围不对称？

一、机器数和真值

在学习原码，反码和补码之前，需要先了解机器数和真值的概念

机器数

机器数：一个数在计算机中的二进制表示形式。其最高位存放符号，正数为0，负数为1

比如 -3 的机器数就是 10000011

真值

第一位是符号位，真值就是将符号考虑进去进行计算的值。

比如：1000 0001 的真值是 -1，而不是 129

二、原码，反码，补码的基础概念和计算方法

在探求为何机器要使用补码之前，让我们先了解原码，反码和补码的概念。对于一个数，计算机要使用一定的编码方式进行存储。原码，反码，补码是机器存储一个具体数字的编码方式

原码

原码就是用第一位表示符号，其余位表示值

1 2	[+1]原 = 0000 0001 [-1]原 = 1000 0001

反码

正数的反码是其本身
负数的反码是在其原码的基础上，符号位不变，其余各个位取反

1 2	[+1]反 = 0000 0001 [-1]反 = 1111 1110

补码

正数的补码就是其本身
负数的补码是在反码的基础上+1

[+1]补 = 0000 0001
[-1]补 = 1111 1111
[0] 补 = 0000 0000
[-8]补 = 1000 0000

三、为何要使用原码，反码和补码

对于正数三种编码方式的结果都相同

[+1] = [00000001]原 = [00000001]反 = [00000001]补

但是对于负数:

[-1] = [10000001]原 = [11111110]反 = [11111111]补

原码是被人脑直接识别并用于计算表示方式，为何还会有反码和补码呢?

由于计算机识别符号位会变复杂，因此计算时使用加法替代减法

如果用原码表示，对于减法来说，结果是不正确的。这也就是为何计算机内部不使用原码表示一个数

1	1 - 1 = 1 + (-1) = [00000001]原 + [10000001]原 = [10000010]原 = -2

为了能够使正负相加得 0，出现了反码：

1	1 - 1 = 1 + (-1) = [0000 0001]反 + [1111 1110]反 = [1111 1111]反 = [1000 0000]原 = -0

发现用反码计算减法，结果的真值部分是正确的，却会出现 +0 和 -0

虽然人们理解上+0和-0是一样的，但是0带符号是没有任何意义的。而且会有[0000 0000]原和[1000 0000]原两个编码表示0

我们希望只有一个 0，所以发明了补码

之前相加会得到各个位都是 1，所以规定补码为在反码的基础上 +1，这样相加之后每个 1 都会变成 0，多出的进位直接抛弃

1	1 - 1 = 1 + (-1) = [0000 0001]补 + [1111 1111]补 = [0000 0000]补=[0000 0000]原

这样0用 [0000 0000] 表示，而以前出现问题的-0则不存在了。而且可以用[1000 0000]表示-128:

1	(-1) + (-127) = [1000 0001]原 + [1111 1111]原 = [1111 1111]补 + [1000 0001]补 = [1000 0000]补

使用补码，不仅仅修复了0的符号，而且还能够多表示一个最小值

这就是为什么8位机器下，使用原码或反码表示的范围为[-127,+127]，而使用补码表示的范围为[-128,127]

因为机器使用补码，所以对于编程中常用到的32位int类型，可以表示范围是: [-2^31,2^31-1] 因为第一位表示的是符号位。而使用补码表示时又可以多保存一个最小值

四、补码是怎么来的

同余

首先介绍一个数学中相关的概念: 同余

两个整数a，b，若它们除以整数m所得的余数相等，则称a，b对于模m同余

记作 a ≡ b (mod m)

读作 a 与 b 关于模 m 同余

举例说明:

1
2
3

4 mod 12 = 4
16 mod 12 = 4
28 mod 12 = 4

所以4，16，28关于模 12 同余

负数取模

加上 mod 右边的数的倍数即可

1 2	-3 mod 2 = (-3+2*2) mod 2 = 1 -2 mod 12 = (-2+12) mod 12 = 10

补码与取模

如果当前时间是6点，我希望将时间设置成4点，我们可以:

往回拨2个小时: 6 - 2 = 4
往前拨10个小时: (6 + 10) mod 12 = 4

在这个例子中，我们忽略了钟表是否多转了一圈，只考虑了当前时间点对不对，实际上就是只考虑对 12 个小时取余的结果对不对

-2 被我们看成是 +10，因为 -2 和 +10 是关于模 12 同余

同理，在补码的计算中，在 n 位机器上，补码与原码是关于模 2^(n-1) 同余

以 8 位为例，负数的补码与原码相加得到 1000 0000，即 128，这个 128 就好比钟表的 12 个小时

我们首先忽略符号位，只考虑剩下7位的值对不对。比如加 -1 和加 +127 就是等价的

2-1 = 2+(-1) = [0000 0010]原 + [1000 0001]原= [0000 0010]补 + [1111 1111]补

忽略符号位，-1 的原码是 000 0001，好比向前拨 2 个小时；补码是 111 1111，好比向后拨 10 个小时

那么， 2 + (-1) 与 2 + (127) 在 7 位比特位中的值一定是一样的。我们忽略了溢出，只考虑了对 111 1111 取余；正如我们忽略钟表多转一圈还是少转一圈，只考虑了对 12 个小时取余

符号位

在补码和取模的讨论中，包括钟表的例子，我们都只看了余数，而回避了符号位的问题，现在着重看下符号位的计算

我们知道，在补码中，正数的符号位是 0，负数是 1

正数和正数、负数和负数相加可能会有溢出问题，比如 127+1，-127-1，此时的符号位都是不对的，溢出的情况我们不考虑

a+b，有以下 3 种可能

a+b = 0
a+b < 0
a+b > 0

以 8 位为例

我们知道由于引入了补码，所以 a+b = 0 的结果必然是 [0000 0000]

以 -3+1 为例，-3+1 = -2+(-1)+1 = -2 + 0，由于 0 是 [0000 0000]，注意我们舍弃了相加等于0的进位，所以符号位由 -2 确定

a+b > 0 同理

这就是补码运算中符号位是正确的原因

五、当遇上位运算

Q：`~1` 和 `~-1` 是多少

~ 是按位取反

1 的补码是 0000 0001，按位取反后是 1111 1110，这是一个负数补码，其原码是 1000 0010，即 -2

-1 的补码是 1111 1111，按位取反后是 0000 0000，这是一个正数补码，其原码是自己，即 0

Q：`9>>>2` 和 `-9>>>2` 是多少

>>> 是无符号右移

9 的补码是 0000 1001，无符号右移 2 位后是 0000 0010，这是一个正数补码，其原码是自己，即 2

-9 的补码是 1111 0111，无符号右移 2 位后是 0011 1101，这是一个正数补码，其原码是自己，即 61（以 8 位机器为例）

注意：无符号位移后是补 0

Q：`9>>2` 和 `-9>>2` 是多少

>> 是有符号右移

9 的补码是 0000 1001，有符号右移 2 位后是 0000 0010，这是一个正数补码，其原码是自己，即 2

-9 的补码是 1111 0111，有符号右移 2 位后是 1111 1101，这是一个负数补码，其原码是 1000 0011，即 -3

注意：有符号位移后，正数补 0，负数补 1
注意：对于补码来说，正数前面补 0 不会影响其值，负数前面补 1 不会影响其值