二进制补码是一种聪明的整数存储方法,使得常见的数学问题非常容易实现。
要理解这个概念,你必须把数字想象成二进制。
它基本上是这样说的:
让我们用四位的迷你字节(我们称之为半字节- 1/2个字节)来尝试一下。
0000
- 零0001
- 一0010
- 二0011
- 三0100
到 0111
- 四到七这就是我们在正数方面所能达到的极限了。23-1 = 7。
对于负数:
1111
- 负一1110
- 负二1101
- 负三1100
到 1000
- 负四到负八请注意,负数比正数多一个值(1000
= -8),因为0000
用于表示零。这可以被视为计算机的Number Line。
区分正负数
为了区分非负和负的十进制值,第一位扮演"符号"位的角色。如果最高位是1
,则可以说该二进制数是负数,而如果最高位(最左边)是0
,则可以说该十进制值是非负数。
"Sign-magnitude"负数只需将其正数相对应的符号位取反,但这种方法必须处理将1000
(一个1
后跟所有0
)解释为“负零”的情况,这很令人困惑。
"Ones' complement" 负数只是其正数对应位的补码,这也导致了一个令人困惑的“负零”,即 1111
(全为1)。
除非您非常接近硬件工作,否则您很可能不需要处理 Ones' Complement 或 Sign-Magnitude 整数表示法。
我想知道这个问题是否可以比维基百科文章更好地解释。
用二进制补码表示法解决的基本问题是如何存储负整数。
首先,考虑一个用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 +
----
另一个系统是过量符号表示法。你可以存储负数,摆脱两个零的问题,但加法和减法仍然很困难。
于是出现了二进制补码。现在你可以存储正数和负数,并且可以相对容易地执行算术运算。有许多方法将一个数字转换为二进制补码。这里是其中一种方法。
将数字转换为二进制(暂时忽略符号) 例如,5是0101,-5是0101。
如果这个数字是一个正数,那么你就完成了。 例如,5在二进制中使用二进制补码表示为0101。
如果这个数字是负数,则
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开头,因此是负数,所以我们找到1111的补码,即0000。
将0000加1,得到0001。
将0001转换为十进制,得到1。
应用符号 = -1。
Tada!
就像我看到的大多数解释一样,上面的解释明确介绍了如何使用二进制补码操作,但并没有真正解释它们在数学上是什么。至少对于整数,我将尝试解释一下,并首先介绍一些可能熟悉的背景知识。
回忆一下十进制如何运作:
2345
是一种写法,
2 × 103 + 3 × 102 + 4 × 101 + 5 × 100.
同样地,二进制是一种只使用0和1来表示数字的方式,遵循相同的基本思想,但用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呢?
这个数字更奇怪的地方在于,如果你尝试通过取反加一来形成它的正数,你会得到同样的负数。虽然零似乎也会有这种行为,但这是出乎意料的,而且与我们通常认为的不同,因为除了计算机之外,我们通常认为数字具有无限长度,而不是固定长度的算术。
这就像奇异性的冰山一角。在表面下还有更多等待我们去发现,但对于本次讨论,以上内容已经足够了。如果您想了解更多信息,可以搜索“固定点算术溢出(overflow)”。如果您真的想深入了解,您还可以研究“模运算(modular arithmetic)”。
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
假设你有一定数量的比特位/三进制位/数字等。你将所有数字都定义为0,并按自然数顺序逐个递增:
00
01
02
..
终究你会溢出。
98
99
00
我们有两个数字,可以表示0到100的所有数。所有这些数都是正数!假设我们也想表示负数?我在Reddit上读到了jng的一个精彩解释(链接),他使用里程表作为类比。
补码是通过对给定数字的1'st补码加1来找到的。
假设我们需要找到10101
的补码,然后找到它的1'st补码,也就是01010
,将这个结果加上1
,即01010+1=01011
,这就是最终答案。
00001010
11110100
-----------------
11111110
“补码”一词来源于“完整性”。在十进制中,数字0到9提供了一组补码(完整集)用于表示所有的十进制数。在二进制中,数字0和1提供了一组补码用于表示所有二进制数。实际上,符号0和1必须用来表示所有东西(文本、图像等),以及正数(0)和负数(1)。
在我们的世界中,数字左侧的空格被视为零:
35=035=000000035.
[0101]=[00101]=[00000000000101]=5 (base 10)
[1011]=[11011]=[11111111111011]=-5(base 10)
if a >= 0 then |a| = a
if a < 0 then |a| = -a = 2scomplement of a
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 Carry 00000 Carry
0110 is the same as 00110
-0111 +11001
---------- ----------
sum 0101 sum 11111
0
而是给出2^N
(根据定义),例如对于数字A
的 3 位,我们想要A+~A=2^N
所以010 + 110 = 1000 = 8
,这是2^3
。至少这解释了在这里“补码”一词的含义,它不仅仅是将0
和1
的含义取反。MIT 有用的视频:https://www.youtube.com/watch?v=RbJV-g9Lob8 - Charlie Parker