数据编码和数据运算

第二章数据编码和数据运算两个基本要素权赋予每一数位的位值，也称位权。weight基数相邻二位高位权与低位权的比值。radix任意进制数的表示法：对于数N有x=±∑xiRin-1i=-m（小数点前n位，小数点后m位）R基数xi0-(R-1)任意一数i位数；小数点前位正，后为负。为n-1,n-2,,,3,2,1,0.1,-2,-3，，-m等式左边：任意进制数等式右边：同值十进制和式•进位计数制例：•十进制数：R=10，xi为0,1,2,···,9各位权103,102,101,100,10-1,10-2,10-3•二进制:R=2，xi为0,1；各位权为23,22,21,20,2-1,2-2常用进位制符号：B（二进制），O或Q（八进制）H（十六进制），D（十进制）例：将二进制数1101011010分别用十进制，八进制和十六进制表示。1101011010B=1×29+1×28+1×26+1×24+1×23+1×21=858D1101011010B=1532Q1101011010B=35AH对于二进制x可写成x=xn…x2x1x0.x-1x-2…x-mxi={0,1},-m≤i≤nn+1位二进制整数x的两种排序x=xn…x2x1x0x=x0x1x2…xn(本课程采用）•计算机中数据格式1.定点格式2.浮点格式2.1定点数的编码和运算•定点数：小数点位置固定不变的数–定点整数：小数点定在最低位数的右面–定点小数：小数点固定在最高位数的后面，即纯小数表示2.1.1无符号数的编码•定点整数数值表示：x=x0x1x2…xnxi={0,1},0≤i≤nx02n+x12n-1+…+xn-121+xn数值范围•0≤x≤2n+1-1•例如:x=010101其数值=24+22+20=21•定点小数数值表示x=x0.x1x2…xnx0=0,xi={0,1},0≤i≤nx12-1+…+xn-12-n+1+xn2-n数值范围0≤x≤1-2-n例如：x=0.10101其数值=2-1+2-3+2-5=21/322.1.2有符号定点数的编码机器数：二进制数最高位表示符号，‘1’为‘-’，‘0’为‘+’。后面各位为数值（绝对值）。真值：带符号机器数对应的数值。例：真值机器数N1-100110011001100N2+101001101010011⒈原码n+1位二进制数原码定义[x]原码=x0≤x2n2n-x-2nx≤0⒉反码N+1位二进制数反码定义[x]反码=x0≤x2n（2n+1–1）+x-2nx≤0⒊补码n位二进制数补码定义[x]补码=x0≤x2n2n+1+x-2n≤x≤0•原码，反码，补码n+1位中最高位为符号位，后n位为X数值。原码形式与机器数相同。•对于定点小数的原码、补码、反码，只要把上述定义式中的2n用1代替，1用2-n即代替即可可。∵2n+1-1=11···111（n+1个1）∴2n+1-1+x正好为x（x为负）例：[-1101101]反码=10010010111111110110110110010010•[x]反码与[x]补码的关系0≤x2n-1[x]补码=[x]反码-2n-1x≤0[x]补码=2n+x=[x]反码+14移码对于n+1位定点整数x[x]移=2n+x2nx≥2-nx：真值，[x]移：机器数•常用于表示浮点数的阶码，便于比较大小•移码中符号位与原码、补码和反码相反•计算机中移码只执行加减运算•原码，反码，补码二进制数表示数值范围真值十进制原码反码补码移码+1111111+12701111111011111110111111111111111+0000001+100000001000000010000000110000001+0000000+000000000000000000000000010000000-0000000-010000000111111110000000010000000-0000001-110000001111111101111111101111111-1111111-12711111111100000001000000100000001-10000000-1281000000000000000对于+0和-0，原码和反码都有两种形式，而补码的表示形式相同，所以补码表示的数比原码和反码要多1个数。对于n+1位二进制，该数为-2n，故补码表示范围为：2n-1-2n。㈤补码运算计算机中带符号数运算一律用补码运算，其运算结果也用补码表示。对于带符号数x，y下列公式成立：[x]补+[y]补=[x+y]补(1)[x]补+[-y]补=[x-y]补(2)[-y]补求法：①用补码定义式求②[-y]补=[[y]补]变补即先求出[y]补，后将[y]补连同符号位求反加1即可。例2-1设x=1010，y=-1010，求[x]补和[y]补。•解：根据补码的编码方法，正数的补码与它的二进制表示相同，所以加上符号位0后得[x]补=01010•根据补码的编码方法，负数的补码的数值部分等于它的二进制位按位取反后在最低位上加1，符号位取反后为1，所以[y]补=10110定点小数的补码编码•x=x0.x1…xn•方法与定点整数的编码方式类似•最高位x0作为符号位•数值范围：-1≤x≤1-2-n•例设x=0.1010，y=-0.1010，则[x]补=0.1010，[y]补=1.0110移码与补码的关系编码与数值的关系2.1.3数据的存储与访问•数据类型–整型数、单精度和双精度浮点数、字符型•数据长度–单字节、双字节、字、双字、四倍字•字节存储顺序–大数端(bigEndian)和小数端(littleEndian)。地址4567数据000F4240(a)大数端存储方式地址4567数据40420F00数据的存储方式•对齐的方式•非对齐的方式。字节地址……161612128844003210(b)字对齐(a)字不对齐……………………字节地址3201定点数的加减运算例子例2-4x=0.1010，y=-0.0011，用补码的加法求x+y。解：[x]补=0.1010，[y]补=1.1101[x]补+[y]补=0.1010+1.1101=0.0111x+y=0.0111例2-5x=0.1001，y=-0.0011，用补码的减法求x-y。解：[x]补=0.1001，[y]补=1.1101，[-y]补=0.0011[x]补-[y]补=[x]补+[-y]补=0.1001+0.0011=0.1100x-y=0.1100加减运算电路ba取反进位输入进位输出FAr10进位输出Cr0r1溢出V取反r31a31b31a1b1b0a0cfbcfcf数据溢出及其检测方法一——符号位判断V=x0y0z0+x0y0z0判断电路FAVz0y0x0判断电路01101001+0011001010011011X0=0，Y0=0，Z0=1，第二项为1，V=1,有溢出。方法二——双符号位判断（变形码）V=z0'z0+z'0z0=z0'z000.xxxx11.xxxx+00.xxxx或+111.xxxx00.xxxx11.xxxx判断电路FAFAVc’0z’0c1c0z0x’0y’0y0x0Z0⊕Z1=0⊕1=1，有溢出。001101001+000110010010011011方法三——判断符号位与最高数值位V=C0C1+C0C1判断电路FAFAz1z0Vc1c0y1x1y0x001101001+0011001010011011C0⊕C1=1有溢出避免数据的溢出的方法•增加数据的表示位数•例如数据6–在8位的计算机中表示为00000110，–在16位计算机中表示为0000000000000110。•例如用补码表示-2时–在8位计算机中是11111110，–在16位计算机中是1111111111111110。•符号扩展数据溢出的概念与数据取模时的丢弃•数据运算中最高位的进位被丢弃并不一定是溢出•例如，两个负数的补码相加，设x=-0110，即-610；y=-0101，即-510。则[x]补=11010，[y]补=11011。[x+y]补=10101(mod25)，即-1110运算结果正确，没有发生溢出习题•教材第66页第7题2.1.5定点数的乘除运算0010×00110010001000000000000011010101010102222NMkkkMiNjjijiNjjjMiiizyxyxYXZ•二进制乘法采用原码乘法•将符号位与数值位分开进行运算•运算结果的数值部分是乘数和被乘数数值位的乘积•运算结果的符号位是乘数和被乘数符号位的异或HAX0X1X2X3X0X1X2X3Y3Y2Z7Z6Z5Z4Z3Z2Z1Z0Y1Y0X0X1X2X3FAFAHAFAFAHAFAFAHAFAFAX3X2X1X04×4无符号阵列乘法电路X4Y4Z8进位保留乘法器HAX0X1X2X3X0X1X2X3Y3Y2Z7Z6Z5Z4Z3Z2Z1Z0Y1Y0X0X0X1X1X2X2X3X3HAHAHAFAFAFAHAFAFAHAFAFAFAFAHA进位加法器CSAXY0XY1XY2XY3CSACSA•二进制除法1101100010011010110100100001101000111•恢复余数法–通过减法实现，不够减时再用加法恢复原来的部分余数。•加减交替法–除数每一步运算所得的余数ri=2ri-1-y。–当ri0时，ri+1=2ri-y，上商1。–如果ri0，上商0，并加y，然后左移一位，再做减y运算，得到ri+1，即ri+1=2(ri+y)-y=2ri+y。比较被除数（或部分余数）和除数大小的方法实现加减交替法的电路000r3r4r5r61y3y2x6x5x4x3x2x100y1q1q3q2y0FAFAFAFAFAFAFAFAFAFAFAFAFAFAFAFA10011010111111001011001111-补码+1001011000111001101011111-补码+不够减：够减：2.2浮点数的编码和运算构成：阶码E，尾数M，符号位S，基数RN=(-1)S×M×RESEM任意进制浮点数：二进制浮点数的编码•规格化：为了在尾数中表示最多的有效数据位为了数据表示的唯一性。•机器零：全部为0，特殊的数据编码N=(-1)S×2E×MM为数N的尾数E为数据N的阶二进制浮点数的规格化≤M112要满足上式，必须使小数点后的第一位为1。规格化的编码•原码–数据位的最高位为1•补码–小数点前后两位互不相同。–例如，尾数0.1010和1.0101是规格化的，而尾数0.0101和1.1010是非规格化的。•基数为2的浮点数规格化后，其尾数的绝对值在1/2到1之间•基数为R的浮点数规格化后，其尾数的绝对值在1/R到1之间。1xxxxxx特点浮点数的表示范围•浮点数的溢出表现为阶码的溢出•浮点数的上溢(overflow)–数据太大，以至于大于阶码所能表示的数据•浮点数的下溢(underflow)–数据太小，以至于小于阶码所能表示的数值时，负上溢负下溢正下溢正上溢图2-2浮点数的表示范围-+负数正数0浮点数标准(IEEE754)•三种格式：短实数、长实数、临时实数（表2.1）•规格化数：(-1)s×1.f×2e-127•非规格化数：(-1)s×0.f×2e-126IEEE754浮点数单精度格式sef3130232201.规格化数：0e255，V=(-1)S╳(2)e-127╳1.f2.+0，-0：e=0且f=0，则V=(-1)S╳03.DMRM(非规格化数）：e=0且f≠0，则V=DMRM4.+∞，-∞正负无穷大：e=255且f=0，则V=(-1)S╳∞5.NaN（无定义数）：e=255且f≠0，则V=NaNIEEE754浮点数双精度格式sef6362525101.规格化数：0e2047，V=(-1)S╳(2)e-1023╳1.f2.+0，-0：e=0且f=0，则V=(-1)S╳03.DMRM(非规格化数）：e=0且f≠0