计算机系统基础(一)笔记——Week4 乘除运算及浮点数运算

Week4 乘除运算及浮点数运算

4.1 整数乘法运算

通常，高级语言中两个n位整数相乘得到的结果通常也是n位整数，只取2n位乘积中的n位。

在计算机内部，一定有$x^2 \ge 0$吗？

$x$是带符号整数，不一定；浮点数则一定。

int mul(int x,int y)
{
    int z=x*y;
    return z;
}

• 可以通过!x || z/x==y来判断z是否正确

• 通过乘积的**高n+1位为全0或全1（不溢出）**来判断是否溢出

• 如果都改为unsigned，则高n位全0则不溢出

可以用无符号乘法器实现带符号乘法，不过不能判断溢出

PS：因为低n位相同

乘法指令不生成溢出标志，编译器可用2n位乘积来判断是否溢出

整数乘法漏洞

int copy_array(int *array,int count)
{
	int i;
	//在堆申请内存
	int *myarray=(int *)malloc(count*sizeof(int));
	//.....
}

当count=2^30+1时，count*sizeof(int)=2^32+4(mod 2^32)=4会发生溢出。

会造成堆中数据大量被破坏！

变量与常数之间运算

采用移位、加法和减法的组合运算代替乘法运算

x*20=(x<<4)+(x<<2)

4.2 整数除法运算

整数除运算

• 对于带符号整数，n位整数除以n位整数，除了$-2^{n-1}/-1=2^{n-1}$会发生溢出外，其余情况都不会溢出。

​ n位带符号整数最大只能表示$2^{n-1}-1$

​ 因为商的绝对值不会大于被除数的绝对值，因此不会发生溢出，也不会有溢出漏洞

• 不能整除时需要舍入，通常朝0方向舍入
• 整除0的结果无法用机器数表示

int a=0x80000000;
int b=a/-1;
printf("%d\n",b);//-2147483648

int a=0x80000000;
int b=-1;
int c=a/b;
printf("%d\n",c);//floating point exception

/-1被编译器优化成取负指令neg，因此没有溢出，但是结果错误。

变量与常数之间的除法运算

一次除法运算大致需要30个或更多个时钟周期，比乘法指令的时间还长

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

无符号：逻辑右移；

带符号：算数右移；

• 能整除时，直接右移

• 不能整除时，有1移出，要进行相应处理

  采用朝0舍入，即截断方式。

  • 无符号数、带符号正整数：直接截断

    14/4=3，0000 1110>>2=0000 0011

  • 带符号负整数：加偏移量$2^k-1$，再右移k位，低位截断（k是右移位数）

    -14/4=-3

    直接截断：1111 0010>>2=1111 1100=-4

    纠偏再右移：k=2,(-14+4-1)/4=-3

    1111 0010+0000 0011=1111 0101 >>2=1111 1101=-3

假设x为int型变量，给出计算x/32值得函数div32。只能用右移、加法和任何按位运算

int div32(int x)
{
    int b=(x>>31)&0x1F;
    return (x+b)>>5;
}

重点在如何计算偏移量b：b=0或b=31，可以右移31位得到32位符号，再取出最低5位就是偏移量b

4.3 浮点数运算

浮点数运算及结果

设两个规格化浮点数为$A=M_a\cdot 2^{E_a},B=M_b\cdot {2^{E_b}}$，则

$A+B=(M_a+M_b\cdot 2^{(E_a+E_b)})\cdot 2^{E_a},E_a>E_b$

$A\times B=(M_a+M_b)\cdot 2^{E_a+E_b}$

$A\div B=(M_a/M_b)\cdot 2^{E_a-E_b}$

可能发生如下情况：

1. 阶码上溢：正指数超过最大允许值
2. 阶码下溢：负指数超过最小允许值
3. 尾数溢出：最高有效位有进位（右规）

​ 1.5+1.5=3.0

4. 非规格化尾数：数值部分高位为0（左规）

   1.5-1.0=0.5

5. 右规或对阶时，右段有效位丢失（尾数舍入）

IEEE建议为每种异常情况提供自陷允许位，为1时调用异常处理程序执行

IEEE五种异常情况

• 无效运算

  • 有一个数是非有限数：$0\times \infty$
  • 结果无效：$0/0$

• 除以0

• 数太大（阶上溢）：E>1111 1110

• 数太小（阶下溢）：E<0000 0001

• 结果不精确：1/3、1/10不能精确表示

上述情况中硬件可以捕捉到，硬件处理时称为硬件陷阱

int a=1,b=0;
// 异常
double a=1.0,b=-1.0,c=0.0
// a/c=1.#INF00,b/c=-1.#INF00

浮点运算中，有限数除以0，结果为正/负无穷大

浮点数加减运算

• 对阶向阶大的看齐，阶小的尾数右移
• IEEE754位数右移时，将隐含的1移到小数部分，高位补0，移出的位保留在附加位上

步骤：求阶差、对阶、尾数加减、规格化、舍入、尾数为0阶码置0

规格化：

• 当尾数高位为0，左规：尾数左移一次，阶码减1，直到MSB为1

  每次阶码减1后，要判断阶码是否下溢（比最小可表示的阶码还小）

• 当尾数高位有进位，右规：尾数右移一次，阶码加1，直到MSB为1

​ 每次阶码加1后，要判断阶码是否上溢（比最大可表示的阶码还大）

舍入：尾数比规定位数长，有多种舍入方式

二进制浮点数计算0.5+(-0.4375)

$0.5=1.000\times 2^{-1},-0.4375=-1.110\times 2^{-2}$

对阶：$1.000\times 2^{-1}$

​ $0.111\times 2^{-1}$

加减：$0.001\times 2^{-1}$

左规：$1.000\times 2^{-4}=0.0625$

判溢出：无

附加位

加附加位能使尾数尽量长，保证精度

IEEE754要求中间结果须在右边加2个附加位（guard、round）

• guard：在significand右边的位
• round：在guard右边的位

用于保护对阶时右移的位或运算的中间结果

若十进制数有效位数为3

2.3400*10^2

0.0253*10^2

2.3653*10^2

若没有舍入位，采用就近舍入到偶数，则结果是2.36，没有2.37精度高

IEEE舍入标准：

• 就近（一般）

  比如，附加位01：舍，11：入，10：强迫为偶数

  1.1101 11==1.1110

  1.1101 01==1.1101

  1.1101 10==1.1110，剩下为奇数，+1

  1.1111 10==10.0000，剩下为奇数，+1

  已经为偶数直接舍

• 向正无穷

• 向负无穷

• 向0

float a=123456.789e4;
double b=123456.789e4;
printf("%f\n%f\n",a,b);
//1234567936.000000
//1234567890.000000

为什么float型会变大？

float可精确表示7个十进制有效数位，后面是舍入的结果，会更大也可能更小

C语言中的浮点数类型

float、double固定，格式不会变

long double类型取决于编译器和处理器

• 从int转float时，不会溢出，但数据可能会舍入（int31位有效数字转为float24有效数字）

• float或double转int，数据可能朝0截断

int x;
float f;
double d;
x==(int)(float) x;//false
x==(int)(double) x;//true
f==(float)(double) f;//true
d==(float)d;//false
f==-(-f);//true
2/3==2/3.0;//false
d*d>=0.0;//true
x*x>=0;//false
(d+f)-d==f;//false d过大会把f吃掉