我正处于一个计算机系统课程中,并且一直在与Two's Complement进行斗争 . 我想了解它,但是我为了我而把这张照片带到了一起 . 我已经阅读了wikipedia article和其他各种文章,包括my text book .
因此,我想开始这个 community wiki 帖子来定义Two's Complement是什么,如何使用它以及它如何在诸如强制转换(从有符号到无符号,反之亦然),逐位操作和位移操作等操作期间影响数字 .
我希望的是 a clear and concise definition ,程序员很容易理解 .
17 回答
二进制补码是一种存储整数的聪明方法,因此常见的数学问题很容易实现 .
要理解,您必须考虑二进制数字 .
它基本上说,
为零,使用全0 .
为正整数,开始向上计数,最大值为2(位数 - 1)-1 .
对于负整数,做完全相同的事情,但切换0 's and 1' s的角色(所以不是从0000开始,从1111开始 - 这是"complement"部分) .
设's try it with a mini-byte of 4 bits (we' ll称之为nibble - 1/2个字节) .
0000
- 零0001
- 一个0010
- 两个0011
- 三0100
至0111
- 四至七这就是我们可以采取积极的态度 . 23-1 = 7 .
对于否定:
1111
- 否定一个1110
- 否定两项1101
- 否定三1100
至1000
- 负四至负八请注意,您可以获得一个额外的负值(
1000
= -8),而不是肯定的 . 这是因为0000
用于零 . 这可以被视为Number Line的计算机 .Distinguishing between positive and negative numbers
这样做,第一位获得"sign"位的作用,因为它可用于区分正十进制值和负十进制值 . 如果最高位是
1
,那么二进制可以说是负数,其中最高位(最左边)是0
,可以说十进制值是正数 ."One's compliment"负数只是翻转符号位,然后从0开始计算 . 但是这种方法必须处理
1000
解释为令人困惑的"negative zero" . 在靠近硬件工作时,通常只需要担心这一点 .我想知道它是否可以比维基百科的文章更好地解释 .
您尝试使用二进制补码表示来解决的基本问题是存储负整数的问题 .
首先考虑以4位存储的无符号整数 . 您可以拥有以下内容
这些是未签名的,因为没有迹象表明它们是否定为正面 .
签名量级和超额表示法
要存储负数,您可以尝试许多事情 . 首先,您可以使用符号幅度表示法,它将第一个比特分配为符号位来表示/ - 以及剩余的比特来表示幅度 . 所以再次使用4位并假设1表示 - 而0意味着你有
那么,你看到那里的问题?我们有正负0.更大的问题是加和减二进制数 . 使用符号幅度进行加减的电路将非常复杂 .
什么是
?
另一个系统是excess notation . 你可以存储负数,你摆脱了两个零问题,但加法和减法仍然很难 .
所以随之而来的是两个补充 . 现在,您可以存储正负整数并相对轻松地执行算术运算 . 有许多方法可以将数字转换为二进制补码 . 这是一个 .
将十进制转换为二进制补码
将数字转换为二进制(暂时忽略符号),例如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 =?
使用两个补码考虑它是多么容易 .
将二进制补码转换为十进制
将1111转换为十进制:
数字以1开头,所以它是负数,所以我们找到1111的补码,即0000 .
添加1到0000,我们获得0001 .
将0001转换为十进制,即1 .
应用sign = -1 .
田田!
像大多数解释一样,我补充说,但并没有真正解释它们在数学上是什么 . 我会首先介绍一些可能很熟悉的背景知识 .
回想一下十进制的工作原理:
2345
是一种写作方式
2 ×103 3 ×102 4 ×101 5 ×100 .
以同样的方式,二进制是一种使用 0 和 1 编写数字的方法,遵循相同的一般想法,但用2代替上面的那些10 . 然后是二进制,
1111
是一种写作方式
1 ×23 1 ×22 1 ×21 1 ×20
如果你解决了,那就等于15(基数为10) . 那是因为它是
8 4 2 1 = 15 .
对于正数而言,这一切都很好 . 如果你愿意在他们面前贴一个减号,它甚至适用于负数,就像人类用十进制数字做的那样 . 这甚至可以在计算机中完成,但是从1970年代早期开始我就没有看过这样的计算机 . 我将留下不同讨论的理由 .
对于计算机来说,使用补数表示来表示负数是更有效的 . 在这里_757505的尴尬,因为问题出现了:所有这些?这可能是要考虑的无限数字 .
幸运的是,计算机不会返回正二进制数,但具有特定的大小 . 对于这些示例,我将使用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 被理解为代表
注意"-"在那个表达式的前面?这意味着符号位带有权重-27,即-128(基数为10) . 所有其他位置保留与无符号二进制数相同的权重 .
制定我们的-15,它是
-128 64 32 16 1
试试你的计算器吧 . 这是-15 .
为了方便起见,我补充了三种主要方式 . 但它有一个奇怪的地方 . 因为's binary, there have to be an even number of possible bit combinations. Each positive number can be paired with its negative, but there'只有一个零 . 否定零会让你变为零 . 所以还有一个组合,符号位中的 1 和其他地方的 0 . 相应的正数不符合正在使用的位数 .
对于这个数字更奇怪的是,如果你试图通过补充和添加一个来形成积极的,你会得到相同的负数 . 看起来很自然零会做到这一点,但这是意料之外的,而不是我们习惯的行为,因为除了计算机之外,我们通常会想到无限制的数字,而不是这种固定长度的算术 .
这就像是一个奇怪的冰山一角 . 在表面之下还有更多的等待,但这对于这次讨论来说已经足够了 . 如果研究定点算术的“溢出”,你可能会找到更多 . 如果你真的想进入它,你也可以研究“模运算” .
2的补码对于找到二进制的值非常有用,但是我想到了解决这个问题的更简洁的方法(从未见过其他人发布过它):
取二进制,例如:1101 [假设空间"1"是符号]等于 -3 .
使用2的补码我们会这样做...翻转1101到0010 ...添加0001 0010 ===>给我们0011. 0011 in positive binary = 3.因此1101 = -3 !
What I realized:
而不是所有的翻转和添加,你可以只做基本方法求解正二进制(假设0101)是(23 * 0)(22 * 1)(21 * 0)(20 * 1)= 5 .
Do exactly the same concept with a negative!(with a small twist)
以1101为例,例如:
对于第一个数字而不是23 * 1 = 8 ,请 - (23 * 1)= -8 .
然后像往常一样继续做 -8 (22 * 1)(21 * 0)(20 * 1)= -3
想象一下,你有一个有限数量的位/ trits / digits /无论如何 . 您将0定义为所有数字为0,并自然向上计数:
最终你会溢出 .
我们有两位数字,可以代表从0到100的所有数字 . 所有这些数字都是正数!假设我们也想表示负数?
我们真正拥有的是一个循环 . 2之前的数字是1. 1之前的数字是0. 0之前的数字是...... 99 .
因此,为简单起见,我们可以说任何超过50的数字都是负数 . “0”到“49”代表0到49.“99”是-1,“98”是-2,......“50”是-50 .
这种表示是 ten's complement . 计算机通常使用 two's complement ,除了使用位而不是数字之外,它们是相同的 .
关于十个补码的好处是加法才有效 . 您不需要做任何特殊的事情来添加正数和负数!
两个补充是通过添加给定数字的第1至第1补充来发现 . 让我们说我们必须找出
10101
的两个补码,然后找到它的补码,即01010
将1
加到这个结果,即01010+1=01011
,这是最终答案 .让我们用8位以二进制形式得到答案10 - 12:我们真正做的是10(-12)
我们需要得到12的赞美部分从10中减去它 . 二进制中的12是00001100.二进制中的10是00001010 .
为了获得12的赞美部分,我们只需将所有位反转,然后加上1. 12 in binary reverse is 11110011.这也是反向代码(一个补码) . 现在我们需要添加一个,现在是11110100 .
所以11110100是12的赞美!当你这么想的时候很容易 .
现在你可以用二进制形式解决上面10-12的问题了 .
从数学的角度来看两个补码系统真的很有意义 . 在十个补充中,想法是基本上“隔离”差异 .
示例:63 - 24 = x
我们添加24的补充,实际上只是(100 - 24) . 所以,我们所做的只是在等式的两边增加100 .
现在等式是:100 63 - 24 = x 100,这就是我们删除100(或10或1000或其他)的原因 .
由于不得不从一长串零中减去一个数字的不方便,我们使用“缩小基数补充”系统,在十进制系统中,九个补码 .
当我们从一大串9中减去一个数字时,我们只需要反转这些数字 .
示例:99999 - 03275 = 96724
这就是为什么,在九次补充之后,我们加1.你可能从童年时期的数学中知道,9通过“偷”来变成10级 . 所以基本上它只是10的补码,从差异中取1 .
在Binary中,两个补码相当于十的补码,而一个补码相当于九的补码 . 主要区别在于,我们不是试图将差异与10的幂相加(将10,100等加到等式中),而是试图将差异与2的幂相区分 .
因此我们将这些位反转 . 就像我们的minuend是十进制的九连串一样,我们的minuend是一个二进制的连锁 .
示例:111111 - 101001 = 010110
因为1的链条低于2的良好幂,它们会从差值中偷取1,就像十进制中的9 .
当我们使用负二进制数时,我们只是说:
0000 - 0101 = x
1111 - 0101 = 1010
1111 0000 - 0101 = x 1111
为了'隔离'x,我们需要添加1,因为1111是远离10000的一个,我们删除了前导1,因为我们只是将它添加到原始差异中 .
1111 1 0000 - 0101 = x 1111 1
10000 0000 - 0101 = x 10000
只需从两侧移除10000即可获得x,它是基本的代数 .
到目前为止,许多答案很好地解释了为什么两个补码用于表示负数,但是不要告诉我们两个补码是多少,特别是不是为什么添加'1',实际上往往以错误的方式添加 .
混淆来自对补数的定义的不理解 . 补充是缺少可以完成某些事情的部分 .
根据定义,基数b中的n位数x的基数补数是b ^ n-x . 在二进制4中,由100表示,其具有3个数字(n = 3)和2的基数(b = 2) . 因此它的基数补数是b ^ n-x = 2 ^ 3-4 = 8-4 = 4(或二进制100) .
然而,在二进制中获得基数的补码并不像得到它的基数补集那么容易,它被定义为(b ^ n-1)-y,只比基数补数小1 . 要获得减少的基数补码,只需翻转所有数字即可 .
100 - > 011(减少(一个)基数补语)
为了获得基数(二)的补集,我们只需加1,作为定义的定义 .
011 1 - > 100(二进制补码) .
现在有了这个新的理解,让我们来看看Vincent Ramdhanie给出的例子(见上面第二个回复)
/ *文森特的开始
将1111转换为十进制:
数字以1开头,所以它是负数,所以我们找到1111的补码,即0000.加1到0000,我们得到0001.将0001转换为十进制,即1.应用符号= -1 . 田田!
文森特的结尾* /
应该理解为
这个数字从1开始,所以它是负数 . 所以我们知道它是某个值x的二进制补码 . 为了找到由它的二进制补码表示的x,我们首先需要找到它的1的补码 .
x的两个补码:1111 x的补码:1111-1 - > 1110; x = 0001,(翻转所有数字)
应用符号 - ,答案= -x = -1 .
它是一种巧妙的编码负整数的方法,使得数据类型的大约一半位组合保留用于负整数,并且大多数负整数与其相应的正整数相加会导致进位溢出将结果保留为二进制零 .
所以,在2的补充如果一个是0x0001则-1是0x1111,因为这将导致总和为0x0000(溢出为1) .
2的补充:当我们添加额外的1和1的数字补码时,我们将得到2的补码 . 例如:100101它的1的补码是011010而2的补码是011010 1 = 011011(通过加1补1)For more information本文以图形方式解释它 .
我喜欢lavinio的答案,但是移位会增加一些复杂性 . 通常在尊重符号位或不遵守符号位时可以选择移动位 . 这是将数字视为带符号(半字节为-8到7,字节为-128到127)或全范围无符号数(半字节为0到15,字节为0到255)之间的选择 .
几个星期前我遇到了同样的问题 . 我最后从各种来源在线阅读它,尝试将各个部分放在一起,并自己写一下,以确保我理解正确 . 我们使用两个补码主要有两个原因:
避免多次表示为0
在溢出的情况下,避免跟踪进位(如在一个补码中) .
执行加法和减法等简单操作变得容易 .
如果您想对手头的问题有更详细的解释,请尝试我写的文章here . 希望能帮助到你!
我读了一个奇妙的解释on Reddit,用里程表作为类比 .
参考:https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html
我反转所有位并添加1.编程:
您还可以使用在线计算器计算十进制数的二进制补码表示:http://www.convertforfree.com/twos-complement-calculator/
最简单的答案:
1111 1 =(1)0000 . 所以1111必须是-1 . 然后-1 1 = 0 .
对我来说理解这些都是完美的 .