“二进制补码”是什么?

505

我正在参加一门计算机系统课程,其中一部分内容让我感到困难的是二进制补码。我想理解它,但是我读过的所有资料都没有给我一个清晰的结构图。我阅读了维基百科文章和其他各种文章,包括我的教科书

什么是二进制补码,我们如何使用它,以及它如何在操作(如从有符号到无符号的强制转换,位运算和位移操作)中影响数字?


1
我认为对我有帮助的评论是,补码类似于反码,但不是给出 0 而是给出 2^N(根据定义),例如对于数字 A 的 3 位,我们想要 A+~A=2^N 所以 010 + 110 = 1000 = 8,这是 2^3。至少这解释了在这里“补码”一词的含义,它不仅仅是将 01 的含义取反。MIT 有用的视频:https://www.youtube.com/watch?v=RbJV-g9Lob8 - Charlie Parker
一个快速的记忆法和澄清混淆的方法:就像符号幅度表示法一样,二进制补码表示法也有一个“符号位”。因此,要找到二进制补码表示法的有符号(负数、零或正数)数字的值,只需计算符号位,即最高有效位为负,然后其余位将按照通常的方式计算(作为无符号编码中的正数)。感谢布赖恩特先生和奥哈洛伦先生撰写了令人惊叹的书籍《计算机系统:程序员的视角》(注:这本书远不止这个简单的示例)。 - aderchox
24个回答

718

二进制补码是一种聪明的整数存储方法,使得常见的数学问题非常容易实现。

要理解这个概念,你必须把数字想象成二进制

它基本上是这样说的:

  • 对于零,使用所有的0。
  • 对于正整数,从0开始计数,最大值为2(位数-1)-1。
  • 对于负整数,做完全相同的事情,但是将0和1的作用互换并向下计数(因此,不是以0000开始,而是以1111开始 - 这就是"补码"的部分)。

让我们用四位的迷你字节(我们称之为半字节- 1/2个字节)来尝试一下。

  • 0000 - 零
  • 0001 - 一
  • 0010 - 二
  • 0011 - 三
  • 01000111 - 四到七

这就是我们在正数方面所能达到的极限了。23-1 = 7。

对于负数:

  • 1111 - 负一
  • 1110 - 负二
  • 1101 - 负三
  • 11001000 - 负四到负八

请注意,负数比正数多一个值(1000 = -8),因为0000用于表示零。这可以被视为计算机的Number Line

区分正负数

为了区分非负和负的十进制值,第一位扮演"符号"位的角色。如果最高位是1,则可以说该二进制数是负数,而如果最高位(最左边)是0,则可以说该十进制值是非负数。

"Sign-magnitude"负数只需将其正数相对应的符号位取反,但这种方法必须处理将1000(一个1后跟所有0)解释为“负零”的情况,这很令人困惑。

"Ones' complement" 负数只是其正数对应位的补码,这也导致了一个令人困惑的“负零”,即 1111(全为1)。

除非您非常接近硬件工作,否则您很可能不需要处理 Ones' Complement 或 Sign-Magnitude 整数表示法。


183
二进制补码的最大好处在于它简化了数学计算。试着将2(0010)和-2(1110)相加,你得到了10000。最高位是溢出位,所以实际结果是0000。就像魔术一样,2 + -2 = 0。 - Naaff
110
除了容易进行加减运算之外,2 的补码的另一个优点是它只有一个零。如果使用简单的符号位表示法,例如使用 0001 表示 +1 和 1001 表示 -1,那么你将会有两个零:0000("+0")和 1000("-0")。这是非常麻烦的。 - Jörg W Mittag
30
感谢您的评论,您点赞的原因是因为这篇文章简明扼要并解释了为什么负数值的范围比正数值大。我来到这里就是想找出这个范围差异的原因。 - Ashwin
2
你不应该说“对于负整数,做完全相同的事情,但是倒计数并交换0和1的角色”。 - Koray Tugay
1
符号位仍然有效(除了0的情况,因为它既不是正数也不是负数),但你不能简单地改变符号位来取反一个数字(有关取反,请参见下面的链接)。 - NH.
显示剩余12条评论

383

我想知道这个问题是否可以比维基百科文章更好地解释。

用二进制补码表示法解决的基本问题是如何存储负整数。

首先,考虑一个用4位存储的无符号整数,你可以有以下内容:

0000 = 0
0001 = 1
0010 = 2
...
1111 = 15

这些是无符号的,因为它们没有指示它们是正数还是负数。

补码和移码符号

为了存储负数,你可以尝试多种方式。首先,可以使用补码符号,将第一位作为符号位分配给表示+/-,其余位表示幅度。所以再次使用4位,假设1表示-,0表示+,那么你就有:

0000 = +0
0001 = +1
0010 = +2
...
1000 = -0
1001 = -1
1111 = -7

所以,你看到问题了吗?我们有正零和负零。更大的问题是使用二进制数进行加减运算。使用符号位表示法进行加减的电路将非常复杂。

什么是

0010
1001 +
----

另一个系统是过量符号表示法。你可以存储负数,摆脱两个零的问题,但加法和减法仍然很困难。

于是出现了二进制补码。现在你可以存储正数和负数,并且可以相对容易地执行算术运算。有许多方法将一个数字转换为二进制补码。这里是其中一种方法。

将十进制转换为二进制补码

  1. 将数字转换为二进制(暂时忽略符号) 例如,5是0101,-5是0101。

  2. 如果这个数字是一个正数,那么你就完成了。 例如,5在二进制中使用二进制补码表示为0101。

  3. 如果这个数字是负数,则

    3.1 找到补码(反转0和1) 例如,-5是0101,因此找到补码为1010

    3.2 将补码加1 1010 + 1 = 1011。 因此,-5的二进制补码为1011。

那么,如果你想在二进制中做2 +(-3)怎么办? 2 +(-3)等于-1。 如果使用符号大小来添加这些数字,你需要做什么? 0010 + 1101 =?

使用二进制补码考虑一下会有多容易。

 2  =  0010
 -3 =  1101 +
 -------------
 -1 =  1111

将二进制补码转换为十进制

将1111转换为十进制:

  1. 该数字以1开头,因此是负数,所以我们找到1111的补码,即0000。

  2. 将0000加1,得到0001。

  3. 将0001转换为十进制,得到1。

  4. 应用符号 = -1。

Tada!


54
我个人认为这是最佳答案。 - Koray Tugay
7
好的,这个很简单,解释得非常清楚。 - Max Koretskyi
5
我不明白为什么在双向转换时加一总会得到相同的数字。在我看来,你会颠倒步骤或减去一些东西。 - Marcos Pereira
4
为什么要对补码加1? - RomanKousta
5
这个回答应该用于维基百科。 - Hiroki
显示剩余2条评论

136

就像我看到的大多数解释一样,上面的解释明确介绍了如何使用二进制补码操作,但并没有真正解释它们在数学上是什么。至少对于整数,我将尝试解释一下,并首先介绍一些可能熟悉的背景知识。

回忆一下十进制如何运作:
  2345
是一种写法,
  2 × 103 + 3 × 102 + 4 × 101 + 5 × 100.

同样地,二进制是一种只使用01来表示数字的方式,遵循相同的基本思想,但用2替换上述的10。然后在二进制中,
  1111
是一种写法,
  1 × 23 + 1 × 22 + 1 × 21 + 1 × 20
如果你计算出来,结果是15(十进制)。这是因为它是
  8+4+2+1 = 15。

对于正数来说,这都很好。如果你愿意,在负数上也可以这样做,就像人们在十进制数字中一样在前面加一个减号。这甚至可以在计算机中做到,但自从1970年代初就没有看到这样的计算机了。我将把原因留给另一个讨论。

对于计算机而言,使用补码来表示负数更有效率。但是有些事情经常被忽略,补码符号涉及到数字的位数颠倒,甚至包括正数前面的隐含零位。这很麻烦,因为问题出现了:所有的数字都要颠倒吗?那可能就是一个无穷大的数字。

幸运的是,计算机并不表示无穷大的数字。数字受到特定长度(或宽度,如果您喜欢)的限制。所以让我们回到正的二进制数字,但是规定一定的位数。这里我会用8位("bits")作为例子。因此,我们的二进制数字实际上应该是
  00001111
或者
  0 × 27 + 0 × 26 + 0 × 25 + 0 × 24 + 1 × 23 + 1 × 22 + 1 × 21 + 1 × 20

为了形成2的补码负数,我们首先要将所有(二进制)数字补码为
  11110000
然后加1变为
  11110001
但是这又该如何理解为-15呢?

答案是我们改变高位比特(最左侧的比特)的含义。所有负数的这一位都将是 1 。更改的方法是更改其对所出现数字值的贡献的符号。因此,我们的 11110001 现在被理解为:
  - 1 × 27 + 1 × 26 + 1 × 25 + 1 × 24 + 0 × 23 + 0 × 22 + 0 × 21 + 1 × 20
注意那个表达式前面的 "-"?它表示符号位承载的权重为-27,即-128(十进制)。所有其他位置保留了它们在无符号二进制数中的权重。
计算出我们的-15,得到:
  -128 + 64 + 32 + 16 + 1
在计算器上试试,结果是-15。
在我看到过的三种表示负数的主要方式中,二进制补码在一般使用中最为方便。但它有一个奇点。因为它是二进制的,所以可能的比特组合必须是偶数个。每个正数都可以与其负数配对,但只有一个零。否定零会得到零。因此还有一种组合,符号位为 1 ,其他所有位置上都是 0 。 相应的正数不适合使用正在使用的比特数。

这个数字更奇怪的地方在于,如果你尝试通过取反加一来形成它的正数,你会得到同样的负数。虽然零似乎也会有这种行为,但这是出乎意料的,而且与我们通常认为的不同,因为除了计算机之外,我们通常认为数字具有无限长度,而不是固定长度的算术。

这就像奇异性的冰山一角。在表面下还有更多等待我们去发现,但对于本次讨论,以上内容已经足够了。如果您想了解更多信息,可以搜索“固定点算术溢出(overflow)”。如果您真的想深入了解,您还可以研究“模运算(modular arithmetic)”。


3
我喜欢这个答案!它解释了如何进行二进制补码和加一的操作。 - jonsno
我也喜欢这个答案,特别是你展示了如何计算负数的部分。我之前认为整个数字都被倒置了,而不仅仅是最高位,然后再加回其他加权值。谢谢,这解决了我的思维障碍。 - user188757
做得好,提到了没有逆元的奇怪数字。但是我们该怎么办呢?如果有人试图反转它,我们只需设置溢出标志吗? - NH.
2
虽然其他答案关注于“如何”,但这个答案通过“为什么”温柔地引导我们。它对我很有帮助。谢谢! - Abhishek Pathak
如果一个数字以11000...000结尾,反转它将得到01000...000。二进制补码表示法的基本思想是,左边所有位于最左边的表示位之左的数字都应该与那个数字相同,但是当反转一个表示为1000...000的数字时,这个规则不再适用。 - supercat

24

2的补码对于查找二进制值非常有用,但我想到了一种更简洁的解决方法(从未见过其他人发表):

以二进制为例,例如:1101,它等于-3(假设空格“1”是符号)。

使用2的补码,我们会这样做...翻转1101,得到0010...加上0001 + 0010 ===> 得出0011。正二进制中的0011 = 3。因此,1101 = -3

我意识到的:

不必进行翻转和相加,只需按照求解正二进制的基本方法(比如0101)进行即可,即 (23 * 0) + (22 * 1) + (21 * 0) + (20 * 1) = 5。

使用同样的概念来处理负数!(稍作变化)

以1101为例:

对于第一个数字,不要使用 23 * 1 = 8,而是使用 -(23 * 1) = -8

然后像往常一样继续计算,即 -8 + (22 * 1) + (21 * 0) + (20 * 1) = -3


1
我能理解二进制补码的最佳方法。阅读这篇文章后,我能够理解上述问题的所有答案。 - SSC
3
这个方法在书《计算机系统:程序员的视角》中提到了。 - jimo
1
这是一个更快的方式! - chanzerre

16

假设你有一定数量的比特位/三进制位/数字等。你将所有数字都定义为0,并按自然数顺序逐个递增:

00
01
02
..

终究你会溢出。

98
99
00
我们有两个数字,可以表示0到100的所有数。所有这些数都是正数!假设我们也想表示负数?
实际上我们拥有的是一个循环结构。2之前的数字是1,1之前的数字是0,0之前的数字是......99。
因此,为了简单起见,我们可以说超过50的任何数字都是负数。 "0"到"49"表示0到49。"99"是-1,"98"是-2,..."50"是-50。
这种表示法是“十进制补码”。计算机通常使用“二进制补码”,它与十进制补码相同,只是使用位而不是数字。
十进制补码的好处在于加法“只是有效的”。您不需要对正数和负数进行特殊处理!

15

我在Reddit上读到了jng的一个精彩解释(链接),他使用里程表作为类比。

enter image description here


这是一个有用的约定。如果使用此约定,相同的电路和逻辑操作仍然适用于二进制中正数的加法/减法,并且也可用于正数和负数,这就是它如此有用和无处不在的原因。
想象一下汽车的里程表,它在(假设)99999上滚动。如果你增加00000,你会得到00001。如果你减少00000,你会得到99999(由于回绕)。如果你再加上一个1,它就会回到00000。所以决定99999表示-1非常有用。同样地,决定99998表示-2也非常有用,等等。你必须停止某个地方,而且按照惯例,数字的上半部分被认为是负数(50000-99999),而下半部分则仅代表它们自己(00000-49999)。因此,最高位为5-9意味着所代表的数字为负数,而为0-4则意味着所代表的数字为正数 - 这与二进制补码中的符号位完全相同。
我也很难理解这个。一旦我理解了它并重新阅读了书籍、文章和解释(那时还没有互联网),结果发现很多描述它的人并不真正理解它。之后我写了一本教汇编语言的书(在接下来的10年里相当畅销)。

哇,我好久没见过既有英里又有公里的速度表了。在我10岁之前,澳大利亚就已经改用公制单位了,但我仍然记得当我父亲试图在限速100公里/小时的区域以100英里/小时的速度行驶时,我不得不提醒他基本的转换规则 :-) - paxdiablo
无论如何,我认为他们在某个时候停止了允许odo回滚。将其从汽车上断开并使用电钻将其回滚是一些相当不正当的人在尝试以更低的里程数出售他们的汽车时经常使用的技巧(有趣的是我们仍然使用该术语,猜测公里数从未流行过)。 - paxdiablo

5

补码是通过对给定数字的1'st补码加1来找到的。 假设我们需要找到10101的补码,然后找到它的1'st补码,也就是01010,将这个结果加上1,即01010+1=01011,这就是最终答案。


4
让我们使用8位二进制形式得到10-12的答案: 实际上,我们要做的是10+(-12)。
我们需要获取12的补数以将其从10中减去。 12的二进制为00001100。 10的二进制为00001010。
要获取12的补数,我们只需反转所有位,然后加1。 12的二进制反转为11110011。这也是反码(一的补码)。 现在我们需要加1,即11110100。
因此,11110100是12的补数!当您以这种方式考虑时,很容易理解。
现在您可以解决上述问题10-12的二进制形式。
00001010
11110100
-----------------
11111110  

3

“补码”一词来源于“完整性”。在十进制中,数字0到9提供了一组补码(完整集)用于表示所有的十进制数。在二进制中,数字0和1提供了一组补码用于表示所有二进制数。实际上,符号0和1必须用来表示所有东西(文本、图像等),以及正数(0)和负数(1)。

在我们的世界中,数字左侧的空格被视为零:

                  35=035=000000035.

在计算机存储位置中,不存在空白空间。所有位(二进制数字)必须是0或1。为了高效使用内存,数字可以表示为8位、16位、32位、64位、128位。将存储为8位数字的数字转移到16位位置时,其符号和幅值(绝对值)必须保持不变。两种补码表示都可以实现这一点。
作为名词: 1的补码和2的补码都是有符号数量的二进制表示法,其中最高位(左侧的位)是符号位。0代表正数,1代表负数。 2的补码并不意味着负数,它表示一个带符号的量。就像十进制中一样,大小表示为正数量。该结构使用符号扩展来在提升到具有更多位的寄存器[]时保留数量:
       [0101]=[00101]=[00000000000101]=5 (base 10)
       [1011]=[11011]=[11111111111011]=-5(base 10)

作为一个动词: 2的补码意味着 取反。它不意味着变成负数。 它的意思是如果是负数则变成正数; 如果是正数则变成负数。大小是绝对值:
        if a >= 0 then |a| = a
        if a < 0 then |a| = -a = 2scomplement of a

这种能力允许使用否定然后加法进行高效的二进制减法运算。 a - b = a + (-b)
取1的补码的官方方法是对于每个数字将其从1中减去。
        1'scomp(0101) = 1010.

这与翻转或反转每个位是相同的。这导致了一个不被喜欢的负零,因此将1的补码加1可以解决该问题。要取反或获取2的补码,首先取1的补码,然后加上1。

        Example 1                             Example 2
         0101  --original number              1101
         1's comp  1010                       0010
         add 1     0001                       0001
         2's comp  1011  --negated number     0011

在这些示例中,否定符号扩展数字也同样起作用。
加法: 1110 进位 111110 进位 0110 相当于 000110 1111 111111 总和 0101 总和 000101
减法:
    1110  Carry                      00000   Carry
     0110          is the same as     00110
    -0111                            +11001
  ----------                        ----------
sum  0101                       sum   11111

请注意,使用二进制补码时,数字左侧的空格用于填充正数的零,但用于填充负数的是一。进位始终被加上,必须为1或0。
祝好!

3
从数学角度来看,二进制补码系统确实很有道理。在十进制的补码系统中,其思想本质上是“隔离”差异。
例如:63 - 24 = x
我们加上24的补码,实际上就是(100-24)。所以,我们只是在等式两边都加上了100。
现在的等式是:100 + 63 - 24 = x + 100,这就是为什么我们要去掉100(或10或1000或其他)。
由于需要从一长串零中减去一个数字,这种情况非常不方便,因此我们使用了“减位基补码”系统,在十进制系统中是九的补码。
当我们被给出一个从许多9中减去的数字时,我们只需要反转这些数字。
例如:99999 - 03275 = 96724
这就是为什么在九的补码之后,我们要加1的原因。你可能从小学数学中知道,通过“偷取”1,9变成了10。因此,基本上就是十的补码从差异中减去1。
在二进制中,二的补码相当于十的补码,而一的补码相当于九的补码。主要区别在于,我们试图用2的幂来隔离差异,而不是使用10的幂(将10、100等加入等式)。
正是因为这个原因,我们倒置了比特。就像在十进制中我们的被减数是一串9一样,在二进制中,我们的被减数是一串1。
例如:111111 - 101001 = 010110
因为一串1比2的幂小1,所以它们从差异中“偷取”1,就像十进制中的九一样。
当我们使用负二进制数时,我们实际上是在说:
0000 - 0101 = x
1111 - 0101 = 1010
1111 + 0000 - 0101 = x + 1111
为了“隔离”x,我们需要加1,因为1111距离10000只有1,我们去掉前导的1,因为我们刚刚把它加到了原始差异中。
1111 + 1 + 0000 - 0101 = x + 1111 + 1
10000 + 0000 - 0101 = x + 10000
只需从两边都去掉10000即可得到x,这是基本代数。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接