二进制求补码算法 c语言,谈谈二进制（四）——原码、补码、反码、移码

╰+攻爆jí腚メ 2023-01-22 14:49 28阅读 0赞

0. 概要

老规矩，先回顾一下前面三篇文章我们都讲了什么。

首先，第一篇【谈谈二进制(一)】我们从进制本身的意义开始，认识了二进制和其他进制，然后完成了十进制和其他各种进制之间的转换。

接着，第二篇【谈谈二进制(二)——四则运算】中，我们则通过十进制的四则运算原理，推导出二进制的四则运算。

上一篇【谈谈二进制(三)——位运算及其应用】，我们将二进制从纯数学的世界中带到了计算机的世界里，并通过一个真实的算法题，了解了二进制位运算在实际编程中的使用。

今天这篇，我们来看看二进制在计算机中的特殊表示。

1. 有符号数和无符号数

在讲各种码之前，先来熟悉一下两个概念：有符号数和无符号数。这两个概念很好理解，就是字面的意思，一个数值是否有正负符号。

在上一篇文章中，按位取反的部分，我们在C++代码中用unsigned关键字定义了一个无符号数。无符号数的意思就是，这个数字存储在计算机中的时候是没有符号的，也就是正数；而有符号数则会把正负号也存入计算机中。但我们知道，计算机所有的数值都是由二进制组成的，那么正负号这种东西该怎么存储呢？

其实正和负这两个东西，就像布尔型的真和假一样，是两种截然相反的状态，因此正和负也可以使用0和1来表示，计算机里实际也是这么做的：0表示正，1表示负。并且正负号在原数有效数的最前面(左边)，所占的这一位被称为符号位。譬如+1001，它的实际存储值就是0,1001，-1001就是1,1001，符号位在逗号的左边。这里的逗号，实际上是一种为了书写方便以及区别整数小数的约定俗成的写法，即整数的数值与符号位之间用逗号隔开，而小数的符号位和数值位之间则以小数点隔开，譬如-0.1001，会写成1.1001。

这种把正负号给数字化后的数值，被称为机器数，带正负号的原数被叫做真值。

讲各种码之前，这里还要提一句，原码、补码、反码、移码这些码，都只是机器数的不同表示形式，就像前面我们讲过的进制，无论二进制还是十进制，对于同一个数值来讲，也只是不同的表示方法而已。

2. 原码

先来看原码，原码是众多码中最简单的一种机器数表示法，其实我们上面在说有符号位的符号的时候，就已经把原码的概念给讲完了，原码就是符号位和真值的绝对值组成的。它和真值之间仅仅是正负号被换成了0和1，然后根据整数或小数加上,，也就是上文中写到的那几个例子，这里简单罗列一下：

$$\[+1001\]\_\{原\}=0, 1001$$

$$\[-1001\]\_\{原\}=1, 1001$$

$$\[+0.1001\]\_\{原\}=0. 1001$$

$$\[-0.1001\]\_\{原\}=1. 1001$$

不过这里有几点我们要提一下，非常有意思。

第一个是整数负数的原码，上文中我们知道，就是把负号给换成1，然后写的时候加一个逗号，举个例子，-1001(-9)，原码表示为1, 1001。这里我们做一个大胆的试验：把逗号去掉，然后把剩余的11001看做一个完整的二进制正整数，也就是25，看看它跟-1001(-9)有什么联系。

从十进制上的数来看，乍看之下25和(-9)好像没什么联系，然后我们来看二进制11001和-1001，咦？似乎有点像，除了最高位的1和负号之外，余下的4位一模一样，我们把它俩相加：11001 + (-1001) = 10000。嘿，这就更有意思了，熟悉二进制运算的朋友们肯定一眼就看出来，10000实际上就是$2^4=16$。

我们是不是可以从这个试验中猜测一个结论：一个负整数的原码，等于2的n次方减去自己？没错，这是一个正确的结论。这里的关键是，n是多少？上面的试验中我们的n为4，这里的4，其实就是原数的位数。用数学表达式表达就是：当$0≥x>-2^n$(x为原数真值)时，则$\[x\]\_\{原\}=2^n-x$。

正整数就没啥好说的，直接在真值绝对值前面加个0,。

再来看看小数，因为小数的符号位和数值位用小数点隔开，因此当0 ≤ x < 1时，也就是正小数时，它的原码就等于它自己。负小数呢？譬如-0.1001，原码写成1. 1001，也很简单，就是1. 1001 = 1 - (-0.1001)。

原码就是这样，后面的这些数学运算规律其实不管也无所谓，因为原码本身实在是太简单易懂了。

3. 补码

补码就稍微复杂一点，它的基础原理涉及到了补数和模的概念，这里我参考了唐朔飞老师的《计算机组成原理》中的一些概念和例子来讲解。

3.1 补数和模

补数的概念初次接触会觉得陌生，但它实际上可能就存在于我们的日常生活中。譬如，某一时刻时钟的某个指针指向6，如果我们想让它指向3，我们可以让指针沿逆时针方向走3格，也可以让它沿顺时针方向能走9格，最终都会让这个指针指向3。假设顺时针方向为正，逆时针方向为负，则刚才的两个行为分别为：6 + (-3) = 3和6 + 9 = 15。

我们知道，虽然我们日常采用24小时制，但钟表上的刻度通常只有12个刻度，因此指针超过12时，就会回归1、2等等。因此上面我们得到的15，实际上是15 - 12 = 3，也就是我们一开始所要达到的指向3的目的地。所以这里15和3在时钟上指向的都是3，那么，在刚才的操作过程中，-3和+9对时钟而言，作用是一样的，都是让原本在6的指针，指向了3。

上面的例子里，在数学上，称时钟的12格刻度为模，写作mod 12，而称+9是-3以12为模的补数，记作

$$-3 ≡ +9 \\qquad(\\text\{mod\}\\ 12)$$

或者说，对于模12而言，-3和+9是互为补数的。同理有

$$-4 ≡ +8 \\qquad(\\text\{mod\}\\ 12)$$

$$-5 ≡ +7 \\qquad(\\text\{mod\}\\ 12)$$

即对于模12而言，+8和+7分别是-4和-5的补数。可见，只要确定一个模，就可以找到一个与负数等价的正数来代替该负数，而这个得到的正数，即为负数的补数，同时，我们观察到，该负数的绝对值，和它的补数相加，就是模(结论一)。

那么当我们有一个负数，且已知模时，如何求它对应的正数补数呢？很简单，只需要让负数和模相加(结论二)，譬如-4 + 12 = 8 (mod 12)，这个+8就是-4的补数了。

这就是模和补数的概念。这里大家可能会有疑问了：上面的几个式子和最后的结论，讲的都是负数的补数，那么正数有补数吗？

有的，但先别着急，我们先来看下，上面我们求得的负数的模到底有什么用。其实参考我们一开始讲的时钟的例子，我们隐隐约约可以感觉到，补数这个东西，可以让减法变成加法。依然来看一个例子，我们设A = 9, B = 5，求A - B(mod 12)。最通常的解法是减法：

$$A - B = 9 - 5 = 4$$

这么解肯定没问题，但我们题目中给出了mod 12，那么对模12而言，-5可以用它的补数+7代替，他们是恒等的，于是这题的另一个解法如下：

$$A - B = 9 + 7 = 16$$

这样我们得到了16，回想一下时钟，16这个数字是不存在的，当时钟拨到16时，其实是4，所以对于mod 12，16又等价于4，即4 ≡ 16(mod 12)。那么如果此时时钟再顺时针转一圈(12格)，到了28呢？它依然是4，即

$$4 ≡ 16 ≡ 28 \\qquad(\\text\{mod\}\\ 12)$$

$$4 ≡ 4 + 12 ≡ 4 + 2\\times12 ≡ 4 \\qquad(\\text\{mod\}\\ 12)$$

这也就是说，正数的补数，就是正数本身(结论三)。

前面讲进制时我们反复讲过一点，不同的进制之间仅仅是进位方式不同，所以上面我们虽然用的是十进制来介绍模，实际上二进制依然可以用模，结合模和补数的概念，以及上面的三个结论，我们可以得到如下二进制数的补数：

$$-1011 ≡ +0101 \\qquad(\\text\{mod\}\\ 2^4)$$

$$+0101 ≡ +0101 \\qquad(\\text\{mod\}\\ 2^4)$$

$$-0.1001 ≡ +1.0111 \\qquad(\\text\{mod\}\\ 2)$$

$$+0.1001 ≡ +0.1001 \\qquad(\\text\{mod\}\\ 2)$$

用上面粗体的三个结论，很容易就能求得各种数字的补数，这里几个二进制我就不再计算验证了，大家可以自己试一下。

有了补数的概念后，人们看到了它可以将减法变成加法，便将其概念用到了计算机中，于是出现了补码这种机器数。

3.2 补码的定义

补码和原码一样，需要用一位数字在高位作为符号位表正负，而低位的数值部分则采用了补数的概念，因此，结合上面补数的特征，我们可以想象到，因为正数的补数是它自己，因此在补码中，正数的数值位是它自己，符号位则同原码一样，正数为0，负数为1。譬如下面两个例子：

$$\[+1001\]\_\{补\}=0, 1001$$

$$\[+0.1001\]\_\{补\}=0. 1001$$

也就是说，正数的补码和原码一样。

负数就要麻烦一些。首先，通过上一小节我们知道，二进制的补数计算方式和十进制一样，譬如-1101，它的最高位为第3位，因此我们取比它高一位的最小值$2^4$作为模，求得它的补数为10000 + (-1101) = 0011。按理说，我们得到的负数的补数是正数，这里只需要再加一个符号位0即可，但注意了，补码中的实际情况并不是这样，尽管负数的补数为正数，但负数的补码前的符号位依然是负符号位1，即符号位与原数保持一致。

为什么会这样？明明求得的补数是正数，符号位却要用负符号1？

实际上，在前面讲补数的时候我们提到过，补数的出现，可以让原本作减法的式子变成加法，补码这种机器数也正是看准了这一点才被计算机引入的。对于计算机来说，让减法变成加法，相当于让计算机只需要在硬件层面上实现一个加法器，就可以解决加减法两种问题。那么这里补码的符号位的问题，自然也是为了计算而设定如此的，我们来看一个实际的例子就知道了。

设A = 1110，B = 1101，我们来求A - B的值。常规用减法，一眼可以看出来，结果是1110 - 1101 = 0001。我们将A和-B(-1101)两个数都换成补码，用加法计算，此时$A = 0,1110\\quad(mod\\ 2^4)$，$-B = 1,0011\\quad(mod\\ 2^4)$。注意了，在使用补码计算时，补码的符号位也参与计算，那么此时这两个补码相加后的结果为：

$$0,1110 + 1,0011 = 10,0001 \\qquad(\\text\{mod\}\\ 2^4)$$

我们看到，结果的符号位产生了进位，变成了10。这里其实涉及到了另一个知识点：补码运算的符号位进位(溢出)。由于篇幅关系，本文不对该知识点展开讲解，大家有兴趣的可以去查找资料了解一下。总之，这里符号位虽然进位了，但并没有发生溢出，我们把符号位的最高位1拿掉，得到了最终的结果0,0001，也就是+0001，与之前的减法结果一致。

这就是负数求补码后让符号位也保持负值1的原因了。上面讲的都是负正数，实际上负小数同理，这里不再赘述，我们直接上两个数学公式来对负数求补码进行一个总结。首先是整数，正整数就不说了，和原码一样，负整数呢？除了上面用标准的补数算法外，我们可以直接用下面这个公式来计算：

$$\[x\]\_\{补\}=2^\{n+1\}+x\\qquad0>x≥-2^n\\quad(\\text\{mod\}\\ 2^\{n+1\})$$

这里的n就是整数x的位数。拿前面我们算过的-1101举例：

$$\[-1101\]\_\{补\}=2^\{4+1\}+(-1101)=100000-1101=1,0011$$

最高位1就是符号位，与后面的数值位部分用逗号隔开，就得到了最终的结果。其实这里我们可以观察到一个规律：负整数的补码，就是原数字除符号位外，数值部分的每一位按位求反后再+1。

接着是负小数：

$$\[x\]\_\{补\}=2+x\\qquad0>x≥-1\\quad(\\text\{mod\}\\ 2)$$

看上去更简单了，举个例子，我们求-0.1001的补码：

$$\[-0.1001\]=2+(-0.1001)=10.0000 - 0.1001=1.1010$$

其实这里求负小数的补码的方式，和上一节中我们求小数的补数的方式是一样的。还记得上一节的结论二吗？求一个负数的补数，就是让负数和模相加。然后我们再仔细观察一下，会发现上面负整数的求补规律在负小数也奏效，即负数的补码，就是原数字除符号位外，数值部分的每一位按位求反后再+1，然后符号位该怎么写怎么写。记住这个结论，它能让我们在求补码的时候避免加减法运算，更加容易。

补码的概念基本就讲完了，想要掌握的话，其实还是需要自己拿笔算一算，写一写。

4. 反码

反码，这种机器数的主要场景用于原码和补码的相互转换，反码作为中间数过度使用。首先，正数的反码，老样子，依然和原码一样，符号位0和1表示正负，然后是数值位部分原封不动，这里直接拿前面原码里的两个正数例子：

$$\[+1001\]\_\{反\}=0, 1001$$

$$\[+0.1001\]\_\{反\}=0. 1001$$

有区别的依然是负数，但反码的负数就简单多了：除了符号位，数值位部分每一位都按位取反。因此：

$$\[-1001\]\_\{反\}=1, 0110$$

$$\[-0.1001\]\_\{反\}=1. 0110$$

非常简单对不对？那么为什么说反码是原码和补码之间相互转换的中间过渡呢？在上一节补码的最后，我们得到了一个求补码的简单规律：负数的补码，就是原数字除符号位外，数值部分的每一位按位求反后再+1，然后符号位该怎么写怎么写。其实这个过程，就是对原码先求反码再给末位+1。同理，如果我们知道了一个补码，想要求它的原码，只需要先将补码的末位-1后，再将数值位部分按位求反即可。

好了，明白了这一点后，我们来看一个上一篇文章中遗留的问题。

4.1 按位取反运算

在上一篇文章【谈谈二进制(三)——位运算及其应用】中的取反运算部分，我们对有符号数5进行取反，却得到了-6这个匪夷所思的答案，当时我在文章中说，这是因为计算机中存储数字的方式都是用补码存储，之所以会得到负值，则是由于补码的最高位表示符号位，按位取反时连符号位一起取反了。今天我们深入了解了补码和反码，也推出了补码和原码之间的转换方式，那么就用今天的知识，来彻底解决这个按位取反的问题吧。

首先，5的二进制为101，其补码为0,101。在进行按位取反操作，即~5时，实际上把符号位也取反了，于是我们得到了1,010这个结果，请注意，这个1,010依然是补码。而从符号位的1我们看到，这是一个负数补码，我们通过补码不能直观地看出它的真值，因此需要先转换成原码。按照前文我们提到的补码转原码的方式，先将1,010末位-1，得到1,001，接着，我们将数值位按位取反，符号位不动，得到1,110。此时，1,110已经是原码了，可以直接将其求出：

$$1,110=-110\_\{原\}=-6\_\{(10)\}$$

于是，我们得到了这个-6。

这个让我们之前摸不着头脑的答案，在我们学完了补码之后，变得清晰明了。

除了这个-6之外，按位取反的部分还有一个小问题，我们后来又使用了一个无符号数5来进行按位取反，发现得到了一个巨大的数字4294967290，并且这个数实际上是$2^\{32\}-6$：0000,0000,0000,0000,0000,0000,0000,0101 // 5

1111,1111,1111,1111,1111,1111,1111,1010 // 4294967290

这个问题其实可以有两种角度去理解，一种是最直观的：因为无符号数不涉及符号位的问题，而C语言中(这个数字是用C++求得的)unsigned int的取值范围在32位机器上为0 ~ 4294967295，没错，最大值就是上面的两个数之和$2^\{32\}-1$，也就是32个1。所以将5(101)左侧不存在的0都取反为1后，就得到了这么大的一个数字。

第二种角度就是来解释-6这个巧合了。我们只需要把$2^\{32\}$看做一个模，按照前面计算补数的运算方式，来求-6的补数，即让模和-6相加，就得到了4294967290这个数字，同时，4294967290是无符号数5按位求反的结果，它们相加的和，则是unsigned int的最大值(32位，$2^\{32\}-1$)，本身就比$2^\{32\}$小1，1 + 5 = 6，于是就很凑巧的变成了我们看到的规律。

5. 移码

补码对计算机来说是个好东西，毕竟它让计算机对于数字的计算变得更加方便了。但对人类来说，补码可就不那么友好了，不说和真值，哪怕和原码相比，补码也存在着一个巨大的缺点：数字本身的被补码隐藏，使得数字的大小不直观。举个例子：

$$+15\_\{补\}=\[+1111\]\_\{补\}=0,1111$$

$$-15\_\{补\}=\[-1111\]\_\{补\}=1,0001$$

如果我们把符号位的1也看作是整个二进制数的一部分，那么显然10001 > 01111。虽然在我们懂得了补码的原理和运算过程后，我们并不会直接这么去比较，但因为负数的补码将数值部分都给改写了，总体来说，补码依然给人以非常不直观的感受，一旦逗号忘记写，或者其他原因造成了误读，那么补码之间的比较将成为灾难。就上面的两个数来说，我们很难一眼就看出来这两个二进制数居然互为相反数，但如果是用原码表示，那么起码他们的数值位是相同的，我们能第一时间反应过来。

此时，如果我们将两个数字的真值都加上$2^n$，这里的n同前面我们讲过的那些n一样，是真值的位数，那么新得到的两个数字的大小就变得很直观了：

$$15 + 2^4 = 1111 + 10000 = 11111$$

$$-15 + 2^4 = 10000 - 1111 = 00001$$

尽管还是无法直接看出它俩的真值互为相反数，但我们可以很直观地比较出这两个数字的实际大小了，不会因为符号位的问题造成误读。而这两个计算后得到的新数字，就是移码。

所以移码的数学定义非常简单：

$$\[x\]\_\{移\}=2^n+x\\qquad(2^n>x≥-2^n)$$

这里的n就是真值的位数，x则是真值。

我们仔细观察上面两个数字的补码和移码，会发现一个有趣的现象：移码实际上就是改变了补码的符号位，从0变1，从1变0。这样一来，当我们知道了一个数的补码后，只需要替换它的符号位，就可以得到移码，从而与其他数值进行直接比较了。

6. 总结

今天我们了解了二进制数的四种机器数表示方式，并且解决了上一篇文章中遗留的小问题。在下一篇文章里，我们将认识定点数和浮点数，对，就是我们编程中非常熟悉的那个浮点数float。