u

unknown25001

V1

2022/09/24阅读:33主题:默认主题

有符号整数

一个字长为 的二进制序列,有 种可能的取值。无论用何种格式编码,可以表示的数最多为 个。

上一篇介绍了的无符号整数表示,这种方式能表示 个非负整数。

如果我们需要表示负数呢?

最容易想到的方案是,我们可以单独划出一位来存储符号,剩下 位存储数值。

比如我们可以定义最高位为符号位,0为正1为负,那么0_000_0010表示2,1_000_0010表示-2。

这个方案首先有一个弊端:它只能表示 个数,因为1_000_0000和0_000_0000都表示0,这浪费了一个取值的空间。另外,如果用这种表示,上一篇设计的加法器就不能用了,需要设计一种全新的加法器,还需要额外设计一种减法器。

实际上,我们有一种比这高效得多、简洁得多的方案——它不仅不会浪费一位取值空间,还能完全兼容之前设计的加法器的运算规则:如果让负数参与加法,加法器能正确地得出减法的结果。

是不是很神奇?下面就来介绍这种精妙的方法,它的名字叫补码表示法


在补码表示法下, 位二进制数可以表示 范围内的整数。它的对应规则如下:

  • 如果一个整数 ,那么规则与无符号数相同,它对应的二进制数为它对应的无符号二进制数本身;
  • 如果一个整数 ,那么它对应的二进制数,为它的绝对值对应的无符号二进制数每一位取反后 得到的二进制数。

对于一个二进制数,我们定义将它每一位取反后+1的结果为它的补码

比如,对于8位二进制数,如果要表示 ,首先写出它的绝对值 对应的无符号二进制数:

要得到表示 的二进制数,要先把上面这个二进制数每一位取反:

我们约定在补码表示法中整数 对应的8位二进制数记为 ,则上面的计算告诉我们


之前说过,这种表示法是兼容无符号整数的加法器的,如果让负数参与加法,能正确得到减法的结果。 我们可以来验证一下,算一下

根据补码表示法, 对应的二进制数为它本身,而 上面算出来对应的是


······呃,然后呢? 不应该是 吗?这怎么是 呢?

别忘了,我们针对的是 位二进制数的空间,能表示的无符号数最大不超过 ,这 已经超出范围了。

如果你还记得二进制加法器的构造:两个 位二进制数的和,是有可能有 位的,而超出来的这一位会体现在最高位的全加器的进位输出端口

在工程上,我们希望所有数据的位宽都是对齐的,并不希望两个8位二进制数的运算的结果需要准备9个二进制单元取接收(不然,那9位二进制数的运算呢?难道又要额外准备一个9位加法器,拿10位来存结果?然后无限套娃?),这种设计是非常丑陋的。

所以大部分时候我们不会存这个多出来的 ,只存结果的低 位。换句话说,我们讨论的“二进制数加法”并不是真的加法,而是“做加法后只保留结果的低 位”,包含“做加法”和“丢弃高位”两个操作。

丢掉最高位的 ,相当于结果减去了 ,是对的。


终于得到了我们想要的 。现在可以想想,这个 是怎么得到的?

别忘了,从 ,这些二进制数都是非负的二进制数,我们在尝试的其实是用非负二进制整数表示负整数。

同时,我们又要求兼容二进制加法器,那也就是说,当某个数加上一个表示负数的非负二进制数,它表示的值其实是会变小的。

问题来了,一个非负二进制数加上另一个非负二进制数,两个都非负,结果怎么会比原来小呢?

上面的计算过程已经给出了答案:当一个正数加上一个负数时,我们并不是让这个正数直接变小,而是让这个正数变得超级大,大到溢出 的范围,再将溢出的那一位丢掉,只留下超出 的部分,这样留下来的数就不存在“非负数加非负数不可能变小”的限制了。


如何让溢出后留下的结果恰好等于减法的结果呢?这种构造方式又与取补码的操作有何联系呢?下面来看看补码的数学意义。

每一位取反,这个操作的数学意义可能不太好想,我可以直接告诉你:一个 位二进制数取反,相当于用 减它

对吧,在每一位上都有 ,结果刚好是减数取反,而且不涉及借位。

而这个 呢,它其实是 ,再 就是

我们的规则是“负数表示为它的绝对值取反后+1”,那也就是 减它的绝对值,对于负数,这相当于 加它本身

所以 可以写成:

但这样写是有问题的,因为这里的加号就是普通的加号,并没有“舍去高位只保留低 位”这层意思。也可以换句话说:这里的等号并不是真的“相等”的意思,而是“低 位相等”的意思。

如果想去掉一个非负二进制数的高位,只保留低 位,可以考虑用整除 取余数的方法,简称对 取模,或者简称模

这就类似于如果你想把一个十进制数的高位截掉,只保留低 位 ,可以用这个十进制数对 取模。

如果两个数对整数 取模的结果相等,我们就称这两个数对 同余,记为 。 对于两个非负二进制数,“对 同余”和“低 位相等”这两句话是等价的。

所以 应该写成这样:

我们需要证明的是这个:

证明这条性质,需要用到同余的一条简单的性质:

根据 ,能得到以下引理:

下面开始证明。


考虑到 分别 两种情况, 有以下四种情况:

可能的取值有这三种:

根据引理 ,这三种全都对 同余:

也就是说:

恒成立。

接下来只需要证:

即证:

由引理

综上:

因此:

证毕。

最后一步用到了同余的传递性:

证明略,不难。


有些数学天赋较高的同学一看到这条:

就瞬间懂了,之前没懂只是因为他们对二进制运算不够熟悉,没有意识到“按位取反等效于用 去减”这一点。当他们看到了真正的数学描述,一切顿时变得显然了起来。

就算你对数字没有那么敏感,看完上面并不复杂的证明过程,你大概率也会觉得这个证明多多少少带点别扭,也许能隐隐感觉到,这个证明似乎并不需要这么复杂,应该存在一种更加优美、简洁的数学工具。

这个感觉是对的。在数论中你会学到,无论是无符号整数的 ,还是有符号数的 ,这两个整数集其实都是模 完全剩余系

具体来讲,同余的概念是可以用来给全体整数分类的。对于模 可以分为 类:模 等于 的数一类,等于 的数一类······模 等于 的数一类。模 等于 的数构成的集合,被称为模 剩余类,记为 。 我们最熟悉的奇数和偶数,其实就是对模 分类,奇数模 等于 ,偶数则等于 ,一共两类,分别对应模 剩余类和 剩余类。

如果在每一类中都挑一个数出来,构成一个 个整数的集合,这个集合其实就是模 的完全剩余系,这就是模 的完全剩余系的定义。

显而易见的是,对于任意整数 ,它和 一定是属于同一个模 剩余类的,而且它所在的模 剩余类的其它元素也一定可以写成 的形式,毕竟加减任意个 都不会影响 的结果,所以我们称 为它所在模 剩余类的代表元——显然,其中的每个元素都可以是这个模 剩余类的代表元。

因此,在 的时候我们取的 ,它跟小于零的 属于同一个模 剩余类。

而很容易想到,一个模 剩余系的每个数,在参与“相加减后模 ”的运算时,全都具有完全相同的运算性质,多出来的整数倍个 的影响都被取模的操作抹掉了。

因此,任何一个 位二进制数参与二进制加法(实际上是参与二进制加法且结果模 )时,它能代表的整数的不仅仅是它自己,也可以是它所属的模 剩余类中的任意一个元素——毕竟这些元素参与运算时的性质都是完全一致的。

事实上,补码表示法不仅兼容二进制加法,还兼容二进制乘法——

在参加“相乘后模 ”的运算时,同一模 剩余类中的全部元素,依然具有完全相同的运算性质——因为这依然只是整数倍个 的区别,依然可以被模 的操作抹掉。


现在我们知道了,在二进制加法和乘法(并模 )的运算中,一个数可以代表任意个与它模 同余的数。具体代表哪一个,则有我们按照实际需要赋予它意义:

我们需要表示负数,那就在它所属的模 剩余类中挑一个负数,用它来表示这个负数;

如果我们不在乎负数,只在乎更大的数值表示上限,那就用它表示它本身;

你甚至完全可以用 位二进制数表示 ,相当于把整个区间往右平移了 ,这依然是一个模 的完全剩余系;

你还可以在每个模 剩余类里闭着眼睛随便取,取出一系列既有正数又有负数而且每个数都相距十万八千里的 个数,这还是一个模 剩余系,依然可以用 位二进制整数表示,这看起来没什么用,但当你接触到哈希算法,你会发现这就是“如何把若干个八竿子打不着的整数用有限长度的二进制数表示,并且尽可能避免碰撞”的一种基本解决思路。

由于 位二进制加法天生带有“结果对 取余”(即舍去高位)这一特性,这套以同余为基础的数学工具,在CS的某些特定领域是极其重要、极其好用的。如果你想进一步系统学习这个数学工具,可以去选修数论课。


你也许发现,如果只规定“负数对应绝对值取补码”这一对应规则,那么能表示的整数区间其实是不确定的,这个 的区间是我们额外规定的,完全可以换成其它区间。

我们以简单的 位二进制整数为例,在补码表示法中,每个四位二进制数的对应的整数为:

X f(X)
0 0000
1 0001
... ...
7 0111
-8 1000
-7 1001
... ...
-1 1111

如果我们想表示 呢?可以表示 吗?

你会发现完全是可以的: 的绝对值是 ,取反变成 变成

唯一的问题是,我们把负数的表示范围扩大了一位,那么正数的范围则缩小了一位,最大的正数 就无法表示了,能表示的整数由 变成了

这个表示法可以用吗?完全可以

之所以我们硬性规定表示的整数一定是 ,也就是 ,不仅是为了对称显得好看,如果你仔细观察上面的表格,你还会发现一条重要的性质:负数的最高位一定是 ,非负数的最高位一定是

因此,我们称有符号二进制数的最高位为符号位,这并不是因为我们规定了最高位用来存放符号,而是我们的编码方式,恰好让最高位可以反映这个数的正负

分类:

其他

标签:

其他

作者介绍

u
unknown25001
V1