深入理解机器码（原码，反码，补码）和算术溢出

如果你是一个计算机专业的本科生，那么你可能大一时就在《数字逻辑》（或《数字电路》）这本书里面学习了机器码。可能当时学的一头雾水，但是现在回过头去又觉得很Easy，就不以为然了。不幸的是，就是这么简单的知识点，贯穿了整个大学生涯，所以我们要牢记这些知识，以下内容包含在：数字电路，计算机组成原理，汇编语言，操作系统原理等课程中。

x---------------------------x
此处添加《数字逻辑》的笔记，在寝室
x---------------------------x

友情提示：以下内容部分摘自：
1.赵岩《C语言点滴》第三章
2.Wikipedia
侵删

1.1 原码、反码和补码的解释

介绍补码之前，先简单介绍一下计算机内部使用的二进制。人类用十进制完全是因为我们有10个手指头。如果有一天你看到一个外星人，它只有4个手指头，那么他使用的一定是四进制，如图1-1所示。

图1-1 进制和手指头的关系

如果能看明白图1-1，说明你已经明白了进制和手指头的关系了。现代的计算机内部使用门电路，它们只能表示0或者1两个状态。如果计算机是一个人，那么他只有两个手指头，所以它使用二进制。所谓的进制，根本就不是什么神秘的东西。

理解了计算机内部使用的二进制，下面来看看原码、反码和补码的官方定义。

• 原码（True form）：原码是一种计算机中对数字的二进制表示方法，数码序列中最高位为符号位，符号位为0表示正数，符号位为１表示负数；其余有效值部分用二进制的绝对值表示。

• 反码（1's complement，在中国大陆称作反码，港台地区称为一补数）：如果机器数是正数，则该机器数的反码与原码一样；如果机器数是负数，则该机器数的反码是对它的原码（符号位除外）各位取反而得到的。

• 补码（2's complement，在中国大陆称作补码，港台地区称为二补数）：如果机器数是正数，则该机器数的补码与原码一样；如果机器数是负数，则该机器数的补码是对它的原码（除符号位外）各位取反，并在末位加1。

补码的反码：按位取反，末位加1。补码系统的最大优点是可以在加法或减法处理中，不需因为数字的正负而使用不同的计算方式。只要一种加法电路就可以处理各种有号数加法，而且减法可以用一个数加上另一个数的二补数来表示，因此只要有加法电路及二补数电路即可完成各种有号数加法及减法，在电路设计上相当方便。（补码的反码就是用来处理ALU的减法运算的）

这样的定义绝对正确，但是绝对也会让你一头雾水，其实我们可以通过画几个图把这些概念简单地阐述清楚。为了方便说明问题，我假定用4位二进制数表示一个整数[①]。

图1-2 无符号数的原码.png

图1-2说明了无符号数的原码表示方法。其中内圈的数字为二进制数，外圈的数字为内圈二进制数所对应的十进制数[②]。

顾名思义，无符号数不能表示负数。为了解决这个问题，我们把最高位定义为符号位。如果最高位为1就代表是一个负数，其他三位表示对应的十进制数。如图1-3所示，这就是有符号数的原码表示。

图1-3 有符号数的原码表示.png

但是用原码来表示一个有符号数会带来两个问题。

• 第一个问题就是正负相加不等于零。如图1-3所示，1+(−1)，就是0001+1001=1010，按照原码表示等于−2。
• 第二个问题就是有两个零存在，分别为0000和1000。可见，原码不适合用来表示有符号数！

为了保证正负相加等于零，我们采用了反码的表示方法，反码的表示如图1-4所示。如果把二进制数1000想象成12点，把二进制数0000想象成6点，原码就是从12点开始顺时针排列−1到−7，而反码就是从6点开始逆时针排列−1到−7。这样做的好处就在于现在正负数相加等于零了。例如1+(−1)，就是0001+1110=1111，用反码表示的话就是(−0)了。

图1-4 有符号数的反码表示.png

第一个问题解决了，但是第二个问题还是没有解决，在用反码表示有符号数的图1-4中，依然有两个零存在，分别为0000和1111。聪明的读者一定已经猜到了，补码就是为了解决这个问题而发明的。

按照补码的定义，−1的反码为1110，不过现在必须在末位加1，那现在−1就是1111了。以此类推，补码的表示如图1-5。与反码表示不一样的是，补码在负数上从−1表示到−8，−0不再存在了。

图1-5 有符号数的补码表示.png

虽然第二个问题解决了，但用补码表示时，正负相加还等于零吗？我们可以自己验证一下，如果丢弃最高位的进位，结果满足正负相加等于零。至此，我们找到了终极的解决方案，那就是利用补码来表示一个有符号的整数。注意一点，对于无符号数，原码、反码、补码都是一致的。所以我们得到的最后结论是：整型数在计算机中，使用补码表示。

1.2 整型数的溢出(Overflow)

如果1.1节你已经完全明白了，那么下面我们开始讨论在实际编写程序中非常危险的一个bug，那就是C语言的整型数溢出问题。

首先，我们知道，有符号数在计算机内部都是通过补码来表示的。其次，在图1-5中，如果加上x，就代表着顺时针走x格；如果减去x，就代表着逆时针走x格。有了这些知识，让我们用实例说话。在图1-5中，如果3+1，那就是从3顺时针走一格，等于4，没有任何问题。但是如果是7+1呢？顺时针走1格后，变成了−8了。如果7+7呢，顺时针走7格，等于−2了。这就是整型数发生了溢出。

所谓的溢出，就是因为4位二进制数，用补码表示一个整数的时候，所能表示的最大正整数就是2^(4-1)-1=7，如果在7的基础上再加1，就会发生“轻微溢出”，变为了最小的那个负数，如果两个最大的正整数相加，就会发生“严重溢出”。结果等于−2。这里注意，所谓的“轻微溢出”和“严重溢出”都是从溢出的角度去定义的。事实上，它们都是非常严重的bug，在实际编程中并不是说“严重溢出”就比“轻微溢出”更严重。

那么，C语言中int所表示的“最大正整数”到底是多少呢？不同的平台，不同的编译器，会有不同的定义。为此，C语言在头文件limits.h中给出了相关的宏定义，如表1-1所示。

*表1-1 整型数的极限值宏定义:

| char | int | short| long | long long |
|----------|
| SCHAR_MAX | INT_MAX | SHRT_MAX | LONG_MAX | LLONG_MAX |
| SCHAR_MIN | INT_MIN | SHRT_MIN | LONG_MIN | LLONG_MIN
|UCHAR_MAX | UINT_MAX | USHRT_MAX | ULONG_MAX | ULLONG_MAX
| CHAR_MIN| - | - | - | - |
| CHAR_MAX| - | - | - | - |

有了这些宏定义，我们就可以编写出程序1-1，程序中分别演示了加法带来的溢出和减法带来的溢出。

程序1-1 溢出的实例

程序最后的运行结果如图1-6所示，最大的正整数为2^(32−1)−1=2147483647。其他的数这里不解释了，读者可以按照反码的原理，自己解释并验证一下。

图1-6 程序运行结果

1.3 溢出深入分析

通过1.2节，我们已经初步知道了造成溢出的主要原因，但是只知道原因是不够的。下面我们对溢出的现象进行深入分析。本节主要说明4个子问题：溢出的定义，溢出发生的边界，溢出的危害以及如何避免溢出。

1.3.1 溢出的定义

关于有符号整型数的溢出，程序1-1已经阐述得很清楚了，大家对这个问题也没有什么异议。但是对于无符号数，《C陷阱与缺陷》 在“整数溢出”一节中指出，在无符号算术运算中，没有所谓的“溢出”一说。我想Koenig的思路可能是这样，当下午1点的时候，没有任何人会说：“现在是12点溢出了。”因为我们已经常识性地知道，我们的钟表上是没有13 这个数字的。但是在C语言中，你能常识性地马上告诉我UINT_MAX是多少吗？下面我们看程序1-2。程序1-2中a是一个无符号整型数，运行这个程序后，会打印出“0”。

程序1-2 无符号整型数溢出的例子
unsigned a = UINT_MAX;
printf ("%u", a+1);

假设现在你每个月赚UINT_MAX，由于你的工作出色，老板决定下个月给你涨一块钱。根据这段程序，你下个月工资将会是0元。这个时候，如果老板说无符号算术运算中没有“溢出”的话，你会同意吗？所以我决定不再讨论“溢出”是否有符号，而是从工程的角度来看，如果经过程序运算和经过纸和笔运算的结果不一样，那么我们就认为整型数运算发生了溢出。除了运算的溢出，C语言中还有很多其他类型的溢出，读者可以参考本书网站上“扩展内容”网页中的“谈谈C语言的溢出”。

1.3.2 溢出的边界

图1-7和图1-8分别演示了有符号数和无符号数中的两种溢出，分别为上溢出和下溢出。上溢出是由于顺时针方向旋转（加法）造成的。下溢出是由于逆时针方向旋转（减法）造成的。

对于无符号数，溢出发生的地方在6点钟方向，如图1-7所示。

图1-7 无符号数的溢出边界.png

对于有符号数，溢出的边界在12点方向，如图1-8所示。

图1-8 有符号数的溢出边界.png

1.3.3 溢出的危害

溢出最令人沮丧的地方就在于，C语言不通过运行时检查来避免溢出[③]，所以程序1-2会正常地运行，没有任何提示和运行错误，你的工资莫名其妙地就变为零了。

当我学习C语言这门课的时候，邻座一美女同学，偷偷递给我一张纸条，纸条上写着程序1-3。我看了一眼对她说：“你没有考虑溢出啊！如果love溢出，会变成一个最小的负数。”然后我就把这个字条还给了那位美女同学。从此以后，她就再也没有联系过我。直到现在，我依然后悔，后悔只是关注了love的溢出，而没有关注time的溢出。

程序1-3 程序员的求爱信
while (time++) { love++; }

溢出的危害如此严重，它能让你从亿万富翁一下变为穷光蛋，也能让你错失到手的爱情，还有什么比这更严重的呢？那为什么C语言不去避免这种错误呢？这符合C语言的两个风格：信任程序员，只要快。因为C语言信任你，所以编译器认为你写出UINT_MAX+1是对的，就算你把铅笔插到自己的鼻孔里，编译器也是认为你是对的，没有运行时检查是为了保证速度。假如你出门旅游的时候带着妈妈，我敢说这一路你是安全的，但是你一定快不起来。C语言就是这样，把妈妈放到家里，把铅笔插到鼻孔里，走你！

1.3.4 避免溢出的方法

聪明的读者一定都看出来了，上面关于美女和纸条的故事是杜撰的。实际的情况是我根本就没上过C语言的课，完全是自学成才。学成后写了一个十万行的程序，送给我暗恋的女孩，她看后十分感动，然后拒绝了我。实际编写工程的时候，溢出发生的概率和美女给你递纸条的概率一样，都不是很高，所以你也不用过分担心这个问题。避免溢出的一个最根本原则就是了解你要处理问题的规模，如果要处理一个班的学生，你完全可以忽略溢出问题；但是如果要处理全世界的人口，那么你就应该提高警惕了。

一个比较简单的避免溢出的方法就是利用double数据类型。一般情况下，让double溢出还真是件比较困难的事。如果要求一定要用整型数来完成任务，那么你首先应该利用表3-1中的宏定义，了解一下C语言在你所用平台上的极限值，并且利用这些宏定义和程序3-4中列出的判断表达式来避免溢出的发生。请注意，程序3-4中的判断表达式有的时候代表溢出会发生，有的时候代表溢出已经发生。

程序3-4 避免溢出的技巧

现在让我们轻松一下吧。设想一下如果一个程序员生了四个女儿，你如何给她们起名字呢？大女儿就叫“玲玲”吧，二女儿叫“玲依”，三女儿叫“依玲”，那么四女儿呢？你一定猜到了，按照这个顺序，就应该叫“依依”了。没错了，在软件学院我的学生里面，就有一个叫“张依依”的女生，不知道她是不是她爸爸的第四个女儿。让我们继续下去，如果这个程序员生下了第五个女儿，那么应该叫什么呢？按照上面介绍过的内容，她应该叫“忆初”了！希望你们能通过这些美丽的女孩名字记住上面讲到的内容，并衷心祝愿这个程序员早日生一个男孩。

1.4 二进制数的溢出

1.4.1 有符号数才会溢出

二进制数的溢出一般出现在ALU的加法运算中，溢出仅针对有符号数的运算，一般有两种情况：

• 两个正数相加，结果为负数；
• 两个负数相加，结果为正数。

如图1-9所示，0011 加上0101如果用个四位加法器进行运算， 就会得到1000.如果我们把它们都看成无符号数那么0011就是3，0101就是5； 而1000就是8 。那么这个运算结果是正确的。 但如果我们把它看作有符号数 原操作数仍然是3和5单一运算结果1000他其实代表的是-8（参见图1-8）。 这个结果是不正确的，也就是发生了溢出。

图1-9

需要注意的是，“进位”和“溢出”的关系是：

• 有“溢出”时，不一定有“进位”；
• 有“进位”时，不一定有“溢出”。

图1-10

x---------------------------x
这段话太罗嗦，重新修改
x---------------------------x
如图1-10，1110加上1100送到 四位的加法器中运算的结果1010 ，同时有一个进位1。 这显然是有进位 但它却是无溢出的情况。为什么呢？我们来看，如果把它当作无符号数进行运算 1110是14，1100是12 如果带上进位一起考虑那就是正确的运算结果26。 如果不带进位则是为10 。因为四位的二进制位只能表示小于16的数， 所以无符号数的的运算结果可以默认为对结果进行 模16的运算。那只看着四位的话结果是10，相当于26 模16的值。 所以这也是正确的。而对于有符号数来说相当于-2加上-4 而这四位的结果就是-6 ，这个运算也是正确的。 当然，从另一个角度来看因为溢出是针对有符号的数目的运算结果，超出了能表示的 范围，我们也可以把有进位这种情况看作无符号数的运算超出了能够表示的范围。

1.4.2 二进制数溢出的判断

在ALU中，进位是很容易判断的，加法器本身就提供了这样的机制。 最高位的全加器的进位输出就是整个加法器的进位。那么溢出又该如何判断呢？其实很简单，利用全加器就能判断，即：“最高位的进位输入”不等于“最高位的进位输出”。

图1-11

就是最高位全加器的进位输出。 把这两个信号连出来，判断它们是否不相等。那么用什么 方法来判断不相等呢？其实非常简单，就连接一个异或门就可以了。 当它们不相等时，异或门的输出为1 当他们两个都为0或者都为1时，异或门的输出为0 因此，就可以用这个信号来表示是否发生了溢出。 至于为什么用这个方法就可以判断溢出，留给大家自己思考。

1.4.3 CPU对溢出的处理方式

不同体系结构有不同的方法。我们先来开MIPS处理溢出的方式。

（1）将操作数看做有符号数，发生“溢出”时产生异常

• add rd,rs,rt # R[rd]=R[rs]+R[rt]
• addi rt,rs,imm # R[rt]=R[rs]+SignExtImm

（2）将操作数看做无符号数，不处理“溢出”

• addu rd,rs,rt # R[rd]=R[rs]+R[rt]
• addiu rt,rs,imm # R[rt]=R[rs]+SignExtImm

它提供了两种不同的指令。如果编程人员想将操作数看作有符号数，需要处理溢出， 则需要使用add和addi这样的指令。 当这样的运算发生溢出时，会产生异常。 就是说，控制电路会检查加法器产生的overflow的信号。 如果overflow信号有效，控制电路就会当做一个异常的情况进行处理。 至于如何处理，我们会在讲到中断和异常时再做分析。 如果编程人员希望将操作数看作无符号数，也就是不对溢出进行处理。 那就需要使用这两条指令，addu和addiu。它们分别和上面这两条指令是对应的。 唯一的区别就是，在执行这两条指令时，控制电路不会检查加法器输出的overflo- w信号。 所以说，MIPS处理溢出的方式是提前做准备。 按照是否要处理溢出，采用不同的指令进行运算。

而x86则采用了另一种方式。它并没有根据是否处理溢出分为两种 运算指令，x86的运算指令，如果产生了溢出， 并不会直接由控制电路检查到并进行处理。 而是将加法器产生的溢出信号传送到了标志寄存器。 如果发生溢出，则会致标志寄存器当中的OF位为1. 如果没有发生溢出，则致OF位为0. 这就是x86的标志寄存器，其中第十一位是 OF位，这就是溢出标志。 则在后续的指令中，需要检查标志寄存器的OF位是否为1并进行相应的操作。

溢出标志OF（Overflow Flag）

• 如果把操作数看做有符号数，运算结果是否发生溢出
• 若发生溢出，则自动设置OF=1；否则，OF=0

图1-12

延伸阅读
1.《C语言点滴》，赵岩，人民邮电出版社；
2.《汇编语言》，第三版，王爽，清华大学出版社；
3.《深入理解计算机系统》（Computer Systems: A Programmer's Perspective），第三版，[美]Randal E.Bryant / David O'Hallaron，机械工业出版社；