随笔 关于二进制补码的一点思考
内容纲要

:sun_with_face:

讨论补码的前提

  二进制的基本原理不难理解,与十进制之间的互换也可以很快掌握。当数的范围框定在非负整数内时,一切都还岁月静好,但涉及负数的表示方式时就麻烦许多了。二进制本身并不能表示负数,基于二进制的功能,我们也不可能在其前面添加一个负号-,人们研究出了“符号位”的表示方法,这其中涉及到的一系列转换方式,其背后的数学原理是本文试图梳理的内容。我总结了多本书中的二进制补码部分的内容,综合归纳出一个尽量全面的补码知识。

  在几乎所有讲解二进制负数表示方式的书中,都会明确的说到,将最左侧位(即最高位MSB)设置为符号位,0意味着正数,1意味着负数。其余的位则是数值位。单就一个“带符号的二进制数”来说,这个规则很好理解,也使我们能够快速辨识正负数。不过在完整学完补码之前,它都会使我们产生一种错觉:最高位与它身后的一堆数字是分隔开的,不属于数值内容,很自然的,许多人会觉得它也不应该参与运算(它只是个正负号嘛),这显然会为后面的加减法学习带来阻碍。这里,我尝试综合多本书的内容,将补码从方法到原理尽量梳理清楚,但是跳过不必要的探究过程(比如one's complement)。
  首先强调两个既定规则和一个前置条件。前置条件是指,当我们讨论某个二进制数时,必须先明确,它是带符号的还是不带符号的? 有了这个前提条件,我们才知道到底要如何看待这个数。本文讨论的显然是带符号的,也就是最高位是“符号位”(sign bit)。与此同时,这也意味着其数字体系已经在一个重要规则之下了,那就是定长。如果长度不确定或不统一,某一位代表什么符号就毫无实际意义了。本文以一个字节的长度为例(8-bit)。通过阅读多本讲解二进制入门的书,我发现这一点往往没有得到足够的强调,对于初学者来说,可能会在一开始感觉有点不清不楚。从“定长”延伸出来的另一个“默认习惯”是溢出忽略。如8比特位长,当我们进行各种运算时,出现了进位,长度到了第九位,那么“溢出”的部分是忽略掉的。这些都基于第一大规则:定长。第二个需要强调的规则是二进制列权值column weighting,这里主要说转换十进制所用的列权值。列权或者说位权/位值的概念早已不新鲜,几乎所有我们用得上的数字系统都属于“位值计数法”(罗马数字不是),不同“位置”的数字有着不同的单位“值”。对于以最高位MSB作为符号位的二进制补码体系,明确它的column weighting不仅对于转换十进制数值很关键,也是我们作为“十进制生物”理解它们的重要手段。8-bit二进制补码所使用的column weighting是:
-128   64   32   16   8   4   2   1
这是一个精巧好用的计算表,后面会用到。

从“补数”开始理解

  接下来,进入正题。按照一般顺序,讲解补码,当然是先说原码,然后说反码,再加1获得补码。这一点对于需要读此文的人来说已无需赘述,让我们直接进入对“补”的理解吧。这里借用Charles Petzold的CODE 《编码》这本书第十三章“如何实现减法”的内容。这本书是少有的将补码底层逻辑讲清楚的著作。截至第十二章末,作者带着我们完成了一个用开关电路搭建出来的二进制加法器,接下来就要面对复杂的减法。与加法的“进位”不同,减法需要“借位”,书中的例子:
 $253$
$\underline{-176}$
 ? ? ?
我们都知道如何计算,3小于6,因此向前借一位,变成13-6得7;5被借走一位变成了4,4也小于7,向前借一位,于是14-7得7;2被借走一位,1-1得0,因此最后得到结果77. 但是这一复杂的逻辑,无法使用简易的加法器,一位对应一位的直接求得,“借位”是需要避免的。什么情况下不需要借位呢?—— 被减数每个位上的数都比减数相应位的数大时。在十进制中,最大的数字是9,因此,在这里先用一个999(因为减数是三位数)来减:
 $999$
$\underline{-176}$
 $823$
这种情况就可以简单的在每一个位上直接减,避免了借位。接下来是用得到的结果823加上原来的被减数253得到1076.

  为了提醒自己正在干嘛,先把这一过程的代数变换写下来,同时强调“减法本质上仍然是加法”这一思路。
253-176=(+253)+(-176)=(+253)+(-176)+1000-1000=(+253)+(-176)+999+1-1000=999-176+253+1-1000
等式两边的恒等关系肯定没有疑议,至于为什么要这样,后面就清楚了。别忘了,我们现在正试图解决二进制的负数表示方法的问题,而在探讨补码的逻辑之前,我是在利用《编码》这本书中的简易“加法器”实验,尝试在一个逻辑简单的加法器上实现复杂的减法。用三位数999去减一个任意三位数,可以保证避免借位,之后,把原本的被减数(一个正数)加回来,所得结果1076加1得1077,再减去(我们凭空添加上去的)1000,得最终结果77,结果正确。现在可以引入“补数”的概念了,用999减去176所得的是可称之为176对于9的“补数”,反过来也一样,823对于9的补数就是176. 所以这一“减法”方式简单来说就是先求减数对9的补数,然后把被减数加上,最后就是加1减1000得到结果。但是,如果被减数小于减数,也就是所得结果为负的情况就又有了新的问题。比如176-253,最后一步又会遇到923-1000,不得不借位。这种情况所用的代数过程是“加999减999”。 
 $999$
$\underline{-253}$
 $746$
然后加上被减数:
 $746$
$\underline{+176}$
 $922$
最后一步遇到了“小的减大的”,我们知道实际运算中,仍然是用大的减小的,然后加上负号即可:
 $922$
$\underline{-999}$
$-077$   999减922时仍然避免了借位。

现在,利用类似的思路尝试二进制减法。把253-176变为二进制:
 $11111101$
$\underline{-10110000}$
????????

首先还是求补数,8位二进制数的最大值就是11111111,
 $11111111$
$\underline{-10110000}$
 $01001111$

看到这里,是不是一下子想到了“反码”?前面定义了“9的补数”,这里其实就是求出了1的补数。而由于是二进制,除了1就是0,所谓“1的补数”,实际上不需要去计算,只需要把1变为0,把0变为1,这不就是所有书上都会告诉我们的反码(inverse)嘛!有时,它也可称为相反数(negation)。如果不从“反向”的角度去理解,而是顺着刚刚我们运算十进制时求“补数”的思路下来,二进制的“反码”意义似乎清晰了许多。接下来,和前面一样,把被减数加上去:
 $01001111$
$\underline{+11111101}$
 $101001100$

下一步是加1:
   $101001100$
$\underline{+000000001}$
 $101001101$
前面我们给整个式子额外加上了11111111(255),然后又加了1,现在就减去256即100000000: 
 $101001101$
$\underline{-100000000}$
 $001001101$  (这便得到了77)

类似的,求二进制下的176-253: 10110000-11111101,第一步仍然是求减数的“对1的补数”,我们已经知道捷径了,直接取反即可,得到00000010;把这个补数与原被减数相加:
 $00000010$
$\underline{+10110000}$
 $10110010$
这个过程实际上是凭空加上去了一个11111111,既然多加了11111111,现在在结果中减掉它。同前面的差为负的十进制减法一样,小的减大的情况,实际运算还是反过来,最后取其相反数。
 $11111111$
$\underline{-10110010}$
 $01001101$   得到了77,但真正的答案是-77。

 到这里,减法机制并没有彻底说完,不过,对于本文的目标——理解二进制负数表示法已经足够了。《编码》这本书很精彩,提供了精细的思路,我无意在此把书中内容搬运更多。接下来我们可以回到二进制补码的“传统”讲述上了。

 我们都知道补码是什么,或者说补码是“如何算出来的”——取反,然后加1。 求“反码”的过程是个中间步骤,因此有人说,反码是补码与原码之间的一个“桥梁”。不过,补码这个名词有点模糊,甚至省略掉了关键信息。我们现在所说的二进制补码,它的英文原名是Two's complement, 直译就是“2的补数”,这一点非常非常非常关键,如果不理解Two's complement说的是什么,就等于根本没有理解补码的概念。
 求反码被我们视作“中间步骤”,这一步其实原本叫做One's complement。One's complement和Two's complement都是二进制负数表示法,而1的补数,在二进制中等价于取反(这个思考逻辑很重要),所以1的补数其实就是“反码”。而用这种方法来表示负数用很多误差隐患,而且会出现+0和-0的尴尬,已被弃用,具体内容这里略过。另一方法,也就是我们现在都在用的负数表示法,是计算“2的补数”,也就是我们都知道的,先求1的补数,然后再加1,即所谓的Two's complement。

为了验证这种表示法的准确性,我们可以随便选一个正数,然后计算其负数,二者相加如果为0,说明负数表示正确。比如66,其二进制为01000010,这是它的原码,而正数的补码仍然是原码保持不变,现在将其取反然后加1得到10111110,这就是得到了表示负数的补码,-66. 现在将原码和补码相加:
 $01000010$
$\underline{+10111110}$
  $100000000$  超过了8位,溢出忽略得到0.
这说明补码表示正确。

现在可以把补码的column weighting搬出来用了。
-128   64   32   16   8   4   2   1
现在已知补码10111110,我们可以用这个8-bit的列权值计算它对应的十进制数:
$-128*1+64*0+32*1+16*1+8*1+4*1+2*1+1*0=-66$
可见,结果正确。
由于正数总是0开头,转换正数时,显然根本不会用上最高位的位置-128,而负数总是以1开头,转换负数二进制到十进制时,计算过程总是-128加上其他位的值。这里已经提示了下一个小话题,补码的数字表示范围。

 二进制能够表示的数的范围取决于它的位数,当我们将其最高位用作符号位时,直觉上似乎是“浪费”了一位。比如8bit的二进制,正常来说可以表达0~255共256个数。但是去掉一位后剩下七位,就只能表示128个数了,然而“补码”的设计的精妙之处就在于,它刚好在正负数区间“平分”了取值范围,实际上我们完全没有浪费位数。8bit补码的表示范围在[-128,+127],刚好也是256个数。

补码对于数字音频设备的意义

 补码就是所谓的机器码,计算机中存放数据使用的都是补码,数字音频设备也同样使用这种二进制系统。补码的特征对于数字音频设备来讲,有突出的优点,这里摘抄一部分《数字音频工作站原理》(录音艺术专业「十二五」规划教材,雷伟 著)中的内容。这是一本相当优质的教材,几乎每个章节的重要知识点都讲解的非常清楚、明白。

  • 音频信号这种波动信号,存在正向和负向的振幅,补码因为能够表示正负数,刚好满足了这种需求;

  • 数字音频设备出现故障时,由于内部数据均为二进制,可能会出现数据中所有位全变成了1或者0的情况,如果变成了111... 数值达到了最大,这将意味着突发性噪声达到最大。但如果使用补码,全0相当于0,全1则表示-1(用上面的column weighting可以计算),也就是说两种故障情况,输出值都是接近0的状态,这可以有效降低突发性噪声,减小故障。

 前面在验证负数表示是否正确时,用到了两个正负数相加,检测其结果是否为0的方法。实际上这正是补码的实际意义之一。通过给原有正数加上补码,可以使其原有位数全部变为0,这个过程当然是在高一位产生了1,但二进制体系是“定长”的,溢出的位被忽略(无效),所以我们得到了实际范围内的最小值。 除此之外,还有一个优点,就是本文开头所用的例子,如果只有逻辑简单的加法器,同样可以实现减法,这大大简化了系统的设计。

 以上就是对于二进制补码的知识总结。欢迎专业人士交流、探讨! :full_moon_with_face:

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇