二, 数据的表示和运算
(一) 数制与编码
1. 进位计数制及其相互转换 1)进位计数制
进位计数制是指按照进位制的方法表示数,不同的数制均涉及两个基本概念:基数和权. 基数:进位计数制中所拥有数字的个数.
权:每位数字的值等于数字乘以所在位数的相关常数,这个常数就是权. 任意一个R进制数X,设整数部分为n位,小数部分为m位,则X可表示为:
X＝an-1r + an-2r + ┅ + a0r + a-1r + a-2r+ ┅ + a-mr (X)r =
n-1
n-2
0
-1
-2
-m
i?n?1?Kri?mi
2)不同数制间的数据转换
(1)二,八,十六进制数转换成十进制数
利用上面讲到的公式: (N)2=∑Di?2i ,(N)8=∑Di?8i, (N)16=∑Di?16i,进行计算.
(2)十进制数转换成二进制数
通常要对一个数的整数部分和小数部分分别进行处理,各自得出结果后再合并. ? 对整数部分,一般采用除2取余数法,其规则如下:
将十进制数除以2,所得余数(0或1)即为对应二进制数最低位的值.然后对上次所得商除以2,所得余数即为二进制数次低位的值,如此进行下去,直到商等于0为止,最后得的余数是所求二进制数最高位的值. ? 对小数部分,一般用乘2取整数法,其规则如下:
将十进制数乘以2,所得乘积的整数部分即为对应二进制小数最高位的值,然后对所余数的小数部分部分乘以2,所得乘积的整数部分为次高位的值,如此进行下去,直到乘积的小数部分为0,或结果已满足所需精度要求为止.
(3)二进制数,八进制数和十六进制数之间的转换
八进制数和十六进制数是从二进制数演变而来的: 由3位二进制数组成1位八进制数; 由4位二进制数组成1位十六进制数.
对一个兼有整数和小数部分的数以小数点为界,小数点前后的数分别分组进行处理,不足的位数用0补足. 对整数部分将0补在数的左侧,对小数部分将0补在数的右侧.这样数值不会发生差错. 2. 真值和机器数
真值:数据的数值通常以正(+)负(-)号后跟绝对值来表示,称之为“真值”.
机器数:在计算机中正负号也需要数字化,一般用0表示正号,1表示负号.把符号数字化的数成为机器数. 3. BCD码(Binary Coded Decimal以二进制编码的十进制码)
在计算机中采用4位二进制码对每个十进制数位进行编码.4位二进制码有16种不同的组合,从中选出10种来表示十进制数位的0～9,用0000,0001,…,1001分别表示0,1,…,9,每个数位内部满足二进制规则,而数位之间满足十进制规则,故称这种编码为“以二进制编码的十进制(binary coded decima1,简称BCD)码”.
在计算机内部实现BCD码算术运算,要对运算结果进行修正,对加法运算的修正规则是: 如果两个一位BCD码相加之和小于或等于(1001)2,即(9)10,不需要修正;
如相加之和大于或等于(1010)2,或者产生进位,要进行加6修正,如果有进位,要向高位进位.
4. 字符与字符串
在计算机中要对字符进行识别和处理,必须通过编码的方法,按照一定的规则将字符用一组二进制数编码表示.字符的编码方式有多种,常见的编码有ASCII码,EBCDIC码等.
1)ASCII码(American Standard Code for Information Interchange 美国信息交换标准码)
ASCII码用7位二进制表示一个字符,总共128个字符元素,包括10个十进制数字(0-9),52个英文字母(A-Z和a-z),34专用符号和32控制符号.
2)EBCDIC码为Extended Binary Coded Decimal Interchange Code的简称,它采用8位来表示一个字符. 3)字符串的存放
向量存储法:字符串存储时,字符串中的所有元素在物理上是邻接的.
串表存储法:字符串的每个字符代码后面设置一个链接字,用于指出下一个字符的存储单元的地址. 5. 校验码Check Digit
数据校验码是一种常用的带有发现某些错误或自动改错能力的数据编码方法.其实现原理,是加进一些冗余码,使合法数据编码出现某些错误时,就成为非法编码.
这样,可以通过检测编码的合法性来达到发现错误的目的.合理地安排非法编码数量和编码规则,可以提高发现错误的能力,或达到自动改正错误的目的.
码距:码距根据任意两个合法码之间至少有几个二进制位不相同而确定的,仅有一位不同,称其码距为1. 1)奇偶校验码(Parity Bit)WIKI
(开销最小,能发现数据代码中一位出错情况的编码,常用于存储器读写检查或ASCII字符或其它类型的信息传输的检查)P216
它的实现原理,是使码距由1增加到2.若编码中有1位二进制数出错了,即由1变成0,或者由0变成1.这样出错的编码就成为非法编码,就可以知道出现了错误.在原有的编码之上再增加一位校验位,原编码n位,形成新的编码为n+1 位.增加的方法有2种:
奇校验:增加位的0或1要保证整个编码中1的个数为奇数个. 偶校验:增加位的0或1要保证整个编码中1的个数为偶数个. 2)海明校验码(Hamming Code)P100
实现原理,在数据中加入几个校验位,并把数据的每一个二进制位分配在几个奇偶校验组中.当某一位出错就会引起有关的几个校验组的值发生变化,这不但可以发现出错,还能指出是哪一位出错,为自动纠错提供了依据. 假设校验位的个数为r,则它能表示2r个信息,用其中的一个信息指出“没有错误”,其余2r-1个信息指出错误发生在哪一位.然而错误也可能发生在校验位,因此只有
k=2r-1-r个信息能用于纠正被传送数据的位数,也就是说要满足关系:
2rk+r+1
3)CRC校验码(Cyclic Redundancy Check 循环冗余校验)P144
CRC校验码一般是指k位信息之后拼接r位校验码.关键问题是如何从k位信息方便地得到r位校验码,以如何从位k+r信息码判断是否出错.
将带编码的k位有效信息位组表达为多项式: 式Ci中为0或1.
若将信息位左移r位,则可表示为多项式M(x).xr.这样就可以空出r位,以便拼接r位校验位.
CRC码是用多项式M(x).xr除以生成多项式G(x)所得的余数作为校验码的.为了得到r位余数,G(x)必须是r+1位.
设所得的余数表达式为R(x),商为Q(x).将余数拼接在信息位组左移r位空出的r位上,就构成了CRC码,这个码的可用多项式表达为:
M(x)·xr+R(x)=[Q(x)·G(x)+R(x)]+R(x) =[Q(x)·G(x)]+[R(x)+R(x)] =Q(x)·G(x)
因此,所得CRC码可被G(x)表示的数码除尽.
将收到的CRC码用约定的生成多项式G(x)去除,如果无错,余数应为0,有某一位出错,余数不为0. (二) 定点数的表示和运算 1. 定点数的表示 1)无符号数的表示
无符号数就是指正整数,机器字长的全部位数均用来表示数值的大小,相当于数的绝对值. 对于字长为n+1位的无符号数的表示范围为: 0-1 2)带符号数的表示 (真值范围-n-1n)
带符号数是指在计算机中将数的符号数码化.在计算机中,一般规定二进制的最高位为符号位,最高位为“0”表示该数为正,为“1”表示该数为负.这种在机器中使用符号位也被数码化的数称为机器数. 根据符号位和数值位的编码方法不同,机器数分为原码,补码和反码.
(1)原码表示法
机器数的最高位为符号位,0表示正数,1表示负数,数值跟随其后,并以绝对值形式给出.这是与真值最接近的一种表示形式.
原码的定义:
(2)补码表示法
机器数的最高位为符号位,0表示正数,1表示负数,其定义如下:
(3)反码表示法
机器数的最高位为符号,0表示正数,1表示负数.反码的定义:
整数 小数 0 移码 =0.0000 (mod 2) =1.0000 =0.0000 负数原码求反+1 移码表示中零也是唯一的 原码 (mod ) (mod(2-=0.0000负数每位求反 )) =1.1111 补码 (mod(反码 )) 真值的移码和补码仅差一个符号位.若将补码的符号位由0改为1或从1改为0即可得到真值的移码 乘法运算可用移码和加法来实现,两个n位数相乘,总共要进行n次加法运算和n次移位运算 三种机器数的特点可以归纳为： ·三种机器数的最高位均为符号位.符号位和数值位之间可用“.”(对于小数)或“,”(对于整数)隔开 ·当真值为正时,原码,补码和反码的表示形式均相同,即符号位用“0”表示,数值部分与真值部分相同
·当真值为负时,原码,补码和反码的表示形式不同,其它符号位都用“1”表示,而数值部分有这样的关系,即补码是原码的“求反加1”,反码是原码的“每位求反”. 2. 定点数的运算 1)定点数的位移运算
左移,绝对值扩大;右移,绝对值缩小. 算术移位规则 符号位不变 码制 添补代码 正数 0 原 0 右移添0 负数 补 左移添1 反 1 算术移位和逻辑移位的区别: 算术移位:带符号数移位; 逻辑移位:无符号数移位; 2)原码定点数的加/减运算;
对原码表示的两个操作数进行加减运算时,计算机的实际操作是加还是减,不仅取决指令中的操作码,还取决于两个操作数的符号.而且运算结果的符号判断也较复杂.
例如,加法指令指示做(＋A)＋(－B)由于一操作数为负,实际操作是做减法(＋A)-(+B),结果符号与绝对值大的符号相同.同理,在减法指令中指示做(＋A)－(－B)实际操作做加法(＋A)＋(＋B),结果与被减数符号相同.由于原码加减法比较繁琐,相应地需要由复杂的硬件逻辑才能实现,因此在计算机中很少被采用. 3)补码定点数的加/减运算; (1) 加法
整数 [A]补 + [B]补= [A+B]补(mod 2n+1)
小数 [A]补 + [B]补= [A+B]补(mod 2) (2) 减法
整数 [A]补 - [B]补= [A+(-B)]补=[A]补 + [-B]补(mod 2n+1) 小数 [A]补 - [B]补= [A+(-B)]补=[A]补 + [-B]补(mod 2)
无需符号判定,连同符号位一起相加,符号位产生的进位自然丢掉
4)定点数的乘/除运算 (1)一位乘法
<1>原码定点一位乘法
两个原码数相乘,其乘积的符号为相乘两数的异或值,数值两数绝对值之积. 设 [X]原=X0 X1 X2 …Xn
[Y]原=Y0 Y1 Y2 …Yn
[X·Y]原=[X]原·[Y]原= (X0⊕Y0)∣(X1 X2 …Xn)·(Y1 Y2 …Yn) 符号∣表示把符号位和数值邻接起来.
原码两位乘和原码一位乘比较 原码一位乘 原码两位乘 符号位 操作数 绝对值 绝对值的补码 移位 逻辑右移 算术右移 移位次数 n 最多加法次数 n <2>定点补码一位乘法 有的机器为方便加减法运算,数据以补码形式存放.乘法直接用补码进行,减少转换次数.具体规则如下: [X·Y]补=[X]补(－Y0 + 0. Y1 Y2… Yn )
<3>布斯法