数据的机器级表示与处理

数据表示基础

进位计数制

十进制：符号数多，运算组合状态过多

二进制：符号数最少，可以表示任何对象，运算规则简单

r进制转10进制：按权展开

10进制转r进制：整数部分除2取余，小数部分乘2取整

进制转换的快速方法

大数转换方法：记住常用的2的幂

2的7，8，10（1k)，15，16，20(1m)，30(1g)次方都很常用

例：

相应地，2进制转10进制也可以：

二进制转2^m进制：m位一分组，小数部分不足位数要补零凑足

地址和虚拟地址空间

多数计算机使用8位的字节作为最小的可寻址存储单元

机器级程序把存储器看成一个非常大的字节数组，成为虚拟存储器

存储器为每一个字节都编了一个唯一的地址，所有可能的地址集合被称为虚拟地址空间

每个计算机都有一个字长，用来指明整数，指针数据的标称大小

字长为n-bit时，范围是0-2^n-1

如32位字节长度的计算机，虚拟地址空间的大小是2^32bit,也就是4GB

除了比特和字节外，还常用字来作为数据表示的单位，表示被处理信息的单位，用来度量数据类型的宽度

注意：字不是字长，字和字长的宽度可以一样，也可以不同

字长等于cpu内部总线的宽度，运算器的位数，通用寄存器的宽度等

寻址和字节顺序

通常，多字节对象被存储为连续的字节序列，地址是所有字节里最小的地址

字节排列顺序：

如：

相应地，大端法时，数据为0x01234567，可以看出，大端法和我们的习惯读法一样

存放方式不同的机器间程序移植时，需要进行顺序转换，音视频图像等文件格式或处理程序也都涉及到字节顺序，如gif是大端法，jpeg是小端法

同一数据类型在不同位数计算机中可能会占不同的位数：可移植性变差

解决可移植性问题：typedef或另类的整数类型：

数据容量的度量单位

注意：通信里的带宽和容量的单位换算不同！

整数表示

补码

对于补码，直接再求一次该补码的补码就是这个数的原码

快速求解法：对于负数的补码，从右往左，第一个1保留，其余各位按位取反，得到的就是该补码绝对值的二进制表示

如补码110110：

所以这个数的绝对值是10，这个数是-10

整数运算实现

c语言的位运算

按位与&，按位或|，按位取反~，按位异或^

可以用在任意的整型数据上

用途：对位串实现掩码（用于提取某些位的集合）操作，实现对多媒体数据或状态/控制信息进行处理等

巧用还可以实现提高程序性能

移位运算：向左或向右按位移动n位，空位补零或补符

用途：提取部分信息，扩大或缩小数值的2，4，8……倍，左移相当于扩大，右移相当于缩小

无符号数：高位移出的是1，则左移时发生溢出

有符号数：移出的位不等于新的符号位时，则溢出

左移：x<<y

右移：x>>y

c并不区分是逻辑移位还是算术移位（底层如何判断是哪种移位？由x的数据类型决定）

位扩展和位截断运算

c语言内没有专门的运算符，但编译器会根据转换前后数据的长短来确定是扩展还是截断

扩展：短转长

无符号数：0扩展，前面补0

有符号整数：符号扩展，前面补符

截断：长转短

强行将高位丢弃，保留低位，所以可能发生溢出

整数加减运算实现

回顾数电：串行加法器采用串行逐级传递进位，电路延迟与位数成正比关系，速度慢

并行进位加法器速度很快，但是连线多，所需驱动大

所以可以分组，组内并行，组间串行，也可以并行级联

n位加法器只能用于两个n位二进制数相加，不能进行无符号数的减运算，也不能进行有符号数的加/减运算，必须在它的基础上增加其他的逻辑门电路，使得它不但能计算和/差，还能生成标志信息（判溢出和生成条件码）

条件标志(Flag):在运算电路中产生，用于溢出判断或条件判断的位信息，通常被记录到专门的寄存器中（程序/状态字寄存器或标志寄存器，如IA-32中的EFLAGS寄存器）

我们只学4个标志信息：OF,SF,ZF,CF

标志	SF	ZF	OF	CF
标志种类	符号标志	零标志	溢出标志	进位/借位标志
值	SF=Fn-1	ZF=1当且仅当F=0	OF=Cn异或Cn-1	CF=Cout异或Cin

溢出标志OF只是有符号数的溢出标志，无符号数的溢出标志看进位/借位标志CF

即有符号溢出OF=1,无符号溢出CF=1（机器级语言中判断，即汇编中）

高级语言溢出判断：无法获得标志位，必须通过程序进行判断，即有符号数正正得负或负负得正的时候说明出现溢出，无符号数的和数小于加数时出现溢出

出现溢出时的加法运算公式：

整数大小比较时用减法，规则：

无符号数比较：CF=0时，表示大于关系

有符号数比较：OF=SF时，表示大于关系

ALU的设计原理及构成

ALU：进行基本算术运算与逻辑运算，包括整数加减运算（不包括浮点数和乘除），与，或，非，左移右移等逻辑运算，核心电路是整数加减运算部件，输出除了和/差等，还有标志信息

ALU的构成：需要一个操作控制端(ALUop)来决定ALU所执行的处理功能，ALUop的位数k决定操作的种类（2的k次方）

整数的乘除运算实现

乘法运算规则

两个n位整数相乘所得的乘机应该有2n位，但是高级语言里经常2个n位整数相乘，结果赋给一个n位整数，即只取2n位乘积里的低n位

这样会造成乘法溢出漏洞

乘法指令分无符号整数乘和有符号整数乘两种，实现时有区别：

即输出结果的低n位是相等的

无符号乘法运算直接正常乘即可

有符号乘法运算：布斯乘法

步骤：先改造乘数，再做二进制乘法运算（被乘数不需要改造）

当乘上-1的时候，相当于就是求被乘数的补码，如10110100乘-1变成了01001100，高位处则是符号扩展，即乘1/-1的结果的最高位是0就补0，是1就补1

乘法溢出判断

无符号数：高n位不全为0即溢出

有符号数：高n位全是0或全是1，且和低n位的最高（符号）位相等时不溢出，否则溢出

高级语言判溢出：!x||z/x==y的真假

变量与常数之间的乘运算

往往以移位，加减法来代替

不管是无符号数还是有符号数，即使乘积溢出时，利用移位和加减运算组合的方式得到的结果都是和采用直接相乘的结果是一样的

整数除运算

溢出和异常情况：

1.除数为0时，会发生异常，此时需要调出操作系统中的异常处理程序来处理

2.最小负数除以-1

不同原因：编译优化问题，直接除以-1被优化成取负指令neg，所以没有发生除法溢出

整数除法商也是整数，在不能整除时必须进行舍入，通常朝0方向舍入

除运算在处理一个变量和一个2的幂次形式的整数相除时，常采用右移运算来实现：

无符号：逻辑右移

有符号：算术右移

但是不能整除的时候，无法实现朝0舍入

如-14/4=-3，但直接截断来右移时结果则是-4

所以遇到不能整除的负整数时应先纠偏，再右移

如-14/4，要右移2位，k=2，（-14+2^k-1）/4=-3

浮点数表示

用科学计数法表示实数：IEEE754标准，用尾数和幂来表示

float型：

double型：

符号位——-阶码———尾数码

尾数码直接把小数点后的数字放到尾数码位置即可，后面补0，如1.01的尾数码是0100000……

阶码：需要移码操作，阶码=指数原码+偏置常数Bias(为了防止负指数带来的计算上的麻烦)，**取原码表示**

float的Bias是127（2^(8-1)-1)

double的Bias是1023 (2^(11-1)-1)

以float型为例对IEEE754浮点数的解释：

阶码	尾数码	表示
1-254	f	规格化数
255	0/≠0	正负无穷/非数NaN
0	0/≠0	机器数0/非规格化数

规格化数定义：小数点左侧有且仅有一个1

10进制真值到单精度表示转换：

1.将小数点左右的部分分别转为2进制

2.转成规格化数表示

3.对号入座，求符号码，阶码，尾数码

4.化为16进制（如果题目要求）

单精度表示到10进制真值转换

反过来即可，先根据符号码阶码尾数码求规格化数表示，再将2进制转10进制

（别忘了阶码要减去偏置常数才是指数）

规格化数表示范围

（以float为例）

由于规格化数阶码是1-254

所以最小最大分别为：

阶码相差1时，由于尾数有23位，所以两个阶码中间有2^23个状态（或者间隔），即从1.0…0到1.1…1（小数点后23位）

如2^-126和2^-125中间的间隔为2^-126/2^23=2^-149,也就是这个区间里相邻两个可表示数相差的距离是2^-149

随着数值增大，相邻两个可表示数相差的距离也增大，在数轴上也更加稀疏，也就更加不准确

阶码为255时

1.尾数全为0时表示正负无穷

注意：浮点数运算中，除数为0时结果是正负无穷而不是溢出异常

2.尾数不为0时表示NaN

阶码为0时

1.尾数全为0时表示正0负0

2.尾数不全为0时表示非规格化数

0和1.00……0*2^-126中间有较大的间隔（和往右边的2^-149相比），可以用非规格化数表示，此时间隔也是2^-149

浮点数运算

和乘除相比，加减比较复杂（因为是科学计数法的加减）

1.在进行尾数加减前，必须进行“对阶”，小阶向大阶看齐，小阶的数字在尾数右移的时候，要把隐含的“1”移到小数部分，高位补0，也就是变成0.1xxx……，移出的低位保留到特定的附加位上

如10进制加法，这就是一个对阶的例子：

但是最后只能保留3位小数，所以还得考虑舍入，要把结果先规格化，再判溢出

规格化（判溢出）：

当尾数高位为0，则需左规：尾数左移一次，阶码-1，直到MSB为1，每次阶码-1后要判断阶码是否下溢，若阶码-1后为全0，则结果为非规格化数，此时应使尾数结果不变，阶码为全0

当尾数最高位有进位，则需右规：尾数右移一次，阶码+1，直到MSB为1，每次阶码+1后要判断阶码是否上溢，若阶码+1后为全1，则发生“阶码上溢”（有的机器会将结果置为正负无穷），IEEE754加减运算尾数最多需要右规1次

右规或对阶时，右端有效位丢失=>尾数舍入

为了减少误差，需要在后面加附加位，形如这里的y：

IEEE754规定：中间结果须在右边加2个附加位，分别是保护位和舍入位

附加位作用：保护对阶时右移的位或运算的中间结果

附加位的处理：1.左规时被移到阶码 2.作为舍入的依据

2位附加位：舍入位的作用就是告诉计算机在进行舍入时应该如何进行，以保证结果的精度和正确性。

IEEE754的舍入：