CSAPP 第二章 整数运算

CSAPP 第二章 整数运算

整数运算也分为两种,无符号整数和有符号整数。 无符号加减法 无符号就是简单将两个二进制位相加。但是结果存在溢出的问题,即结果无法放到字长的限制中去。 如果字长是w,则无符号数最大就是2的w次方减1,这就导致如果两个数的和如果到达2的w次方,结果实际上就少了2的w次方。比如字长为4,1001+1001

整数运算也分为两种,无符号整数和有符号整数。

无符号加减法

无符号就是简单将两个二进制位相加。但是结果存在溢出的问题,即结果无法放到字长的限制中去。 如果字长是w,则无符号数最大就是2的w次方减1,这就导致如果两个数的和如果到达2的w次方,结果实际上就少了2的w次方。比如字长为4,1001+1001,结果实际上是10010 - 10000 = 10。十进制来看就是9+9 = 9+9-16 = 2,结果里少了2的四次方。 检测无符号数加法的溢出,就是先让直接加起来两个数字,由于默认会丢掉最高位。所以取剩下的部分作为结果,再和任何一个加数比较,如果结果小于加数就发生了溢出。因此可以写一个判断程序:

2.27 判断是否溢出。

int uadd_ok(unsigned x, unsigned y){
    unsigned result = x + y;
    return result >= x;
}
减法就是对无符号数求反再加。对无符号数求反,就是简单的用2的字长次方减去无符号数,就可以得到结果

2.28 无符号数求反

x 对x按4字长取反
十六进制 十进制 十进制 十六进制
0 0 0 0
5 5 2的四次方-5 = 11 B
8 8 2的四次方-8 = 8 8
D 13 2的四次方-13 = 3 3
F 15 2的四次方-15 = 1 1

补码加减法

补码加法的核心是,在底层的操作与无符号数是一样的。只是解释不同。 所以溢出存在,但是方向不同。由于无符号的溢出位置不影响原本的字长数,而补码中,实际的字长少了一位有效数字。 所以存在正溢出和负溢出。用两个大的int数相加,结果的最高位如果是1,溢出到了符号位,就变成负数,相当于从结果中减去2的字长次方。 反过来如果两个很大的负数相加,会发生负溢出,结果实际上被加上了2的字长次方。先来看正溢出的情况
int main()
{
    //4d7c6d00
    int i = 1300000000;

    show_bytes((byte_pointer) &i, sizeof(int));

    //59682f00
    int j = 1500000000;

    show_bytes((byte_pointer) &j, sizeof(int));

    //a6e49c00
    int sum = i + j;

    show_bytes((byte_pointer) &sum, sizeof(int));

    printf("%d + %d = %d\n", i, j, sum);
}
结果是1300000000 + 1500000000 = -1494967296,这个结果等于2800000000 - 4294967296(2的32次方) 负溢出的情况是:
int main()
{
    //4d7c6d00
    int i = -1300000000;

    show_bytes((byte_pointer) &i, sizeof(int));

    //59682f00
    int j = -1500000000;

    show_bytes((byte_pointer) &j, sizeof(int));

    //a6e49c00
    int sum = i + j;

    show_bytes((byte_pointer) &sum, sizeof(int));

    printf("%d + %d = %d\n", i, j, sum);
}
结果是-1300000000 + -1500000000 = 1494967296,很显然,结果是-2800000000 + 4294967296 检测补码溢出的方式是检测两个加数和结果,如果两个加数都大于0且和小于0,发生正溢出;两个加数都小于0且和大于0,发生负溢出。

2.29 补码的和

x y x+y 整数和 x+y 补码和 情况
10100 10001 -27 5 负溢出
11000 11000 -16 -16 没有溢出
10111 01000 -1 -1 没有溢出
00010 00101 7 7 没有溢出
01100 00100 16 -16 正溢出

2.30 检测是否补码加法是否溢出的函数,直接按照判断标准写即可:

int tadd_ok(int x, int y){
    int result = x + y;
    return !(!(x > 0 && y > 0 && result <= 0) || (x < 0 && y < 0 && result >= 0));
}

2.31 代码纠错

int tadd_ok(int x, int y){
    int sum = x + y;
    return (sum - x == y) && (sum - y == x);
}
这个的关键在于sum之后的结果再减去x是否可以得到y。由于补码是一个循环的阿贝尔群,无论是否溢出,sum-x==y和sum-y==x永远返回true。所以这个函数的结果永远是true,也就起不到判断的作用。

2.32 代码纠错

用这个函数去判断x-y是否溢出可以吗?
int tsub_o(int x, int y){
    return tadd_ok(x, -y);
}
看到减号就要想到补码的正负数不是一一对应的这个问题。在y等于int的下限的时候,-y就会出问题,依然和y相等,虽然从补码的底层逻辑来看是正确的,但从整数的角度来看,逻辑是错误的。 写这个函数的正确版本首先要区分y的取值范围。-2147483647=<y<=2147483647的时候,可以调用tadd_ok函数,但在y等于最小值的时候,直接通过判断x而不是y来返回结果。
int tsub_o(int x, int y){
    if (y >= -2147483647) {
        return tadd_ok(x, -y);
    } else {
        return x < 0;
    }
}
测试该函数:
int main()
{

    int x1 = 123;
    int x2 = 0;
    int x3 = -3908;
    int y = -2147483647-1;

    //x1 = 123 y = -2147483648,x1+y 不溢出,x1-y溢出

    printf("%d + %d OK? %d\n", x1, y, tadd_ok(x1, y));

    printf("%d - %d OK? %d\n", x1, y, tsub_o(x1, y));

    //x2=0 y = -2147483648,x2+y 不溢出,x2-y溢出

    printf("%d + %d OK? %d\n", x2, y, tadd_ok(x2, y));

    printf("%d - %d OK? %d\n", x2, y, tsub_o(x2, y));

    //x3=-3908 y = -2147483648,x3+y 溢出,x3-y不溢出

    printf("%d + %d OK? %d\n", x3, y, tadd_ok(x3, y));

    printf("%d - %d OK? %d\n", x3, y, tsub_o(x3, y));

}
这题一开始做的有点懵逼,就是-y=y把自己绕进去了。 补码的减法也就是取逆,其实很简单,由于正负数是不对称的,上边也看到了2.32的题目。所以当x为int下限的时候,-x就是x,也就是加法的逆。 其他情况就是直接取负即可。

2.33 字长为4的补码取逆

x -x
十六进制 十进制 十进制 十六进制
0 0 0 0
5 5 -5 B
8 -8 -8 8
D -3 3 3
F -1 1 1
取一个补码表示的数的补码,除了各个位取补再加1之外,还有一个好办法是找到最右边的1,然后把这个1左边的所有位取反。

无符号和补码乘法

两个为什么放一起,是因为两者的底层操作完全相同。而且最后被截断的位也完全相同,只是解释不同。

2.34 字长3位的乘法

无符号整数的相乘,是直接用位相乘得到结果即可。补码相乘不是直接用位乘,而是先运算得到实际结果,再转换成二进制结果。
模式 x y x乘以y 截断之后的x乘以y
无符号 100 101 010100 20 100 4
补码 100 101 001100 12 100 -4
无符号 010 111 001110 14 110 6
补码 010 111 111110 -2 110 -2
无符号 110 110 100100 36 100 4
补码 110 110 000100 4 100 -4
2.35 这个证明没能力做出来,但是代码可以记住,判断x乘以y是否溢出的代码:

2.36 使用int64_t来判断是否溢出。

思路是先将两个int转换成64位,相乘之后,判断高位是否有数字,简单的方法就是转成32位然后判断值是否相等。如果高位全部是1表示负数或者是0,则结果相等表示没有溢出。否则数值会有变化。
int tmult_ok64(int x, int y){
    __int64 result = (__int64) x * (__int64) y;

    return result == (int) result;
}

2.37 修改XDR库函数的溢出错误。

原来函数的核心错误是malloc的参数类型 size_t 只有32位,而数组长度乘以每个元素的大小的乘积可能会导致溢出。 即使使用64位无符号整数:
uint64_t asize = ele_cnt * (uint64_t) ele_size
这句话会把ele_size转成64位无符号,ele_cnt也会转成64位无符号,然而如果溢出存在,在传给malloc函数的时候,依然会被截断成低32位。 解决方法想了半天,后来看答案才恍然大悟,32位字长之下,由于寻址限制,malloc根本没有必要分配超过32位的内存数量。 所以就用之前的判断溢出函数判断一下乘积是否溢出,如果溢出就返回NULL,不溢出,再交给malloc函数进行工作。

乘以常数的优化

刚才普通的乘法是模拟两个变量相乘。在实际乘法中,如果乘以常数,编译器通常不会直接采用乘法,而是采用移位和乘法相结合的方式。 乘以2的幂,无论是无符号还是补码形式,都可以采取移位运算,之后即使溢出,其结果也和执行普通的乘法是一样的。 换算成2进制的话,如果一个的位数某一个位有一个1,乘以这个数就相当于移位这个1后边的几个0。 比如 110 * 100, 100的第三位有一个1,则相当于把110右移100后边的两位。 2.38 汇编指令的LEA就是移位然后加上一个数字,可以执行(x<<k)+b这样的命令。 在k = 0,1,2,3和b=0或者x的情况下,可以表示的a的倍数如下:
k b 倍数
0 0 1 即还是原来的x
1 0 2
2 0 4
3 0 8
0 x 2
1 x 3
2 x 5
3 x 9
综合起来看,可以表示1,2,3,4,5,8,9的倍数。

2.40

用移位来计算乘法:
  1. 由于6=4+2,一个数x乘以6 = (x<<1) + (x<<2)
  2. 由于31 = 32 - 1,一个数x乘以32 = x<<5 - x
  3. -6 = 2 - 8,所以是 (x<<1) - (x<<3)
  4. 55 = 32 + 16 + 8 - 1,所以是 (x<<5)+(x<<4)+(x<<3) - x,观察(x<<5)+(x<<4)+(x<<3)可以改写成 (x<<6) - (x<<3)的情况,所以最后是(x<<6) - (x<<3) - x

无符号和补码除法

整数的除法得到的结果是整数,相当于用竖式计算的时候得到的整数结果,抛弃余数。计算机除法的一个主要问题是留下的整数到底该往何处舍去。 对于无符号除以2的幂,由于无符号表示的都是非负数,可以采用将无符号数向右移的方法来除。而且结果也是一个整数,并且是向0舍入,所以结果是正确的。 但是补码除法就有一些问题了。在补码表示正数的时候,和无符号一样没有问题。但是在补码表示负数的时候,右移的时候高位会补1,在无法整除的情况下,结果会向负无穷舍入,而不是0。 举例子来说,如果只是用移位来解决问题。则 12340/16 = 771 ,而-12340/16 = -772,而这种结果是不可接受的,两个结果应该除了符号之外,整数的值相同。 所以才去的方法是给进行除法之前的数字加上一个偏置量,假如一个数字要除以2的k次幂,这个偏置量是(1<<k)-1,在如此操作之后,移位的结果就会向0的方向舍入,而不是向负无穷的方向。 所以补码除以2的幂的表达式就是 (x<0? x+(1<<k)-1: x) >> k

2.42 编写一个除以16的函数

不能使用任何除了移位和加减之外的方法。其实这就是把上边一个计算的规律写成函数,由于不能直接判断x是否大于0,则可以取x的最高位,然后替换公式里的结果:
int div16(int x){
    //向右移31位,然后用掩码来获取最低位,也就是参数的最高位,这一位代表是不是负数
    int highest_bit = (int) (0x00000001U & ((unsigned int) x) >> 15U);

    //16是2的四次方
    //用是不是负数来参与运算
    return (x + (highest_bit << 4U) - highest_bit) >> 4;

}

2.43 猜数字

这个首先要看机器产生了什么结果,然后来猜数字。 可以看到先把x左移5位,然后再减去x,可以知道结果是 2的5次方-1 = 31,即M= 31 再来看y,如果y小于0,则y加上7,然后右移3位。从前边的公式可以知道,k=3,偏置量是x + 1<<3 -1 正好是7,所以这个结果是y/8,即N=8

2.44 判断公式

  1. (x>0)|| (x-1)<0, 这个意思就是x大于0或者x-1小于0。考虑x为int下限的结果,x大于0为假,x-1的结果是+2147483647,此时两个条件都为假。所以当x为int下限的时候不成立。
  2. (x&7)!=7 || (x<<29<0)。 x&7的结果是只保留最后3位,左边成真的条件是不等于7,也就是后三位不是111。右边的结果是x右移29位之后最高位是1。令左边为真的数只有000-110六种,令右边成真的只有100,101,110三种。左边取值范围覆盖右边,所以恒为真。
  3. (x * x) >= 0,这个早已经讨论过,如果两个数相乘发生溢出,最高位被截取到1,则就不会大于0。在x = 46341的时候就会发生溢出。
  4. x<0 || -x <=0。很显然。这个在除了下限之外的结果都是成立的。如果x等于下限,x的负数还是自己,所以也成立,这个式子恒为真。
  5. x>0 || -x >=0。当x为下限的时候,-x还是x,所以两边都是假。当x为下限的时候这个式子不成立。
  6. x + y = ux + uy,由于位级操作相同,且都要转换成无符号数进行比较,所以为真。
  7. x * ~y + uy * ux == -x,这个从数值取反来看,由于底层位不变,计算完之后转换成无符号数字,则相当于ux * (0x11111111),在转换成int,式子恒等。
LICENSED UNDER CC BY-NC-SA 4.0
Comment