从计算机为什么用补码存储数据，衍生到存储单元数据溢出

引言

先说几句屁话，觉得啰嗦可以忽略跳过这段屁话。
俗话说：眼看他起高楼，眼看他宴宾客，眼看他楼塌了。我想这句话放在我们做技术的，也很合适——基础不牢，地动山摇。
尽管我们很多人不是做基础开发的，但是操作系统、数据结构和算法、计算机网络、设计模式……这些IT领域的基础性学科，对于我们来说其实挺重要的，比如做优化、跨语言学习、工程框架搭建……。基础虽然不能决定眼前，但是能够决定我们在这条路上走多远。框架那么多、特效那么多，真心没有兴趣一个个都摸一遍，所以偶尔回过头去翻看这些基础性的东西是挺有意思的。

• 是否还记得在学操作系统的时候，很困惑计算机为什么要用补码存储数据，而不是用我们人更容易理解的原码来进行存储呢？

关于这个问题，相信很多教这门课的老师以及工作多年的coder也解释不清，甚至不知道这个概念。

• 本文将尝试从理性结合感性的角度去说明计算机为什么用补码存储数据，当我们明白这个问题后，那么，我们就可以去理解另一个衍生问题——数据溢出。我们先来看一段关于数据溢出的Java代码片：

/*char是无符号数，16位存储，表示范围是0～2^16-1（即0～65535）*/
char ch = Character.MAX_VALUE; // ch为65535
ch += (char) 1; // 加1后，引起数据溢出，则ch为0

/*int是有符号数，32位存储，表示范围是－2^31~2^31-1（即－2147483648～2147483647）*/
int i = Integer.MAX_VALUE; // i为2147483647
i += 1; // 加1后，引起数据溢出，则i为－2147483648

• 至于上述代码片的执行结果为什么会这样，暂时不解释，希望通过文章循序渐进的过程来说明溢出的问题。

fuck概念

• 计算机用二进制来表示数据，这个大家应该都了解（不了解的找块板砖拍死自己算了）。

• 没有特殊说明，本文都以4位存储单元来说明
• 下面几个小节会提到一些关键概念，不要对这些概念恐慌，这些概念会结合例子或者对比的形式，尽量以通俗简洁的文字来说明，保证人人都能看的懂

加法器

• 计算机只有加法器没有减法器，两个数的减法运算会被计算机转换为加法运算。（先埋个伏笔——通过补码进行表示，即可将减法运算转换为加法运算）

模、补数

• 在日常生活中，有许多化减为加点例子。我们以最平常的钟表为例，时针逆时针拨x（0<x<12）格和时针顺时针拨12-x格，效果是相同的。比如，时针从10点调整到5点有以下两种方法：

  1. 时针逆时针拨5格，相当于做减法：10 -5 = 5
  2. 时针顺时针拨7（即12 - 5）格，相当于做加法：10 + 7 = 12 +5 = 5（MOD＝12）

• 总结，x + (MOD - x) = MOD就是模，x和MOD - x就是一对“互补”的数，即原数x的补数为MOD - x或者原数MOD - x的补数为x。通过对钟表拨时针的例子可以发现，用补数（7）代替原数（5），可把减法转变为加法（出现的进位就是模，进位舍弃）。

二进制数的模，先来看下两个个例子（此处我们忽略符号）：

1. 2位存储所能表示的最大数是11（10进制：3 = 2^2 - 1），比他大1的是11 + 1 = 100（10进制：4 = 2^2），那么这个100则是2位存储所能表示的所有数据的模。
2. 4位存储所能表示的最大数是1111（10进制：15 = 2^4 - 1），比他大1的数是1111 + 1 = 10000（10进制：16 = 2^4），那么这个10000则是4位存储所能表示的所有数据的模。

通过对上面两个例子可以推论：一个二进制数的最高位位数用n表示，那么该二进制数的模就是2^n。

原码、反码、补码

• 先来看一张国内外教材对比的表（出自《计算机教育》2015年第10期的文章——《原码、反码和补码的教学讨论》）

国内外教材对比.png

注意下ones' complement和 two's complement的撇号（'）的位置（学过英语的都知道，撇号（'）在s前和s后的含义是不一样的）

• 给定一个有符号数x，来对比下国外和国内教材对原码、反码、补码的表示：

  • 国外教材
    • sign and magnitude representation（原码）：最高位位符号位（0表示正数，1表示负数），剩余位（数据位）为x的大小。
    • ones' complement representation（反码）：如果x为正数，则是其二进制表示；如果x为负数，则是其对应正数的bit complement/bitwise NOT（按位取反）——执行每一位逻辑否定的一元操作。可用公式表示为：
      • [x]反 = (2^n - 1) - |X|（其中n为将符号位算在内的位数，|X|为绝对值）
    • two's complement representation（补码）：如果x为正数，则是其二进制表示；如果x为负数，则是其对应正数的二的补（所有位取反后加1）。可用公式表示为：
      • [x]补 = (2^n) - |X| ＝ [x]反 + 1（其中n为将符号位算在内的位数，|X|为绝对值）
  • 国内教材
    • 原码：最高位为符号位，剩余位（数据位）为x的绝对值。
    • 反码：如果x为正数，则与原码相同；如果x为负数，符号位保持不变，数据位取反。
    • 补码：如果x为正数，则与原码相同；如果x为负数，符号位保持不变，数据位取反，然后加1（若符号位有进位，则舍弃进位）。

• 对比国内外教材的表述，是否发现高下立现：

  • 国内教材画蛇添足，并且容易引起误解：
    1. 原码是反码和补码的基础，反码和补码由原码转化而来
    2. 原码、反码和补码的符号位相同
  • 国外教材，则非常通俗：
    1. 求解一个数的反码和补码，根本不需要知道原码，直接通过它们的两个对应公式即可，甚至可以说原码与反码和补码没有半毛钱关系，反倒是反码和补码存在关系——补码 = 反码 + 1
    2. 原码的出发点是符号的表示（符号位），即用0表示正数，用1表示负数；反码和补码的出发点是减法的运算，即用两个正数的加法取代两个数的减法

狗日的国内教材和翻译，真是误人子弟啊

计算机为什么用补码存储数据

• 上面铺垫了这门久，终于要进入第一个正题——计算机为什么用补码存储数据。为了不引起混淆，我们就以国外教材对于原码、反码和补码的表示法来进行说明。简单起见，以4位存储表示有符号数为例，通过原码、反码和补码的表示法来生成一张表：

|有符号数（十进制）|sign and magnitude representation（原码）|ones' complement representation（反码），[x]反 = (2^n - 1) - \X|two's complement representation（补码），[x]补 = (2^n) - \X|
|:-:|:-:|:-:|:-:|
|+7|0111|表示方式不变|表示方式不变|
|+6|0110|表示方式不变|表示方式不变|
|+5|0101|表示方式不变|表示方式不变|
|+4|0100|表示方式不变|表示方式不变|
|+3|0011|表示方式不变|表示方式不变|
|+2|0010|表示方式不变|表示方式不变|
|+1|0001|表示方式不变|表示方式不变|
|+0|0000|表示方式不变|表示方式不变|
|-0|1000|1111|0000（求解过程：[x]补 = 2^n - \x\ = 2^4 - \-0\ = 2^4 - (+0)，使用二进制则为10000 - 0000 = 10000，超过4位（有进位），那么舍弃进位1，最终结果就是0000）|
|-1|1001|1110|1111|
|-2|1010|1101|1110|
|-3|1011|1100|1101|
|-4|1100|1011|1100|
|-5|1101|1010|1011|
|-6|1110|1001|1010|
|-7|1111|1000|1001|
|-8|超出4个bit所能表达范围|超出4个bit所能表达范围|1000|
|备注|零重码，二进制存在两种表示方法：0000和1000|零重码，二进制存在两种表示方法：0000和1111|零无重码，同时解决了原码和反码不能表示-8的问题|

• 通过上述表格，可以很自然的总结出一个结论：补码表示法（two's complement representation）可以防止0的机器数重码，同时又解决了原码和反码无法表示－8的问题，这样就极大的简化了计算机的硬件设计。

• 结合之前提到的时钟例子，我们把补码表示法（two's complement representation）所表示的四位存储单元，按照从0000到1111递增的方式，均匀的分布在时钟的表盘上。于是，我们就可以得到下面这张图（图片来自于这里）：

two's complement wheel

• OK，继续以时钟的方式来观察上图：

  • 顺时针方向位加法，逆时针方向为减法
  • 模为2^n：在1111处顺时针拨一格，就到了0000。用数学的方式，即1111 + 1 = 10000，进位舍弃则结果为0000，那么四位存储的模就是10000（2^4）
  • 减法转换为加法：3 - 1 = 3 + （-1） = 0011 + 1111 = 0010，眼尖的人可能会说0011 + 1111明明等于10010，怎么会是0010？还记得之前提过的最高位进位舍弃嘛，因此对于4位存储来说，进位舍弃后就是0010 = 2。

    若减法不转换为加法，那么3 -1 = 0011 - 0001 = 0010 = 2

  • 数据溢出：当0111（7）加1时，按照我们人的思维来说，应该结果为8，但是对于机器来说则不是，因为0111（7）是四位存储所能表示的最大有符号数，所以它是无法表示01000（8）的，这个时候我们就说数据溢出了。那么数据溢出该怎么办呢？很简单，机器的思考方式显然和我们人脑不一样，机器按照上面环形图的方式，由于0111（7）加1是顺时针造成的数据溢出，那么我们可以把机器的操作想象成在0111（7）处顺时针拨了一格，我们再去对照下环形图发现这时候指向了1000（－8）。

    把这个过程想象成拨时针就OK了，对于1000（－8）减1也是同样道理

• 至此，我们完全可以总结一下，并解答计算机为什么用补码存储数据：

  1. 计算机只有加法器没有减法器，两个数的减法运算会被计算机转换为加法运算，而补码正好能够解决减法转换为加法的问题
  2. 防止机器发生零重码，同时解决了原码和反码不能表示-8的问题，这样极大的简化了计算机的硬件设计
  3. 以循环的方式解决数据溢出的问题

从补码的角度解答代码片中的数据溢出

• 既然已经知道了计算机为什么用补码存储数据，那我们就可以回过头去消灭文章开头的数据溢出的代码片了。由于代码片中ch和i的问题是一样的，那我们就选择ch来进行分析，另一个留给你们分析。

• 在Java中，char为无符号数，16位存储，表示范围是0～2^16-1（即0～65535）。

  1. 首先，我们按照0000 0000 0000 0000到1111 1111 1111 1111递增的方式，均匀的分布在时钟的表盘上，图就不画了，自己在脑中想象一下或者画个草稿。
  2. 然后，找出数据溢出点，通过观察char环形图可以发现数据溢出点是0（0000 0000 0000 0000）和65535（1111 1111 1111 1111）
  3. 最后，我们的ch = 65535 + 1，那么很显然发生了数据溢出，按照拨时针的方式就可以得出ch = 0

• Perfect，是否解答了当初学操作系统和编程的时候，困扰你们很久的问题。送给大家一句话：有些概念可能当时不理解，但是随着经验多累积和回顾的多了，自然而然就理解了。

贴出我看的关于补码的文章链接，有几篇中文文章对于某些知识点可能说错了，切记要带着批判的观点去看：

• 《深入理解计算机系统》第二章
• 《计算机教育》2015年第10期的文章——《原码、反码和补码的教学讨论》
• 补码原理的个人理解
• 为什么计算机用补码存储数据？
• 原码、反码和补码
• 补码
• Class #7 - Signed Binary Numbers, Subtraction and Overflow