0.2 位的知识

计算机中的数据和信息都要表示为1和0的组合。在这种组合的表达式中，我们把每8个二进制位合称为一个字节。比如，11010101就是一个字节，0100000110011101就是两个字节，其中的每一个二进制位称为一个比特。我们可以从左至右给一个字节的8个位排序（依次记为从7至0）。现在想象有这么一个字节，如图0.2.1所示。

在上图中，128=27，64=26，…，依此类推。因此，一个字节所能表示的最大数是各位均被置为1的数：11111111。该二进制数的值等于：

128+64+32+16+8+4+2+1=255

最小的二进制数是00000000。所以，一个字节能存放从0到255这个范围内的数，总共有256个可能的值。

大多数计算系统的内存储器是由许许多多被称为字节的单元组成的。每一个字节有一个地址。每一个存储单元存放一个数据或一条指令。在微型机中一般以4个字节存放一个实数，以2个字节存放一个整数。为简化起见，下面我们只用一个字节存放一个整数。

如果存放的是带符号的数，通常将第7个字位放置符号，非负整数置为0，负整数置为1。比如，

+7 的原码为00000111（最左边的0表示非负整数）

-7 的原码为10000111（最左边的1表示负数）

二进制数111代表十进制的7。如果用2个字节存放一个整数，情况是一样的。比如+7的原码为0000000000000111。

根据以上规则，0的原码如下：

+0 的原码为00000000

-0 的原码为10000000

这样一来，表示同一个数0的+0和-0在内存中就有两个不同的形式，也就是说0的表示不是唯一的。这显然不适合于计算机的运算。下面介绍反码。

如果一个数值为正，则它的反码与原码相同。比如，

+7 的反码为00000111

127 的反码为01111111

+0 的反码为00000000

如果一个数值为负，则其符号位仍为1，其余各位是对原码取反（也就是把0换为1，1换为0所得）。比如，

-7 的反码为11111000

-127 的反码为10000000

-0 的反码为11111111

此时，0的表示仍是不唯一的。

原码和反码都不便于计算机的运算，因为在运算过程中要先判断各自的符号位，然后才能对后7位进行相应的处理，很不方便。为了将符号位和其他位进行统一处理，对减法也能按照加法来处理，这就需要补码。补码是这样规定的。

如果一个数是正数，其原码、反码、补码都相同。比如，

+7 的补码为00000111

如果一个数是负数，其补码的最高位仍为1，其余各位为原码的取反，然后对整个数再加1。比如，

-7 的补码为11111001

-0 的补码为00000000

+0 的补码为00000000

此时，+0和-0的补码表示是相同的，也就是说，0的补码是唯一的。十进制数与补码的对应关系见表0.2.1。

从上表可以看出，一个字节能够存放从-128到127这个范围内的符号数，总计仍是256个值。

由以上分析可知，计算机是以补码的形式存放数据的。那么十进制数减法在机器里是如何运算的呢？

例0.2.1

计算机如何做33-15？

首先，我们做一个变换，即换成加法思路。

33-15=33+（-15）

这里33是正数，其原码、反码和补码都相同，33=001000012。

而-15是负数，-15=100011112，-15的原码是10001111。接着，符号位不变，对其他位取反（把0换为1，1换为0）得-15的反码为11110000。再将反码的最低位加1，得到-15补码为11110001。在计算机内，-15就表示为11110001。那么，

在结果之中舍去最前面位上的1（因为一个字节只能容纳8个二进制位），答案为000100102=18。这里的最前一位是0说明答案是非负的，此时它的原码、反码、补码是相同的。

例0.2.2

计算15-33。

首先要看成是15+（-33），将-33写成补码形式：11011110+1=11011111，于是

在结果11101110之中的最左边一位是1，这说明答案是负的。为了将负数的补码转换为十进制形式，要进行如下处理：补码的最高位不改动，其余各位取反，再加1，这样就得到负数的原码。对11101110来说，最高位不动，其他位取反，得10010001；再加上1，得原码10010010，因为000100102=18，所以结果是-18。

无论采用什么样的大小模式，可以表示的整数大小都是有限的。一旦超过这个大小，就会产生一个具有溢出错误的结果。比如，用一个字节表示下式的运算：

这里的左边一位是1，表明答案是负的。这说明在做两个正数的加法时，得出了一个负数，产生了一个溢出错误。在此，若用两个字节来表示，就不会出现溢出错误了。

在计算机中，表示集合的方式是多种多样的。一种办法是将集合的元素无序地存储起来。如果是这样，做集合的并、交、差等运算时会浪费许多时间，因为这些运算将需要大量的元素检索。另一种方法是将全集中的元素按某种顺序存放，这种方法比较容易计算集合的组合。

设全集U是有限的。首先给U中的元素规定一个顺序，例如U={a1，a2，…，an}。于是，可以用长度为n的位串表示U的子集A：如果ai∈A，则位串中的第i位是1；否则位串中的第i位是0。

如果要系统地表示给定的非空集合的子集，也可以采用一种被称为Gray码（Gray code）的编码方案（参见参考文献[5]第111页）。

例0.2.3

令U={1，2，3，4，5，6，7，8，9，10}，而且U的元素是从小到大排序的，也就是ai=i。下面用位串表示U中所有奇数的子集、所有偶数子集和不超过5的整数的子集。

表示U中所有奇数的子集{1，3，5，7，9}的位串，其第1，3，5，7，9位为1，其他位为0，即1010101010。

表示U中所有偶数的子集{2，4，6，8，10}的位串，其第2，4，6，8，10位为1，其他位为0，即0101010101。

表示U中不超过5的整数的子集{1，2，3，4，5}的位串为1111100000。

例0.2.4

接上题，如果集合B={1，3，5，7，9}的位串是1010101010，那么我们可以求集合B的补集的位串。

用0取代1，用1取代0，即可得0101010101，这对应着集合{2，4，6，8，10}。

计算机的信息一般用字位的组合来表示，每个字位有两个可能的值，即0或1。信息就是用0和1表示的字符序列或字位串。对字位可以进行一定的逻辑运算，这种字位运算对应于第2章所讨论的逻辑联结词，而对位串的运算也就是处理信息。为方便应用，列表于此，见表0.2.2。

注：符号∨为逻辑运算或，∧表示运算与。

例0.2.5

求位串0110110110和1100011101的按位或∨、位与∧进行的位运算。

解：

例0.2.6

令U={1，2，3，4，5，6，7，8，9，10}，集合A={1，2，3，4，5}和B={1，3，5，7，9}的位串分别是1111100000和1010101010，我们可以用位串找出它们的并集的位串：

1111100000∨1010101010=1111101010

它对应的集合是{1，2，3，4，5，7，9}。

它们的交集的位串：1111100000∧1010101010=1010100000，它对应的集合是{1，3，5}。

关于位运算的更多知识，读者可以参见参考文献[7]第255页。

习题0.2

1.写出下列各个十进制数的原码、反码和补码。

（1）11

（2）-23

（3）56

（4）-128

2.仿照前面的例题，运用补码表达7+6，7-6，-7+6的计算过程。

3.写一个算法，使它能从一个给定的二进制数的原码得到该数的补码。