计组笔记(一)——计算机中的数据表示

计算机系统中的数据表示

数据编码

进制转换

    其他->十进制 按权展开 十进制->其他 整数部分:除基取余,先低后高 小数部分:乘基取整,先高后低 二进制->八进制 整数部分:从右往左,3位一组,不够3位最左边补0 小数部分:从左往右,3位一组,不够3位最右边补0 二进制->十六进制 和八进制一样,4位一组

补码的性质

补码与原码、真值的相互转换

    补码=模+真值,即[X]补=M+X 如果X>0,那么模就会作为超出部分被舍去,此时[X]补=X,所以正数的补码就是其本身; 如果X<0,那么[X]补就是X以M为模的补数。比如M=12,X=-3,那么[X]补=M+X=12-3=9。 真值,原码,补码之间的相互转换 如果X>0,那么真值=原码=补码 如果X<0: 写出绝对值|X|的原码,按位取反,末位加一 写出绝对值|X|的原码,从右往左,第一个1以及其右边的各位0保持不变,以左的各位按位取反。 要注意的是原码不能表示-1。 课堂例题: 机器字长为8,求X=-0.1101100的原码以及补码。 分析:X<0,原码为1.1101100,补码为0.1101100按位取反末尾加一,即1.0010011+0.0000001=1.0010100。 或按照方法2,将0.1101100倒数第三位以右不变,以左按位取反即得到:1.0010100 课堂例题: 分析:四个选项中,X的值不变,关键是看y和z的值。 y为short型,则字长为16,-9的绝对值9的原码是0000 0000 0000 1001,末位1不变,以左按位取反得到-9的补码:1111 1111 1111 0110,选项中为16进制,则4个二进制数为1组,即FFF7。排除AB。 执行赋值语句z=x+y,先将16位的y转换为32位,即FFFFFFF7,则x+y=0000 007F + FFFF FFF7,F表示151,15+7位22,22-16等于6,则末位为6,向前进1…一次类推,即可得到选项D。 或者直接用排除法,127-9是个正数,它的补码的符号位一定是0,选项C排除。所以选D。 另外,H表示这数字是十六进制数。为了区别不同数制表示的数,通常用右括号下标数字或字母表示数制,十进制数用D表示,二进制用B表示,十六进制数用H表示,八进制用O表示。
* 课堂例题

分析:unsigned表示无符号,var1和var2都是16位2进制,其中var1是有符号整数,那么就要用补码表示。-32767的绝对值|-32767|=32768-1,表示成16位二进制即:1000 0000 0000 0000 - 1=0111 1111 1111 1111,最后一位1不变,其余按位取反得-32767的补码,即:1000 0000 0000 0001,将这个数直接赋值给无符号数var2,即:32768+1=32769,选D。

补码的符号位扩展

纯小数扩展:低位补0;

纯整数扩展:高位补符号位的数。(符号位是1,高位补1,符号位是0,高位补0)

补码的算数右移(除2运算)

结论:符号位不变,按位右移1位(与符号位的扩展类似,也可以理解为:右移后高位补符号位)

例:[X1]补=0.1101010,[X2]补=1.0100110

则 [ 1 2 X 1 ] 补 [frac{1}{2}X_1]_补 [21X1]补=0.0110101, [ 1 2 X 2 ] 补 [frac{1}{2}X_2]_补 [21X2]补=1.1010011

补码的算数左移(乘2运算)

结论:按位左移1位,末位补0。

如何判断是否溢出?

如果算数左移后,符号位上的数字发生变化,则说明溢出。实际做题时,只需要比较最高位和次高位两个数是否相同即可,如果相同,则说明算数左移一位后不会溢出,否则溢出。比如1.0010110,乘以2,即算数左移一位,就会发生溢出,因为最高位是1,次高位是0,二者不相等。

变形补码

为了便于判断补码运算时是否溢出,采用变形补码。

变形补码,即采用双符号位,左符为真正的符号位,右符用来判断是是否溢出。

判断方法:运算结果中两个符号位数值相同,则没有溢出,不相同则溢出。

比如要对1.0010110进行左移1位运算,先将其变成双符号位,即给高位再添一个符号位:11.0010110,然后进行左移,得10.01001100

,双符号位上的两个数1和0不相等,则溢出。注意,双符号位只是用来判别运算结果是否溢出,写实际结果时要去掉多加的一个符号位。

反码的性质

    最高位为符号位,0表示正,1表示负 反码也要两个0,[+0]反=0000…000,[-0]反=1111…111 表示数的范围和原码一样: 纯小数:-(1-2-(n-1))到+(1-2-(n-1)) 纯整数:-(2n-1-1)到+(2n-1-1) 反码与原码以及真值之间的转换 当X>=0时,反码=原码=真值 当X<0时,真值的符号位取反,数值位不变,得原码;原码的符号位不变,数值位取反,得反码。 反码按位取反,再加负号得真值。 反码=补码+1

移码的性质

    用途:移码常用来表示浮点数的阶码(纯整数) 移码的定义:[X]移=2n-1+X,即偏移量+真值 移码表示的范围:-2n-1<=X<2n-1(和补码相同,负数多表示一个) 最高位为符号位,0表示负数,1表示正数(和原码、补码、反码相反) 移码中的0是唯一的,即2n-1:10000000…000(n-1个0) X越大,[X]移越大,二者呈线性正比关系。 移码和补码的相互转换:符号位取反,数值位不变 课堂例题
  1. 16进制为00,那么二进制就是0000 0000。 0000 0000的符号位是0,当作补码、原码、反码看时,这是一个正数,分别表示0,+0,+0; 当作移码看时,我们知道,移码的数和真值之间是线性正比关系,0000 0000表示的是能用移码表示的最小的那个数,就是-128。
  2. 16进制为80,那么二进制就是1000 0000。 1000 0000当作补码看,符号位是1,负数,先写 -,然后1及其右边的0不变,左边取反,即1000 0000,那么表示的真值就是 -1000 0000,即-128; 1000 0000当作原码看,符号位是1,负数,数值位是0,那么表示的真值就是:-0; 1000 0000当作反码看,符号位是1,负数,先写-,按位取反,即0111 1111,表示的真值是 -0111 1111,即-127; 1000 0000当作移码看,符号位取反的对应的补码,即 0000 0000,相应的表示的真值就是0,1000 0000其实就是移码的偏移量。
  3. 16进制为FF,那么二进制就是1111 1111。 1111 1111当作补码看,符号位是1,负数,先减1,得1111 1110,再按位取反的真值的绝对值的原码:0000 0001,对应的真值就是-0000 0001,即-1; 1111 1111当作原码看,符号位是1,负数,对应的真值就是 -0111 1111,即-127; 1111 1111当作反码看,符号位是1,负数,先写-,按位取反,即0000 0000 ,表示的真值就是 -0000 0000,即-0。

各编码的表示范围

    原码 整数:-(2n-1-1)~+(2n-1-1) 小数:-(1-2-(n-1))~+(1-2-(n-1)) 补码 整数:-2n-1~+(2n-1-1),负方向比原码多表示一个数 小数:-1~+(1-2-(n-1)),负方向比原码多表示-1(1.000…000) 反码:和原码一致 移码:只有整数部分,和补码的范围一致

各编码之间的转换

    X是整数,那么X可以用移码表示,移码的表示范围和补码一样,补码符号位取反,数值位不变得移码。 除了移码以外,原码、补码、反码,符号位为1永远表示负数,为0永远表示正数 X>0,真值=原码=补码=反码 X<0 真值到原码:去掉负号,最高位取反(或置1)的原码 真值到补码1:去掉负号,按位取反,末位加一; 真值到补码2:去掉负号,从右往左,第一个1以及其右边的各位0保持不变,以左的各位按位取反。 补码到真值:先写负号,从右往左,第一个1以及其右边的各位0保持不变,以左的各位按位取反。 原码到补码1:符号位不变,其余各位按位取反,末位加一; 原码到补码2:符号位不变,从右往左,第一个1以及其右边的各位0保持不变,以左的各位按位取反。 原码到反码:符号位不变,其余各位按位取反 补码到反码:末位减一 真值到反码:去掉符号,其余各位按位取反

定点与浮点的表示

浮点数的表示

浮点数的规格化

阶码一般用移码表示,尾数可用原码或者补码表示。尾数决定精度,阶码决定范围。

尾数的规格化表示

    尾数用原码表示 规格化的浮点数是指尾数的格式应该是:x.1xxxxxxx,表示的范围:1/2≤|M|<1 尾数用原码表示时,判断是否规格化:即数值位的第一位必须是1。 尾数用补码表示 尾数M≥0,尾数应具有格式:M=0.1xxx…x,表示的范围[1/2]补 ≤ [M]补<[1]补 尾数M<0,尾数应具有格式:M=1.0xxx…x,表示的范围[-1]补 ≤ [M]补<[-1/2]补 即当尾数小于0时,为了使计算机判断方便,一般不把[-1/2]补列为规格化的数,而把[-1]补列为规格化的数。 尾数用补码表示时,判断是否规格化:看符号位和数值位第一位是否相等,若不相等就是规格化,否则不是规格化。 这种判断方法用一个异或电路就可以实现,非常方便。 左归与右归(假设尾数用双符号位的补码表示) 左归:当运算结果尾数为非规格化尾数时,即11.1xxx或00.0xxx,尾数数值位左移n位,阶码-n,直到尾数规格化为止 ,同时判断阶码是否下溢。 右归:当运算结果尾数发生溢出时,即10.xxxx或01.xxxx,尾数右移n位,阶码+n,直到尾数规格化为止,同时判断阶码是否上溢。 举例,比如当尾数用原码表示时,1.0011001 × 25不是规格化的尾数,需要左移2位,实际手动运算时符号位不要动,数值位往左移2位,末位添0,同时阶码-2,得1.1100100 × 23,左归后表示的真值没有发生变化,且尾数已经规格化。 又比如,经过运算后浮点数用双符号位表示 为10.0101101× 25,如果是定点数,这个双符号位不相同,表示溢出。但这是浮点数,并没有溢出,只需要规格化,尾数整体右移1位的 1.0010110,末位的1舍去,同时阶数+1,得1.0010110× 26 溢出判断 看阶码是否超出表示范围。 课堂例题-1

分析:阶码用移码表示时范围和补码一样,题中阶码为6位,即 -25~25-1,即-32~+31,尾数用补码和用原码表示时,必须是规格化的,二者表示的范围也是不一样的,如下图:

有了尾数和阶码各自的表示范围,两两组合即可解题:
  1. 最大正数
  2. 最小正数
  3. 最大负数
  4. 最小负数 本题是16位浮点数,将上面得到的区间画在数轴上,同时用另一个坐标轴画出16位定点补码整数,可见,浮点数的表示范围要远远大于纯整数:
    课堂例题-2

IEEE-754

注意事项:

  1. 尾数用原码表示,小数点前隐含一个1
  2. 阶码用移码表示,偏移量规定为0111…1111,即2n-1-1,而不是移码的一般偏移量:1000…0000,即2n-1,两者之间差一个1。
  3. 阶码的最大值(全1)作为特殊标记: 阶码全为1,尾数符号位是0,数值位全为0,则表示正无穷; 阶码全为1,尾数符号位是1,数值位全为0,则表示负无穷; 阶码全为1,尾数的数值位不是全0,则全部表示非数NaN。
  4. 阶码的最小值(全0)作为特殊标记: 阶码全为0,尾数符号位是0,数值位全为0,则表示机器零(+0); 阶码全为0,尾数符号位是1,数值位全为0,则表示机器零(-0); 阶码全为0,尾数的数值位不全是0,则表示非规格化的数。如果是单精度,阶数统一规定为-126(0000 0001),如果是双精度,阶数统一规定为-1022(0000 0000 01)
  5. 单精度共32位,阶码占8位,表示范围是-126~+127;尾数占24位,数值位为23位,由于隐含一个1,所以实际表示24位; 双进度共64位,阶码占11位,表示范围是-1022~+1024;尾数占53位,数值位为52位,由于隐含一个1,所以实际表示53位;
    课堂例题 分析: 全0表示机器0,+0 0 100 0010 0 100 0000 0000 0000 0000 0000,尾数的符号位是0,表示一个正数,阶码是1000 0100,根据移码的定义,[X]移=偏移量+X,IEEE-754规定的阶码的偏移量是0111 1111,那么真值X=1000 0100-0111 1111=1000 0100-1000 0000+0000 0001=0000 0101,即+5,尾数的数值部分是1000…000,加上隐含的1,即1.1000…000,那么该单精度数值表示数就是+1.1000…000×2+5=11000.00…00,即48 1 000 0000 0 100 0000 0000 0000 0000 0000,阶码是特殊标记全0,但是尾数又不全是0,那么就表示非规格化的数,前面不隐含1,而是隐含0,那么尾数表示的就是-0.100…00,非规格化的数的单精度浮点数,其阶数统一为-126,那么表示的数就是 − 0.1 × 2 − 126 = − 2 − 127 -0.1×2^{-126}=-2^{-127} −0.1×2−126=−2−127 1 111 1111 1 000 0000 0000 0000 0000 0000,阶码是特殊标记全1,尾数的数值位是全0,符号位是1,表示负无穷。 IEEE-754中的阶码用移码表示,偏移量规定为01111…111,如何计算对应的真值? 拿单精度的浮点数来说,它的阶码的偏移量规定为0111 1111,即127,按照移码的定义,[X]移=偏移量+X来计算 标准移码的偏移量是1000 0000,即128,比IEEE-754中的偏移量多1。这也就意味着,同一个真值,标准移码=754移码+1。按照我们之前的方法,标准移码和其真值的补码是符号位取反的关系。所以知道IEEE754的移码,先+1得到标准移码,再符号位取反即可得到真值的补码;相应的,如果知道真值,先计算其补码,然后符号位取反得到标准移码,再-1得到IEEE754移码。即: 已知真值,求IEE-754标准短浮点数(32位)的方法 写出X的二进制形式 规格化 写出符号位,扩展尾数、阶码对应的754移码(真值的补码符号位取反再-1) 按照符号位1位、阶码8位、尾数23位的格式写出。 课堂例题

分析:先写出-8.25的二进制形式,即-1000.01,写成规格化的单精度浮点型即:-1.00001×23,阶码是3,尾数是-1.00001。

知道阶码的真值3,求IEEE754对应的移码,先写出3的原码,即0000 0011,这也是3的补码,按照标准移码的转换方式,符号位取反的标准移码1000 0011,再-1得IEEE754移码的1000 0010,尾数的符号位是1,数值位是1.00001,那么得到的IEEE754单精度数值就是:

1 1000 0010 0000 1000 …0000,转化为16进制就是C104 0000。

本题测试程序:

    单精度浮点数测试程序

BCD码

非数值数据的编码

检错与纠错码

奇偶校验码

特点:只能检查1位错误,且不能纠正。

奇校验:保证数据(包括奇校验位在内)的n+1位数中,1的个数是奇数;

偶校验:保证数据(包括奇校验位在内)的n+1位数中,1的个数是偶数;

二维奇偶校验可以检查1、2、3位错误,可以纠正1位错误。

    例题

循环冗余校验码

用2代替X,得到1011。 2.G是1011,总共是4位,所以在F低位添3个0,F=1001010000

3.计算F÷G,计算时采用的是模2的减法,即不借位(可以理解为按位异或),凑够4位且高位是1就可以理解为够除。最后得3位余数(因为G是4位,所以余数必须凑够三位,不够的话高位补0)。

4.将这3位余数放在F后,则得到要发送的值。那么这个值会被G按照同样的方法整除。

即余数是000表示数据正确,数据不为0,则表示出错,且采用合适的G可以指明错误。

该例子中F有7位,余数是3位,除去000表示正确,其余7中组合没有办法纠错10位数据,只能检查部分错误。

如果数据位是4位,那么刚好可以完全纠错。

    CRC使用场合:适合突发性错误,光盘、磁盘、网络通信。 对于随机性错误,适合用海明码。

海明码

    多少位的校验码可以发现并纠错1位错误(公式记住)
m:数据位可能出错的位数

r:校验位可能出错的位数

1:全部正确

是4位,所以余数必须凑够三位,不够的话高位补0)。

4.将这3位余数放在F后,则得到要发送的值。那么这个值会被G按照同样的方法整除。

即余数是000表示数据正确,数据不为0,则表示出错,且采用合适的G可以指明错误。

该例子中F有7位,余数是3位,除去000表示正确,其余7中组合没有办法纠错10位数据,只能检查部分错误。

如果数据位是4位,那么刚好可以完全纠错。

    CRC使用场合:适合突发性错误,光盘、磁盘、网络通信。 对于随机性错误,适合用海明码。

海明码

    多少位的校验码可以发现并纠错1位错误(公式记住)

m:数据位可能出错的位数

r:校验位可能出错的位数

1:全部正确

经验分享 程序员 微信小程序 职场和发展