【译文】补码表示--理论和示例

补码表示是数值计算中的一个基本技术，它使得减法操作可以用加法操作来替换。

这篇文章首先用几个例子来回顾补码表示的理论。然后，我们将简单地讨论加法器/减法器的框图。

补码表示是数字计算机表示有符号整数的一种方式。补码表示的主要目的是用加法操作来代替减法操作。通过这种方式，我们可以用同样的电路来处理加法和减法。因此，可以减少门电路的数目，从而减少整个电路系统的大小，能耗。事实上，如果不使用补码表示，我们只能用一种类似平时手算十进制数的方式，这需要两种不同的门电路块来计算加法和减法。此外，在计算之前，还需要一些执行逻辑判断。

知识背景：无符号数的计算

假设我们有一个加法器，输入是两个4比特无符号数，a=a3a2a1a0 和 b=b3b2b1b0，还有一个进位输入信号cin，然后计算它们的和 a+b+cin。要怎么用这个加法器来实现减法操作呢？比如，S = a - b? 在S上减去一个常数M,再减去M, S的结果不变：

$等式1: S=a+M−b−M$

当M足够大时，可得：
$等式2: B=M−b>0$

所以等式1可以写成：
$等式3: S=a+B-M$

等式3需要一个加法操作和一个减法操作。另外，为了计算B，还需要一个减法操作。看上去把运算变得更加复杂了，因为 $S=a-b$ 只需要一个减法操作，而等式3需要一个加法操作，两个减法操作。但是，等式3计算需要的两个减法都是减去同样的常数M, 我们是否能找到一个合适的M，来简化等式2和等式3中的减法操作。如果可以，就能用等式3达到用加法实现减法的目的。所以问题变成：常数M的合适值是多少？在后文会被证明，对于k比特的数， $M=2^k$

假设一个4比特无符号数b, 测试减法 $M-b$ .
$k=4$ ,所以 $M=2^4=16_{(10)}=10000_{(2)}$ 。
为了简化运算，可以把M写成 $M=(M-1)+1$ ,代入等式2：
$B=10000_{(2)}-b=(01111_{(2)}-b)+00001_{(2)}$
可以很简单地计算 $01111_{(2)}-b$ ,因为事实上是对b按位取反。假设 $b=0011_{(2)}$ ,则
$B=(01111_{(2)}-0011_{(2)})+00001_{(2)}=01100_{(2)}+00001_{(2)}$
可以看出，括号里的减法其实是b按位求补。因此，要算 $M-b$ ,只需要对b按位求补再加上 $00001_{(2)}$ . 在后文会提到，从实现的角度，对一个数的按位求补加上 $00001_{(2)}$ 是很简单的

得到B之后，可以用加法器计算等式3中的a+B。为了得到最后的结果，还需要把a+B的结果减去M。在上面的例子中，我们考虑的是4比特的无符号数，因此，S能取得最大值时，应该是 $a=1111_{(2)}$ 和 $b=0000_{(2)}$ ,得到 $S=1111_{(2)}=15_{(10)}$ . 所以4比特是足够表示4比特减法的。选择 $M=16_{(10)}=10000_{(2)}$ ，加上M或者减去M,只能影响第5位比特的值。所以， $a-b+M=a+(M-b)=a+B$ ,第5位比特值改变第一次。接着， $a+B-M$ ,第5位比特值改变第二次。因为是二进制，则第5位比特值没有改变，所以当计算 $a+B-M$ 时，只需要丢弃 $a+B$ 的第5位比特值即可。事实上，这等价于对 $a+B$ 作模M运算，限制 $a+B$ 的值小于等于M-1

上述讨论总结为：如果a和b是两个k比特的无符号数，则a-b等价于计算a加上M-b，然后丢弃第k+1位比特值。在这里M等于 $2^k$

在模M运算中，M-b被称为b的补码(two's complement). 一个数的补码可以通过对这个数按位求补再加1得到。

例子1

a,b均为无符号4比特数，用补码表示计算a-b， $a=1011_{(2)}=11_{(10)}$ , $b=0110_{(2)}=6_{(10)}$

因为是4比特数，所以 $M=2^4$ 。根据上述理论，先求
$B=M-b=(M-1)-b+1=01111_{(2)}-0110_{(2)}+00001_{(2)}=01001_{(2)}+00001_{(2)}=01010_{(2)}$
再把a加上B,
$a+B=1011_{(2)}+01010_{(2)}=10101_{(2)}$
再丢弃第5位比特值，得到
$a-b=0101_{(2)}=5_{(10)}$

例子2

a,b均为无符号5比特数，用补码表示计算a-b， $a=10111_{(2)}=23_{(10)}$ , $b=01001_{(2)}=9_{(10)}$

因为是5比特数，所以 $M=2^5$ 。根据上述理论，用M-b表示-b，先求
$B=M-b=(M-1)-b+1=011111_{(2)}-01001_{(2)}+000001_{(2)}=010110_{(2)}+000001_{(2)}=0100111_{(2)}$
再把a加上B,
$a+B=10111_{(2)}+0101111_{(2)}=101110_{(2)}$
再丢弃第6位比特值，得到
$a-b=01110_{(2)}=14_{(10)}$

怎么表示有符号整数呢？

将b和M-b相加得到M，而M在模为M的运算中等于0；这也是为什么在模为M的运算中，M-b可以看做是b的补码。在表格1的第二列给出了所有3个比特位的可能组合。相对应的十进制数值放在第一列。假设 $M=2^3$ ,对应的补码放在第三列。可以发现，在模为M的运算中，第二列加第三列的值等于0. 表格展示出，一个3比特位的数值可以有两种不同的解释。比如，010可以是解析成正十进制数2，或者负十进制数-6.为了区分这两种情况，我们在最左边增加一个额外的符号位，用来区分数值是正数还是负数。

kk_image222.png

当符号位为0，表示该数为正数。在此示例中，剩下的3个比特位根据上表的第一列给出对应的十进制的大小。比如， $0010_{(2)}$ ,表示+2. 当符号位1，表示该数为负数，必须要使用上表的第三列来解析。比如， $1010_{(2)}$ 应解析成-6. 事实上，我们使用4比特位来表示一个有符号的大小为3比特位的数。

现在让我们加上符号位，并实验所有可能的组合。图一展示了4比特位数值的所有可能的组合。如果设定这些数为无符号数，则我们得到圆圈外面的数值。如，无符号数 $1010_{(2)}$ 等于十进制数10. 如果设定这些数为有符号数，则我们得到圆圈里面的数值。如，无符号数 $1101_{(2)}$ 等于十进制数-3.

128.png

从图1可以看出，补码常数M 为 $2^4=16$ 。比如，一个负数-5，表示为 $11=16-5$ . 所有的负数的符号位都为1，当我们处理有符号数时，这个有助于我们在系统里判断负数。
图1也展示了有符号数和无符号数的数值表示范围。用无符号数表示，4比特位可以表示 $0$ ~ $15$ 的数值范围。用有符号数表示，4比特位可以表示 $-8$ ~ $+7$ 的数值范围. 需要注意有符号补码表示的范围的非对称性。该特性可能会导致数值溢出，程序员需要谨慎地处理去避免这种情况发生。
小节总结：当我们假设一个有符号的补码表示，首先要关注符号位。如果符号位为0，可以像无符号数一样处理得到十进制数值。如果符号位为1，相关的十进制数值是该补码表示的补码。如 $1101_{(2)}$ ， $101_{(2)}$ 按位求补得 $010_{(2)}$ ，再加1，得 $011_{(2)}$ 即3. 所以 $1101_{(2)}$ 表示-3。

例子3

假设有一个有符号的补码表示，找到 $a=01110_{(2)}$ 和 $b=10110_{(2)}$ 对应的十进制数值。

因为a的符号位为0，是正数，所以 $a=2^3+2^2+2^1=14$
因为b的符号位为1，是负数，所以 $b=-(b的补码)=-(01001_{(2)} + 00001_{(2)})=-(01010_{(2)})=-10$

现在，我们熟悉了有符号的补码表示，可以更简单地实现加法和减法。

例子4

假设有一个有符号5比特位的补码表示，有 $a=01001_{(2)}=9_{(10)}$ 和 $b=00101_{(2)}=5_{(10)}$ ，计算a-b。

为了计算a-b，需要找到-b，去加上a.
$-b=b的补码=11010_{(2)} + 00001_{(2)}=11011_{(2)}$
遂，
$a+(-b)=01001_{(2)} + 11011_{(2)}= 100100_{(2)}$ ,
由于是5比特位的运算，所以丢弃第6位，得到 $a-b=00100_{(2)}=4_{(10)}$

例子5

假设有一个有符号5比特位的补码表示，有 $a=10111_{(2)}=-9_{(10)}$ 和 $b=00110_{(2)}=6_{(10)}$ ，计算a-b。

为了计算a-b，需要找到-b，去加上a.
$-b=b的补码=11001_{(2)} + 00001_{(2)}=11010_{(2)}$
遂，
$a+(-b)=10111_{(2)} + 11010_{(2)}= 110001_{(2)}$ ,
由于是5比特位的运算，所以丢弃第6位，得到 $a-b=10001_{(2)}$
将结果转换为十进制，
$a-b=10001_{(2)} =-(01111_{(2)}) =-15_ {(10)}$

在上述两个例子中，我们丢弃了第6比特位的数值，但结果是正确的，因为补码表示是基于模M运算的。

例子6

假设有一个有符号5比特位的补码表示，有 $a=10111_{(2)}=-9_{(10)}$ 和 $b=01001_{(2)}=9_{(10)}$ ，计算a-b。

为了计算a-b，需要找到-b，去加上a.
$-b=b的补码=10110_{(2)} + 00001_{(2)}=10111_{(2)}$
遂，
$a+(-b)=10111_{(2)} + 10111_{(2)}= 101110_{(2)}$ ,
由于是5比特位的运算，所以丢弃第6位，得到 $a-b=01110_{(2)}=14_ {(10)}$
然而，实际上 $a-b=(-9_ {(10)}) -9_ {(10)} = -18_ {(10)}$ . 这是因为5比特位最大能表示的正数是 $01111_{(2)}=15_ {(10)}$ . 这个例子说明我们总是需要检查计算的结果去保证没有数值上溢发生，从而保证计算结果是正确的。数值上溢发生在，两个正数相加导致结果为负数，还有两个负数相加导致结果为正数。由于补码的性质，一个正数和一个负数相加不会引起数值上溢。

简单加/减法器的框图

就像本文开头所说，补码表示就是为了在同一个电路模块上执行加法和减法。如下图所示，输入为二进制数a和b，还有输入进位 $c_{in}$ , 输出为a+b+ $c_{in}$ .

当标志位sub/add为0， Selective complement不执行， y=b， $c_{in}=0$ ，因此结果为a+b+ $c_{in}=x+y$ 。
当标志位sub/add为1， Selective complement执行，对b按位取补， $y=y^{compl}$ ， $c_{in}=1$ ，结果为 $a+b+c_{in}=x+(y^{compl}+1)$ 。按上文所说 $(y^{compl}+1)$ 等于y的补码。所以加法器的最后输出的其实是x-y

555.png

总结

1. 如果a和b是两个k比特的无符号数，则a-b等价于计算a加上M-b，然后丢弃第k+1位比特值。在这里M等于 $2^k$

2. 在模M运算中，M-b被称为b的补码(two's complement).

3. 一个数的补码可以通过对这个数按位求补再加1得到。

4.当我们假设一个有符号的补码表示，首先要关注符号位。如果符号位为0，可以像无符号数一样处理得到十进制数值。如果符号位为1，相关的十进制数值是该补码表示的补码。

5.我们总是需要检查计算的结果去保证没有数值上溢发生，从而保证计算结果是正确的。数值上溢发生在，两个正数相加导致结果为负数，还有两个负数相加导致结果为正数。

最后编辑于：2022.06.09 15:35:07

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 213,864评论 6赞 494
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,175评论 3赞 387
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 159,401评论 0赞 349
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,170评论 1赞 286
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,276评论 6赞 385
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,364评论 1赞 292
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,401评论 3赞 412
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,179评论 0赞 269
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,604评论 1赞 306
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,902评论 2赞 328
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,070评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,751评论 4赞 337
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,380评论 3赞 319
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,077评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,312评论 1赞 267
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,924评论 2赞 365
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,957评论 2赞 351

【译文】补码表示--理论和示例

这篇文章首先用几个例子来回顾补码表示的理论。然后，我们将简单地讨论加法器/减法器的框图。

知识背景：无符号数的计算

例子1

a,b均为无符号4比特数，用补码表示计算a-b，,

例子2

a,b均为无符号5比特数，用补码表示计算a-b，,

怎么表示有符号整数呢？

例子3

假设有一个有符号的补码表示，找到和对应的十进制数值。

例子4

假设有一个有符号5比特位的补码表示，有和，计算a-b。

例子5

假设有一个有符号5比特位的补码表示，有和，计算a-b。

例子6

假设有一个有符号5比特位的补码表示，有和，计算a-b。

简单加/减法器的框图

就像本文开头所说，补码表示就是为了在同一个电路模块上执行加法和减法。如下图所示，输入为二进制数a和b，还有输入进位, 输出为a+b+.

总结

1. 如果a和b是两个k比特的无符号数，则a-b等价于计算a加上M-b，然后丢弃第k+1位比特值。在这里M等于

2. 在模M运算中，M-b被称为b的补码(two's complement).

3. 一个数的补码可以通过对这个数按位求补再加1得到。

4.当我们假设一个有符号的补码表示，首先要关注符号位。 如果符号位为0，可以像无符号数一样处理得到十进制数值。如果符号位为1， 相关的十进制数值是该补码表示的补码。

5.我们总是需要检查计算的结果去保证没有数值上溢发生，从而保证计算结果是正确的。数值上溢发生在，两个正数相加导致结果为负数，还有两个负数相加导致结果为正数。

推荐阅读更多精彩内容

a,b均为无符号4比特数，用补码表示计算a-b， $a=1011_{(2)}=11_{(10)}$ , $b=0110_{(2)}=6_{(10)}$

a,b均为无符号5比特数，用补码表示计算a-b， $a=10111_{(2)}=23_{(10)}$ , $b=01001_{(2)}=9_{(10)}$

假设有一个有符号的补码表示，找到 $a=01110_{(2)}$ 和 $b=10110_{(2)}$ 对应的十进制数值。

假设有一个有符号5比特位的补码表示，有 $a=01001_{(2)}=9_{(10)}$ 和 $b=00101_{(2)}=5_{(10)}$ ，计算a-b。

假设有一个有符号5比特位的补码表示，有 $a=10111_{(2)}=-9_{(10)}$ 和 $b=00110_{(2)}=6_{(10)}$ ，计算a-b。

假设有一个有符号5比特位的补码表示，有 $a=10111_{(2)}=-9_{(10)}$ 和 $b=01001_{(2)}=9_{(10)}$ ，计算a-b。

就像本文开头所说，补码表示就是为了在同一个电路模块上执行加法和减法。如下图所示，输入为二进制数a和b，还有输入进位 $c_{in}$ , 输出为a+b+ $c_{in}$ .

1. 如果a和b是两个k比特的无符号数，则a-b等价于计算a加上M-b，然后丢弃第k+1位比特值。在这里M等于 $2^k$

4.当我们假设一个有符号的补码表示，首先要关注符号位。如果符号位为0，可以像无符号数一样处理得到十进制数值。如果符号位为1，相关的十进制数值是该补码表示的补码。