第第3章章运算方法运算方法和运算部件和运算部件上海大学计算机学院3.1.1 数据的表示方法和转换1、进位计数制进位计数制：用少量的数字符号（也称数码），按先后次序把它们排成数位，由低到高进行计数，计满进位，这样的方法称为进位计数制基数：进位制的基本特征数，即所用到的数字符号个数。例如10进制：09十个数码表示，基数为10权：每个数字符号所表示的数值等于该数字符号乘以一个与数码所在位有关的常数，该常数称为权常见的进位制：2，8，10，16进制不同数制的表示方法以十进制为例：基数:10;符号:0,1,2,3,4,5,6,7,8,9(N)10= Dm10m + Dm-110m-1+ D1101 + D0100+D-110-1 +D-210-2 + D-k10-k = Di 10i 这里整数部分有m+1位，小数部分有k位，基数为10，权为10i以二进制为例：基数:2符号:0,1计算规律:逢二进一或借一当二二进制的多项式表示:N2= dm 2m + dm-1 2m-1 + dm-2 2m-2 + d1 21 + d0 20 + d-1 2-1 + d-2 2-2 + d-n 2-n其中m+1为整数位数；n为小数位数。Di表示第i位的系数,2i称为该位的权. 注意：8和16进制自学不同数制间的数据转换3.1.1 数据的表示方法和转换二进制数、八进制数、十六进制数间的转换八进制和十六进制是从二进制演变而来从二进制数转换到八进制数或十六进制数由3位二进制组成1位八进制，4位二进制组成1位十六进制从八进制数或十六进制数转换到二进制数顺序将每一位写成3位或4位即可(位数不足补0，以小数点为界：整数补左面，小数补右面)例3.4(1101.0101)2=（001101.010100)2=(15.24)8例3.5(1 1101.0101)2=（00011101.0101)2=(1D.5)16例3.6(15.24)8=(001 101.010 100)2=(1101.0101)2练习请将一个8位2进制整数转换成，8进制，16进制，并检查是否正确如果是小数呢？3.1.1 数据的表示方法和转换十进制转二进制对于整数和小数部分分别处理，各自得出结果后在合并。整数部分：除2取余法将（105）2转换成二进制得出： （105）10 = （1101001）2练习请将一个2位10进制整数转换成2进制，8进制，16进制，并检查是否正确3.1.1 数据的表示方法和转换十进制转二进制对于整数和小数部分分别处理，各自得出结果后在合并。小数部分：乘2取整法例如:将(0.8125) 10 转换成二进制小数（4位有效数字）. 整数部分2 0.8125=1.625 12 0.625=1.25 12 0.25=0.5 02 0.5=1 1(0.8125) 10 =(0.1101) 2练习请将一个2位10进制小数转换成2进制，8进制，16进制（3位有效数字），并检查是否正确3.1.1 数据的表示方法和转换十进制转任意进制方法：整数部分用除基数（2，8或16）取余数法，小数部分用乘基数（2，8或16）取整数法任意进制转十进制用按权展开即可得十进制数的表示3.1.2 十进制的编码与运算十进制数位的编码与运算计算机中采用4位二进制码（码容量为16）对每个十进制数位进行编码，用10种来表示09，基于不同的选择策略，有多种方案有权码无权码.3.1.2 十进制的编码与运算有权码2*1+4*1+2*1+1*1=93.1.2 十进制的编码与运算BCD码的运算如果两个一位BCD码相加之和小于或等于(1001)2，则不需要修正；否则加6修正，并向高位进位例:5+3=8 7+8=15 8+9=17 010101111000+0011+1000+10011000111110001+0110+01101010110111向高位进位+6修正3.1.2 十进制的编码与运算无权码3.1.2 十进制的编码与运算无权码的运算(以余3码为例)当两个余3码相加不产生进位时，从结果中减去0011；否则，将进位信号送入高位，本位加0011例3.11 (28)10+(55)10=(83)10 01011011(28)10+)1000 11000(55)10 11100011低位向高位进位-) 0011 +)0011低位+3，高位-3 101101103.1.2 十进制的编码与运算数字串在计算机内的表示与存储数字串在计算机内的表示与存储主要形式主要形式字符形式字符形式l-即一个字节存放一个十进制数位或符号位，即一个字节存放一个十进制数位或符号位，存放的是存放的是09十个数字和正负号的十个数字和正负号的ASCll编码值编码值（P301页）。例如，页）。例如，123的编码为的编码为2B313233，占用，占用4个连续的字节，这里的个连续的字节，这里的2B，31，32和和33是用是用十六进制形式给出的编码，十六进制形式给出的编码，2B表示正号，表示正号，31，32和和33分别表示数字分别表示数字1，2和和3。一。一123在主存中为在主存中为2D313233，其中，其中2D为负号。为负号。压缩的十进制数形式压缩的十进制数形式-即一个字节存放一个十进制数即一个字节存放一个十进制数位位,符号位放在最低数字位后，例如符号位放在最低数字位后，例如+123表示成表示成123B（共（共2个字节）个字节）3.2 带符号的二进制数据的加减运算原码、补码、反码及其加减运算原码表示法原码的定义： X原=X0X11- -X=1+|X|- -1X0即 X原=符号位+|X|+0原=00000， - 0原=10000所谓原码就是即最高位为符号位，“0”表示正，“1”表示负，其余位是数值的绝对值。方法1方法2练习写出3位2进制整数（其中第一位是符号位）所有原码和对应的10进制数3.2 带符号的二进制数据的加减运算反码表示法反码的定义：X反=X反=(2-2-n)符号位+X (mod 2 - 2-n )，其中n为小数点后的有效位数。+0反=0.0000，-0反=1.1111X0X12- -2n+X- -1X0方法1方法2正数的反码与其原码相同；负数的反码是对其原码逐位取反，但符号位不变。 练习写出3位2进制整数（其中第一位是符号位）所有反码和对应的10进制数3.2 带符号的二进制数据的加减运算补码表示法补码的定义：X补=即X补=2符号位+X（mod 2）当X=+0.0000时，X补=0.0000当X=-0.0000时，X补=2+X=10.0000-0.0000=10.0000=0.0000 mod 2因此，+0补=-0补=0.0000X0X12+X=2- -|X|- -1X0方法1方法2正数的补码与其原码相同；负数的补码是在其反码的末位加1。 练习写出3位2进制整数（其中第一位是符号位）所有补码和对应的10进制数小数呢？练习X补=0.1010，则X原=?X反=0.1010，则X原=?X补=1.1010，则X原=?X反=1.1010，则X原=?模的概念：把一个计量单位称之为模或模数。例如，时钟是以12进制进行计数循环的，加2和减10的效果是一样的；因此，在以12为模的系统中，凡是减10的运算都可以用加2来代替，这就把减法问题转化成加法问题了. 11-10=1 -10+12=2 （11+2）mod 12=13 mod 12 =1 计算机的运算部件与寄存器都有一定字长的限制（假设字长为8），因此它的运算也是一种模运算。当计数器计满8位也就是256个数后会产生溢出，又从头开始计数。产生溢出的量就是计数器的模，显然，8位二进制数，它的模数256。在计算中，两个互补的数称为“补码”。 50-40=10 （50+216）mod 256=266 mod 256 =10 (40)10= 00101000 (216)10=11011000 =(100000000)=2563.2 带符号的二进制数据的加减运算补码运算的几个重要结论用补码表示的两数进行加法运算，其结果仍为补码X+Y补=X补+ Y补（条件：结果不超过示数范围）符号位与数值位一样参与运算取反加取反加1 1 例题P 74 3.14-3.193.2 带符号的二进制数据的加减运算数据以补码和反码表示形式转换成原码反码转换成原码符号位保持不变，正数的数值部分保持不变，负数的数值部分取反补码转换成原码符号位保持不变，正数的数值部分保持不变，负数的数值部分取反加1练习X=0.0011，Y=0.1110，则X+Y补=？，X-Y补=？X=-0.1110，Y=0.0011，则X+Y补=？，X-Y补=？3.2 带符号的二进制数据的加减运算整数的表示形式原码：原码：X原=补码：补码：X补=反码：反码：X反=X 0X 2n2n-X= 2n+|X| - 2n X 0 X 0X 2n2n+1 + X= 2n+1 - |X| - 2n X0 X 0X 2n(2n+1-1)+X - 2n X 0 加减法运算的溢出处理当运算结果超出机器数所能表示的范围时，称为溢出。仅当两个同号数相加或异号数相减同号数相加或异号数相减时，才可能发生溢出。例如：（4位2进制情况下）12+7=19（溢出）(- 12)+(- 17)=- 19（溢出） 01100+) 00111 10011 10100+) 11001 1011013.2 带符号的二进制数据的加减运算3.2 带符号的二进制数据的加减运算溢出的判别（1）当符号相同的两数相加时，如果结果的符号与加数（或被加数）不相同，则为溢出。 溢出条件： fafbfs 分别表示被、加、结果符号位fAfBfS+ fAfBfSfSfAfBfSfAfB（2）当任意符号两数相加时，如果C=Cf，运算结果正确，其中C为数值最高位的进位，Cf为为符号位进位。如果CCf，则为溢出。溢出条件CCf。CCf+CCfCCfCfCC：最高位进位 Cf：符号位进位3.2 带符号的二进制数据的加减运算3.2 带符号的二进制数据的加减运算（3）采用双符号位fs1fs2。正数的符号位为00，负数的双符号位为11。符号位参与运算，当结果的两个符号位fs1和fs2不相同时，为溢出。溢出条件=fs1 fs2，或者溢出条件=fs1 fs2+fs1 fs2。fs1 fs2+ fs1 fs2fs1fs2fs2fs13.2 带符号的二进制数据的加减运算定点数和浮点数定点数：小数点固定在某个位置上的数据，一般有小数和整数两种表示形式。浮点数：小数点位置可浮动的数据。 N=M RE其中： N为浮点数，M为尾数，E为阶码为阶码，R为阶的基数(底)3.2 带符号的二进制数据的加减运算浮点数的规格化形式常用的浮点数的两种形式：单精度浮点数（32位），阶码8位，尾数24位（内含1位符号位）双精度符号位（64位），阶码11位，尾数53位（内含1位符号位）MsEM1位 n+1位m 位Ms是尾数的符号位E是阶码M是尾数3.2 带符号的二进制数据的加减运算移码的定义X移=2n+X - 2n X 2n把补码符号位取反即得移码把补码符号位取反即得移码移码具有以下特点：最高位为符号位，1表示正号，0表示负号在计算机中，移码（阶码）只执行加减法运算，且需要对得到的结果加以修正，修正量为2n，即要对结果的符号位取反数据0有唯一的编码3.2 带符号的二进制数据的加减运算数据的数值范围和精度数值范围：机器所能表示的一个数的最大值和最小值的范围。数据精度：一个数的有效范围。例如：32位定点小数（补码）的范围为：-1=x=1-2-31，-1定点整数（补码）的范围为-231 +2311，数据精度为31位32位单精度数的数值范围为：-2127127 +(1-2-23-23)2127127，数据精度为24位注意：单精度浮点数（32位），阶码8位，尾数24位（内含1位符号位）3.3 二进制乘法运算定点数一位乘法定点原码一位乘法规则：两个原码数相乘，其乘积的规则：两个原码数相乘，其乘积的符号符号为相乘两数为相乘两数的异或值，的异或值，数值数值为两数绝对值之积。为两数绝对值之积。假设：X原=X0X1X2XnY原=Y0Y1Y2Yn则：X Y= X原 Y原=(X0Y0)|(X1X2Xn) (Y1Y2Yn)0.1101(x)0.1011(y)+11011101000011010.10001111(z)设设x=0.1011，y=0.1101,让我们先用习惯方法让我们先用习惯方法求其乘积，其过程如下：求其乘积，其过程如下：2个4位数字相乘后是8位，如何存储？P82 图3.5“移位”和“+”3.3 二进制乘法运算例3.31X=0.1101，Y=0.1011，计算乘积XY解：解：部分积部分积乘数乘数0000000000001011011 1+X001101 001101右移一位右移一位 00011011011（丢失）丢失）+X001101010011 右移一位右移一位 00100111101（丢失）丢失）+0+0000000001001 右移一位右移一位 00010011110（丢失）丢失）+X001101 010001010001右移一位右移一位 0010001110010001111 111（丢失）（丢失）+0(+0(整数位，不是符号位整数位，不是符号位)乘积高位乘积高位乘积乘积低位低位XY=0.100011111111，乘积符号，乘积符号= =XY=00=0，乘积为正数。乘积为正数。演示练习X=-0.1001，Y=-0.1011用定点原码一位乘法求X*Y.3.3 二进制乘法运算二、定点补码一位乘法1、补码与真值的转换关系 设设X补补=X0.X1X2Xn， 当真值X0时， X0=0， 当真值X0时， X0=1，X补=1.X1X2Xn=2+X 得出对X为正负数都合适的公式如下：X0=0或1，是符号位3.3 二进制乘法运算2、补码的右移：不论数的正负，不论数的正负，连同符号位将数右移连同符号位将数右移一位并保一位并保持符号位不变，相当于乘持符号位不变，相当于乘1/2（或除（或除2）。 3.3 二进制乘法运算3、补码一位乘法设被乘数X补= X0.X1X2Xn，乘数Y补= Y0.Y1Y2Yn，则有：3.3 二进制乘法运算定点补码一位乘法法则X*Y若若Y为正数，则按照定点原码一位乘法的方法为正数，则按照定点原码一位乘法的方法计算计算X补补* *Y补补若若Y为负数，则先按照定点原码一位乘法的方为负数，则先按照定点原码一位乘法的方法计算法计算X补补* *Y补补，然后再加上，然后再加上-X补补3.3 二进制乘法运算例：设X=-0.1101，Y=0.1011，即X补=11.0011， Y补=0.1011，求XY补解：计算过程如下：P 85 页3.34 自学（Y是负数）练习X=-0.1001，Y=-0.1011用定点补码一位乘法求X*Y.布斯（Both）公式运算规则：运算规则：(1) 如果yi yi+1=00或11，部分积加0，再右移一位；(2) 如果yi yi+1= 01，部分积加 x 补，再右移一位；(3) 如果yi yi+1= 10，部分积加 - x补，再右移一位；就是后一位大就+ x 补x=0.1101， y=0.1011，用补码一位乘法用补码一位乘法计算计算 xy=？xy补补=0.10001111演示练习X=0.1011，Y=-0.1101用定点补码一位乘法求【X*Y】补.3.4 二进制除法运算定点原码一位除法两个原码数相除，其商的符号为两数符号的异或值，数值为两数绝对值相除后的结果。(1)恢复余数法(2)加减交替法人工计算方法011011101)101101101100101101101001101余数0111计算：0.1011/0.1101(1)恢复余数法例：假设X=0.1011，Y=0.1101，求X/Y解：-Y补=11.0011，取双符号位，-Y用+-Y补取代(1)恢复余数法(2)加减交替法原理：当某次求得的差值（余数Ri）为负时，不是恢复它，而是继续求下一位商，但是用加上除数（+Y）的办法来取代（-Y）操作，其它操作不变。(P93页)(2)加减交替法法则当余数为正时，商上1，余数左移一位，减去除数当余数为负时，商上0，余数左移一位，加上除数 (Ri+1=2Ri+Y)(2)加减交替法3.5 浮点数的运算浮点数的加减法运算浮点数：N=M RE X=Mx REx Y=My REy“对阶对阶”操作操作向大阶看齐向大阶看齐尾数加尾数加/ /减运算减运算 规格化操作规格化操作将结果用科学计数法表示将结果用科学计数法表示舍入舍入四舍五入？四舍五入？检查阶码是否溢出检查阶码是否溢出规格化浮点数运算流程求阶差：E=|EX-EY|保留大阶：E=max (EX，EY )对阶：小阶尾数右移E位尾数加减：M(MX)(MY)尾数加减结果判断右规：尾数右移一位，E+1左规：尾数左移K位，E-K*全“0”舍入规格化数M溢出溢出右规：M右移一位，E+1结果阶码判断不溢出置机器零E=-max M=0结果X Y正常上溢溢出置上溢标志出错XY不溢出对阶尾数加减规格化舍入判溢出结果3.6 运算部件定点运算部件由算术逻辑运算部件ALU、若干个寄存器、移位电路、计数器、门电路等组成浮点运算部件通常由阶码运算部件和尾数运算部件组成3.7 数据校验码数据校验码：一种常用的带有发现某些错误或自动改错能力的数据编码方法。目的：及时发现读写、存取和传送过程中的错误实现原理：加进一些冗余码，使合法数据编码出现某些错误时，就成为非法编码。码距：是根据任意两个合法码之间至少有几个二进制位不相同而确定的，仅有一位不同，称其码距为1。一、奇偶校验码开销最小1、原理 统计出一段数据中1的个数是奇数还是偶数，如若1位出错就能够发现，用于数据传送。 奇校验一段数据中“1”的个数为奇数，则奇校验位=0正常；一段数据中“1”的个数为偶数，则奇校验位=1 偶校验与奇校验相反3.7 数据校验码原数据增加校验位后数据携带校验位后数据原数据发送端接收端校验3.7 数据校验码2、不足：只能发现一位错或奇数个位错，不能确定哪 一位错，也不能发现偶数个位错(奇校验)3、将码距由1增加到24、校验过程二、循环冗余校验(CRC)码CRC的编码方法可以发现并纠正信息存储或传送中连续出现的多位错误在k位信息码之后拼接r位校验码CRC编码中用到的运算加减异或模2乘法模2除法二、循环冗余校验(CRC)码K位有效信息M(x)生成多项式G(x) (r+1位)M(x) xr 除以G(x)所得的余数为R(x)，商为Q(x)R(x)对应于校验码CRC码：M(x) xr+R(x)=Q(x) G(x)+R(x)+R(x) =Q(x) G(x)所以CRC码可被G(x)表示的数码除尽CRC编码方法：原数据的多项式表达：10010011M(x)=C7x7+ C6x6+ C5x5+ C4x4+ C3x3+ C2x2+ C1x1+ C0已知:原数据为多项式M(x);给定生成多项式G(x) 位r+1位,则有r 位校验位。则有： M(x) *xr R(x)余数 G(x) Q(x) 商 CRC码：码：M(x)*xr +R(x)例：原数据1100，给定G(x) =1011，求进行CRC编码后的数据 编码过程： M(x)=1100= 1x3+1x2+0x1+0x0=x3+x2 G(x) =1011= 1x3+ 0x2+ 1x+1= x3+x+1，因此得出r=3 M(x)*xr =1100*1000=1100000 M(x) *xr 1100000 010 全程模2操作 G(x) 1011 1011 CRC:1100010 =Q(x)+= =1110+ 练习设信息码是101101，生成多项式G(x)=x+1，则CRC校验码为多少？