unknown25001

2022/09/24阅读：43主题：默认主题

有符号整数

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

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

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

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

比如我们可以定义最高位为符号位，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

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

你会发现完全是可以的：的绝对值是，取反变成，变成。

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

这个表示法可以用吗？完全可以。

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

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

分类：

其他

标签：

其他

作者介绍