4.乘除运算

4.1 整数乘法运算实现

高级语言里两个n位整数相乘得到的结果通常也是一个n位整数，即只取结果2n位里的低n位

int a,b,x;

x = a*b;

因此，C语言里，参加运算的两个操作数的类型和结果的类型应该一样，如果不一样则会先转换为一样的结果。

机器内部运算，$x^2 \ge 0$ 不一定成立。如果x是带符号整数不一定成立，如果是浮点数，那么成立。

#include <stdio.h>

typedef unsigned char   uint8_t;
typedef signed char     int8_t;

int main()
{
    int8_t m = 15;
    int8_t n = 10;

    int8_t k1 = m * n;

    printf("m*n: %d (%x %b)\n",k1,k1,k1);

    return 0;
}

输出结果为-106

只取了低8位作为结果，溢出了。

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

如何用程序判断一个乘法运算结果是否正确呢？!x || z/x == y，算出来还可以除回去，就说明这个运算结果是正确的。

编译器来判断的话，是看最高位是否为全0或1。

如果只用乘法只用低位的话，用补码作运算，有无符号数的运算在机器层次没什么不同，那么可以只用低位作为结果，只用一个无符号乘法器就行，但是这样的话就无法在编译器层次判断数据溢出了，只能在程序里判断是否溢出。

乘法器硬件不判断溢出，只是把结果存其来供软件使用，如果程序里不进行溢出判断，那么可能就会有一些溢出问题。

对于加减运算，不论有无符号，可以使用同样的指令，但是有无符号乘法的指令要分开。

乘法指令的操作数长度为n，乘积长度为2n。

溢出判断很重要，举个例子，程序的漏洞

int copy_array(int *array, int count)
{
    int i;
    int *myarray = (int*)malloc(count*sizeof(int));
    if (myarray == NULL)
        return -1;
    for (i = 0; i<count; i++)
        myarray[i] = array[i];
    return count;
}

如果count很大，那么count*sizeof(int)就会溢出，这会导致堆内存的数据被大量破坏，攻击者可以构造特殊的参数来触发整数溢出，用预设信息覆盖一个已分配的堆缓冲区，实现改变内存数据执行任意代码。

整数乘法运算比移位运算和加法运算用的时间长，需要很多时钟周期来实现。因此编译器处理常数和变量相乘的时候，往往用移位和加减法组合运算来实现的。如20*x

$20 \times x = (16 + 4) \times x = x << 4 + x << 2$

不管有无符号的乘法，就算是溢出了，两种运算的结果都是一样的。

整数除法实现

对于带符号整数，n位除以n位，只有 $- 2 ^{n-1} / -1 = 2 ^{n-1}$ 这种情况会发生溢出，对于其他情况，只会越除越小（绝对值），所以不会溢出。

整数除法的商也是整数，不能整除时需要舍入，向0方向舍入，是截断取整。

比如 $7/2=3$ ， $-7/2=-3$。

还有个特殊问题，整除0该怎么办，这个结果无法用机器数表示，会发生“异常”，会交给操作系统进行处理。

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

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

这两段代码，上面的会输出一个数，下面的会报错。这和编译器优化有关系，上面的优化成取反了，不存在溢出检测。

对于整数除法，比较复杂，无法用流水线方式实现，要根据试商的方式调整，需要几十个时钟周期，比乘法指令的时间还要长。

所以在写程序的时候，还是要避免这个事情。

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

• 无符号：逻辑右移

• 带符号：算术右移

结果一定时整数，如果移出去的全是0那么就可以整除，一出去的bit里有1，就需要相应的处理了。

无符号数和带符号正数，直接把移出去的丢掉就行。带符号负整数，要给机器码加偏移量 $2^k - 1$ 然后直接移动机器码就行。

举个例子，一个变量除以常数32，不可以使用乘法、乘法、模运算、比较运算、循环语句、条件语句：

对于带符号负数，$(x + 2^5 - 1)>>5$，

(x>=0 ? x : (x + 31)) >> 5

然而不可以用比较运算，那么就要考虑使用符号位构造31，带符号整数右移，补1，因此有这个程序：

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

根据符号确定是否偏移，然后右移代替除法。