原码、反码、补码还不会？我拿着我家的钟表给你讲

本篇文章主要总结原码，反码和补码，对这一块不熟悉的，快来看看吧！
本片文章原创，如果要转载，请注明出处

1. 计算机是如何存储整数的

计算机是怎么存储信息的呢？计算机是用状态存储信息的，它只有两个状态，高电平和低电平，这样的一个状态叫做一个比特(bit)，实际上计算机就是用一个或一组比特序列来存储信息的，对于整数也是如此。把人易于识别的信息转换成计算机的比特序列的过程叫编码，对于整数，最常用的就是原码，反码和补码，除此之外还有BCD码等其他编码方案。

1.1. 原码

严格来说，对于有符号数(就是有正整数和负整数以及0的概念)才有意义，无符号数因为没有符号，就没有这个概念了。那么原码是怎么表示有符号数的呢？原码是符号位+绝对值的表示方法，即最高位表示符号位，剩下的位表示数的绝对值，对于正数，符号位是0，负数符号位是1，如下图所示的+1和-1的表示：

采用原码的方案，假设我们用$n$位长的比特序列来表示一个有符号整数，由于第一位被符号位占用，剩下$n-1$位表示数值，这$n-1$位可以组合出$2^{n-1}$种不同的状态，所以原码表示整数的范围显然是：$[-(2^{n-1}-1),2^{n-1}-1]$，为啥要减去1，因为我们表示的数是从0开始的。这样的表示方法很容易理解，但是计算机理解起来就费劲了😄，对于计算机来说，有下面几个缺点：

• 因为最高位有两种取值，所以当绝对值是0时，就有+0和-0的编码，但是符号对于0来说是没有意义的，这就造成一个编码空间的浪费。
• 表示数是为了执行运算，对于原码来说，计算机在执行加减时，需要把符号位特殊处理。在计算机芯片实现方面，为了简化电路设计，比较好的编码方案是，让计算机无视符号位的存在，把有符号的数，当成一个无符号数一样根据布尔代数的规则执行计算，然后还能得到正确的结果。显然原码这样的编码方式是不能实现的，例如算1-1，减法可以通过加一个负数来实现，即1-1=1+(-1)：
  这样的结果显然是不对的。

1.2. 反码

在说反码之前，先讲一下补数的概念，那什么是补数呢？来看一个钟表的例子

上面图片中有一个地方说错了，是1和11互为补数，而不是-1。不好意思。😅
根据上面的钟表的例子，一个数的补数是相对的，需要一个参考值，例如1的补数是11，是相对12来说的。那么显然的，假设一个从0开始的计数系统所能表示的数的个数是$N$，那么对于这个计数系统一个正整数$x$，其补数就是$n-x$。
下面再来说反码是如何表示一个整数的，反码规定：

• 对于正整数，其反码跟其原码是一样的
• 对于负整数，其反码，就是符号位1不变，剩余的数值位，依次取反(就是0变1，1变0)

对于正整数，表示的范围和原码是一样的，对于负整数，一个比特序列和其按位取反后的比特序列是一一对应的，所以表示的范围和原码是一样的，当然反码中也存在+0和-0的概念，只不过-0是用11111111来表示的。所以反码在表示数值的范围上和原码是一样的。
那反码第二条规则，符号位不变，数值为依次取反的目的是啥呢？请看下图：

我们用8位的比特序列来举例说明，求一个负数的补码的过程就是，用符号位不变，用0111 1111(127)减去其数值位，根据我们刚才说的补数的概念，这就是求相对于127的补数。但是长度为7的比特序列，可以表示的数的个数是$2^7=128$个，求127的补数是不对的，况且也没有把符号位考虑进去，反码不能实现前面所说的无视符号位的计算的目标，可以随便验证几个就知道了：

1. 例如用反码计算1-1，-1在反码中是用1111 1110表示的，计算结果依然是反码，结果是1111 1111，这个结果是多少呢？我们无法一眼看出来是多少，由于反码实质上是求相对于127的补数，所以对于一个反码表示的负整数，再求一次反码，就可以得出相对应的原码的序列，就可以看出来其绝对值了。那1111 1111求反码以后，就是1000 0000，数值位是0，所以就是-0（给0加上符号是没有意义的），如下图所示
   
2. 我们再用反码计算2-1，-1在反码中是用1111 1110表示的，计算结果依然是反码，结果是0000 0000，这个结果当然也是反码表示，只不过符号位为0，表示正整数，对于正整数，反码与其原码一样，所以就是0，但是2-1=0显然是不对的。如下图所示：
   

1.3. 补码

正如其名称那样，补码的核心含义就是负整数用其相对应的正整数的补数来表示，因此补码就可以把减去一个数，用加上这个数的补数来实现了。那补码是如何实现这一目标的呢？我们来看一下补码的编码规则，补码规定：

• 对于正整数，其补码跟其原码是一样的
• 对于负整数，其补码，就是其反码+1

第二条规则中的+1是啥意思，为啥要+1？是这样的：
如果想在计算的时候让符号位跟数值为一起按照加法规则参与运算，那就需要把有符号数连同符号位看成一个无符号数。既然不考虑符号的问题¹，

• 那么对于正整数和0来说，其原码表示就可以表示其真正的值了；
• 对于负整数而言，就表示成其相对应的正整数的补数。还按照8位比特来举例，8位比特序列能表示$2^8=256$个数，那对于负整数$-N$而言，其编码形式就是其相对应正整数$N$的补数，即$2^8-N$，请看下图求-1补码的过程，
  

连同符号位取反+1，跟前面说的反码+1不一样呀？，其实他们的效果是等价的。因为在求反码的过程中，是保证了符号位不变，剩余的数值为取反，因为按照反码规则，负整数的符号位是1，本身就跟正整数的符号位是相反的，如果在取反的过程中考虑符号位，那么对于一个负整数来说，其反码的比特序列，就是把对应正整数的比特序列连同符号位取反，所以，求负整数的补码，也可以说是将其反码+1。
现在补码的规则我们是了解了，但是这个补码真的可以无视符号位的存在，让计算机按照计算无符号数的方式来完成有符号数的计算吗？答案是肯定的。

• 首先对于正整数和+0而言，他们的表示和无符号数的表示是一样的，所以对于正整数的加法而言，结果是正确的。
• 其次对于正整数加负整数而言，例如正整数x和负整数-y，x-y = x的补码加上（-y）的补码，而-y的补码就是y的补数，即$2^8-y$，即$x-y=x-y+2^8$，如果：
  • $x-y=0$，那么结果就是$2^8$，对于8位的比特序列来说，$2^8$表示就是0000 0000（高位舍去了），也就是0；
  • $x-y=n>0$，那么结果就是$2^8+n$，对于8位的比特序列来说，$2^8+n$表示就是正整数$n$的反码表示形式（高位舍去了）；
  • $x-y=-n<0$，那么结果就是$2^8-n$，这不就是n的补数吗？n的补数就是负整数-n的补码表示形式。

对于8位比特序列来说，可以组合出$2^8=256$种状态，也就是说可以表示256个有符号整数，

• 当符号位为0时，剩下的7位比特序列可以组合出$2^7=128$种状态，即可以表示128个数，算上0，那就是可以表示$[0,2^7-1]$即，$[0,127]$；
• 当符号位为1时，剩下的7位比特序列可以组合出$2^7=128$种状态，可以表示128个数，但是这128个状态并没有跟当符号位为0时的128个状态一一对应，因为0(0000 0000)的补码还是0000 0000，(补码解决了0的符号问题)，这就导致当符号位为1时，那128个状态种有一个状态表示的负整数找不到其对应的正整数，这个比特序列就是1000 0000(在原码中，它原本是表示-0的比特序列)，它就是-128的补码，可以看出，它的补码也是它本身（没有对应的正整数）。所以当符号位为1时，可以表示的数的范围$[-2^8,-1]$，即$[-128,-1]$。

综合起来，当比特序列的长度为$n$时，补码可以表示的有符号数的范围$[-2^{n-1},2^{n-1}-1]$，为了便于理解，我这里把8位长度的补码表示，按照从0开始，依次加1的数值变化表贴在这里：

正是因为补码的这些优点，所以现在计算机对于有符号数，一般都是采用补码表示的，当然在JVM中也是用补码。

2. 补码运算的溢出问题

溢出是什么？溢出表示的是：某个长度的比特序列表示的两个数相加的结果超过了，这个比特序列所能容纳的数的范围，得到了不正确的结果的现象。就以8位长度表示的有符号数来举例子，前面我们说过了，对于一个正整数a(算上0)来说，它的范围$[0,127]$，对于一个负整数b的范围$[-128,-1]$，那a+b的范围，即：
$$-128<=a+b<=126$$
这个范围在补码表示的有效范围内的，所以相异符号的两个数相加不会溢出，溢出出现在相同符号的两个数相加的情况下。例如：

• 给127(二进制表示：0111 1111)，加上1(二进制表示：0000 0001)，结果是1000 0000，本来应该是128的，但这个结果超过了补码表示的最大正整数127，因此实际上是-128，这就是上溢；
• 给-128(二进制表示：1000 0000)，加上-1(二进制表示：1111 1111)，结果是0111 1111，本来应该是-129，但这个结果超过了补码表示的最小负整数-128，因此实际上是127，这就是下溢，见下图所示。

那计算机是如何检测溢出的呢？通过看上面的127+1和-128-1的例子我们可以发现，

• 对于正整数和0来说，如果两个正整数或0相加得到的结果，超过了数值为所能表达的最大的数，那么数值位的最高位必然会产生进位，这是显然的，8位比特表示的正整数最大值是127，编码0111 1111，数值为全是1，当结果超过127时，那第7位必然产生进位；对于正整数相加而言，因为正整数或0的符号位都是0，因此相加符号位不会产生进位；
  
• 对于负整数相加来说，如果两个负整数相加没有发生溢出，那结果必然也是负整数，因为负整数的符号位都是1，在运算时符号位必然产生进位（两个1相加结果是0，进位1），因为此时符号位为0，在不溢出的情况下，结果的符号位应该是1，因此数值位的最高位必然产生了进位，这个进位加到符号位上，使其变成1，才保证了不溢出情况下，结果的正确性。因为负整数相加符号位产生进位是必然的，所以，在溢出的情况下，数值位的最高位必然没有产生进位，这才使得符号位变成0，结果出错。逻辑有点绕，大家细品^_^。
  

为了便于理解，我把用补码表示的两个数A,B它们的符号位，以及数值位的最高有效位产生的进位与溢出的真值表贴在下面：

根据真值表，溢出标志F = c^cf，就是把数值位的最高有效位产生的进位与符号位产生的进位相异或，但是一般来说，处理器在实现的时候，是不会单独用一个标记来维护有符号数的数值位的最高有效位产生的进位的。其实数值位的最高有效位产生的进位cf，会加到符号位上去，因为两个相同符号的数相加时，符号位是一样的，符号位相加后的结果是0，那么最终结果的符号位的值就反映了结果的数值位的最高有效位产生的进位。实际上，大部分处理器也就是这么干的，处理器会把相加的结果的符号位产生的进位存入CF标志位，然后把CF和结果的最高位进行异或操作，再把结果存入溢出标志位(OF)。 大家可以参考《汇编语言 基于x86处理器》第85页。

最后还有一个与溢出有关的题目：有两个有符号整数a和b，如何在不申请额外空间的情况下，交换a和b的值，方法写在下面：

void switchTwoNum(int* pa,int* pb){int a = *pa,b = *pb;a=a+b; //a的值现在是a+bb=a-b; //b现在的值是a+b-b=aa=a-b; //a现在的值是 a+b-a=b*pa = a;*pb = b;
}

当a+b的值发生溢出的时候，还会得到正确的结果吗？答案是肯定的。当a和b异号的时候，不会发生溢出，所以只讨论a，b同号溢出的情况；

• 假设$a>=0，b>=0$，a=a+b，发生上溢，此时得到的a是个负数，b=a-b会发生下溢，使得得到的结果就是原来a的值，这是因为a+b-b=a，a既然是在补码范围内的数，经过两次操作，得到的结果还在补码范围内，因此第一次发生上溢，第二次就会下溢(怎么溢出去的就怎么溢回来😄)，结果是一样的
• $a<0，b<0$的情况类似，就不赘述了。

这种交互数值的方法，使处理器在做三次赋值运算时，多做了三次算术运算，但是我一般还是不会去节省那一个int类型的空间的哈，直接申请一个临时变量搞定。

好了以上就是要讲的所有内容的，你听懂了吗？如果有什么遗漏或错误，欢迎各位大神不吝赐教，如果你觉得我讲的好，有价值，不妨动动小手指点个赞，支持一下吧！

3. 参考文献

1. 原码、反码、补码
2. 《汇编语言 基于x86处理器》