原码、补码和反码

原文:http://blog.chinaunix.net/u/20/showart_438418.html

在计算机里如何表示整数?


整数有无穷多个,在计算机里,通常我们只能表示出 其中的一部分。假如我们用 n 个比特来表示一个整数。1 个比特有 2 个状态,n 个比特就有 2^n 个状态,把这 2^n 个状态的集合记为 A. 显然,用 A,我们可以与 n 个整数建立起一一对应。我们还希望 A 所表示的整数能够象整数那样地运算---整数,象整数那样运算,这是不是一句废话?数学中的整数相加,仍然是一个整数,但 A 里两个整数相加,我们却无法保证它们的和仍在 A 中,用代数的术语来讲,叫做 “不满足封闭性”,这是个很坏的性质。



一、补码




不 过数学上有处理这个问题的成熟方案,如果我们能后退一步,让 A 表示的是模 |A| 的剩余类,则加法运算马上就封闭了。而且这个时候 A 不仅可以与 2^n 个整数对应起来,而且,在某种意义下,可以与整数环 Z 对应起来。用代数的观点,这个 “某种意义”就是所谓的同态。

整数有两种封闭运算,一种是加法,另一种是乘法。A 作为模 2^n 的剩余类,也有加乘两种运算。定义 Z 到 A 的映射
f(x) = m mod 2^n

f 是一个同态,也就是说,f 满足这样的良好性质:

f(x+y) = f(x) + f(y)
f(xy) = f(x)f(y)

我 们通常使用 10 进制数,在这个进制下,f(x) 并不容易计算,但是在计算机里,本质的表示是二进制,于是 f(x) 的运算变得出奇地简单。如果 x 小于 2^n,则 x 的 2 进制表示就是 f(x),如果 x>=2^n,则要求其模 2^n 的余数,这恰好是 x 二进制表示的最低 n 位,换句话说,简单地把高位抛弃就行了。顺便指出,f(0)=0, f(1)=1.

我们来看一看 A 中的加法,f(x)+f(y), 若结果小于 2^n,则运算自然封闭,如果 f(x)+f(y) >= 2^n,则取其最低的 n 位,用电路实现时,可以简单地扔掉高位,保留低位。

到目前为止,一切都很好,但是减法怎么办呢?对整数运算而言,减去 a 不过是加上 a 的相反数的同义语。只要对 A 中的每个元素,能容易计算出其相反数就可以了。理论上 f(x) 的相反数就是

f(-f(x))

不过这个好像不容易计算,因为我们现在并没有给出 A 中“负数”的概念,事实上 A 是模 2^n 的剩余类环,根本就没有所谓的负数。

这个困难也是容易处理的。作为 f(x) 的相反数,-f(x) 应该满足这样的性质:

-f(x) + f(x) = f(0) = 0

所 以我们只要有在 A 中找一个元素,使得它与 f(x) 的和是 0 就可以了。但是 f(x) 本身可能含有很多比特 1,加上一个数能使它们变成 0 吗? 考虑到 A 中的加法要模去一个 2^n,这个问题实际上很好办,只要让求出的和是 2^n 就可以了。所以难发现 -f(x) 就是把 f(x) 的比特“取反”---即 0 变 1, 1 变 0,并加上 1 就得到了 -f(x)。容易验证:

f(-x) = - f(x).


现在我们回过头来看前面的一句话,红色部分:

“我们通常使用 10 进制数,在这个进制下,f(x) 并不容易计算,但是在计算机里,本质的表示是二进制,于是 f(x) 的运算变得出奇地简单。如果 x 小于 2^n,则 x 的 2 进制表示就是 f(x),如果 x>=2^n,则要求其模 2^n 的余数,这恰好是 x 二进制表示的最低 n 位,换句话说,简单地把高位抛弃就行了。顺便指出,f(0)=0, f(1)=1.”

红色那句话简直是胡扯,因为没有考虑到负数的情况。但 f(x) 容易计算这句话并没有错,因为当 x 为负数时,我们可以利用 f(x) = -f(-x)。 由于 -x 是正的,f(-x) 容易计算,之后 -f(x) 也不过是取反加 1 而已。

好,到目前为止---在数学世界里,简直是完美的。但是回到现实, A 里头真的没有负数,怎么办?整数能比较大小,A 里头的数又怎么办?

这时候,我们可以用一个不太完美的方案,把 A 里头的元素再映射回整数 Z 中,如果只需要无符号的数,则变换为

g(u) = u,    0<= u <2^n

其实就是不把 A 中的元素模 2^n 的剩余类,而直接看成整数。不过这时的运算就要考虑溢出了。如果是无符号的情形,运算的结果仍是模 2^n 的余数,外加一个溢出标志。

如果要考虑负数,如果没有特别的理由,则要求正负个数大致相等是自然的。可以考虑让 0 代表 0, 1~2^{n-1}-1 代表正数,2^{n-1}+1~2^n-1 代表负数。丢掉一个 2^{n-1} 是因为希望正数和负数刚好配对,若 u 代表负数,则其落在 2^{n-1}+1~2^n-1 中,但它代表负几呢?当然是负 -u 了。从两个相反数之和为 0 ,或 2^n 的观点,-u 就是 2^n-u, 而 u 则是 -(-u) 即 u-2^n。

2^{n-1} 是个麻烦,在 A 中,它的相反数就是自己,把它当正数,负数都不大合理。出于完整性考虑,随便选一个好了。在这里我们让 2^{n-1} 为负数,理由是它的最高位是 1,跟其它“负数”长得比较象。

换个角度看,模 n 的剩余类,或者余数为 0,1,...,2^{n-1}, 2^{n-1}+1, ..., 2^n-1. 这些余数也可以表示为:

0,1~2^{n-1}, 2^n-(2^{n-1}-1), ..., 2^{n}-1

我们刚才所做的就是把上面数列中 2^{n} -r (1<= r<= 2^{n-1}-1)类型的的数对应为负数 -r 而已。用代数的术语,就是在陪集中选取了不同的代表元。

于是我们定义  A  到  Z  的变换,使得

当 0<= u <= 2^{n-1} 时, g(u) = u
当 2^{n-1} <u < 2^n 时,g(u)=u - 2^n

当然,这时运算起来有可能溢出,但结果仍可以看成模 2^n 的余数,外加一个溢出标记。


上面所说的就是补码。



二、反码


抽象地看,反码与补码只有一个区别,同样的 n 比特状态集合 A,反码让这些元素表示模 2^n-1 的剩余类,而补码模 2^n。于是从 Z 到 A 的映射定义为

f(x) = x mod 2^n-1

不过且慢,A 的大小是 2^n,而模 2^n-1 的余数只有 2^n-1 个? 是的,这是反码一个不完美的地方,它浪费了全 1 的码字,不过我们可以把全 1 的和全 0 的数看成一样的。

f 同样是个环同态,满足

f(x+y) = f(x) + f(y)
f(xy) = f(x)f(y)
俄且 f(0)=0, 或者全 1, f(1) = 1.

f(x) 可以计算如下,设
x = 2^n q + r,

则由于 2^n = 1 mod (2^n-1),所以

x = q + r  (mod 2^n -1)

若然 q+r 仍大于等于 2^n,则递归使用上述步骤。当然也可以直接去模 2^n-1,但上面的处理充分利用了二进制表示。而且当 x 为负数时,我们有两外的处理方法,见后面相反数的部分。

f(x) 能求出后,A 中的加法运算和乘法运算也就容易处理了,若 f(x)+f(y)<2^n,则不作特别处理,如果 f(x)+f(y) >=2^n,则结果为 f(f(x)+f(y)) 即把第 n+1 比特加到最低比特上。对于乘法,f(x)f(y) 可以多出n-1 位,处理方法是把第 n+i 比特加到第 i 比特上,或者说把高出 n 位的比特都右移 n 位并加在低位上, 如果仍然越界,则重复上述步骤。从这里可以看到反码的一个弱点,它的越界处理比较麻烦,而补码直接把越界的位丢掉就是了。

A 中的相反数如何求? -f(x) + f(x) = f(0) = 0, 加出一个全零比较难办,但加出一个全 1 不是问题,所以我们可以让 -f(x) 为 x 的取反,即 0 变成 1, 1 变成 0。于是求相反数的问题解决了。

同样,我们可以考虑在反码中引入正数,负数,这个与补码的类似,这里就不多说了。

有 趣的是 2^n 几乎不可能是素数,而 2^n-1 有可能. 2^n-1 形的素数称为梅森素数。如果 2^n-1 是素的,则 A 中非零元素都可求逆。那么对应于 32 位和 64 位计算机的,将会是 31 位计算机和 61 位计算机,看上去很不错嘛,期待中。


这样就结束了我们对反码的讨论。




三、原码


这个没有什么可说的,2^n 个状态直接表示 0~2^n-1,如果要引入负数,则让最高位为 1 的表示负数, 所以 0x 代表 x,而 1x 代表 -x.

原码最好的地方是它简单,最不好的地方在于它没有良好的代数结构。

Monthly Archives

Pages

Powered by Movable Type 7.7.2

About this Entry

This page contains a single entry by Cnangel published on December 9, 2007 6:49 PM.

关于md5和sha1 was the previous entry in this blog.

C语言程序静态库和动态库的创建及其应用 is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.