9.28 第二章习题

2.37

原代码用malloc申请了指定类型的大小个数字节的空间，如果成功分配了空间，就对这段空间进行赋值。

需要注意的是，malloc定义中，参数类型是int，所以A.中即使把asize改成了64位数据类型，依然不能赋值足够的空间。换句话说，只要用同一个分配空间的函数，我们就永远无法赋值超过字节的空间。我们只能让函数在遇到分配超过字节的时候返回一个表示“执行失败”的空指针。

需要注意的是，在C/C++语言的库中，表示数量一类的变量用的都是无符号类型。那么下面的代码就会出现一些问题：

1
2
3
4
5
6
7
vector<int>num;
int sum = 0;
/*中间执行若干操作*/
for (int i = 0;i <= num.size() - 1;i++) {
    sum += num[i];
}

应该如何修改这段代码？

2.71

原代码最后只保留了8个字节，没有符号扩展为32位。

1
2
int bits = bytenum << 3;
return word >> bits << 24 >> (24 - bits);

2.75

如果x和y都是正数，显然他们有没有符号都没区别了。我们主要讨论负数的情况。 考虑signed_high_prod是如何实现的。最终的返回值其实是的高位，那么计算时signed_high_prod需要先符号扩展为位，也就是在前面补了个1（二进制意义下）。 我们以16位扩展到32位举例。设原来是32位的0x和0x，在signed_high_prod函数中符号扩展后变成了0xFFFF和0xFFFF。但是我们要计算的是无符号数，也就是说它不应该被扩展，我们希望的是在前面填0而非1。 下一步，如果我们能让两个乘数的高16位被加上1，他们就相当于变成了没有被扩展过的无符号数了。也就是说我们要给这两个数相乘的结果先加上0xFFFF，根据乘法分配律，原式变成了0x0000$p_0p_1p_2p_3q_0q_1q_2q_3，那么再加上p_0p_1p_2p_3(1<<16)，再用乘法分配律，就变成了我们希望的p_0p_1p_2p_3和q_0q_1q_2q_3。我们回顾我们加上的两个乘数，化简之后其实就是p_0p_1p_2p_3和q_0q_1q_2q_3$0000。我们要写unsigned_high_prod，其实就是把signed_high_prod的结果加上这两个数抹去后16位的结果。

参考代码：

1
2
3
4
5
6
unsigned unsigned_high_prod(unsigned x, unsigned y) {
    signed sig_x = x >> (w - 1);//如果符号位是1，sig_x的值就是1
    signed sig_y = y >> (w - 1);
    signed signed_prod = signed_high_prod(x, y);
    return signed_prod + x * sig_y + y * sig_x;
}

2.77

不难发现位运算和乘法运算是有一定关系的。十进制下乘以就相当于原数末尾追加一个，同样地，二进制下左移一位相当于乘以。

换句话讲，我们可以把乘数的二进制表示展开，于是有 这里的要么是0，要么是1，于是以上的公式通过一系列变换后可以用以下的公式表示：

1
2
3
4
5
6
7
8
9
int mul(int x,int y){
    int ans=0;
    for(int i = 0;i <= 31;++i){
        if(y & (1 << i)){
            ans += x << i;
        }
    }
    return ans;
}

实际的CPU中是有专门的电路来计算乘法的（乘法消耗的时间依然是加法的数倍），因此我们一般不需要这样写。但是，整数的乘方也是我们常见的运算之一，CPU却没有这样的电路。你能根据上面的推导，举一反三，写出如何高效计算一个数的幂（指数为自然数）的方法吗？

参考代码：计算

1
2
3
4
5
6
7
8
int mul(int a,int b,int p){
    int ans = 1;
    for(; b; b >>= 1){
        if(b & 1) ans = ans * a % p;
        a = a * a % p;
    }
    return ans;
}

注意如果p比较大，中间过程可能溢出，需要使用long long。不同于暴力求解，在b是32位时，这串代码中的for最多循环32次，非常高效。甚至，如果和都是矩阵，上述推理依然成立。你可以再次推导一遍，但是在学习“代数结构”这一板块的数学知识后（将在大二下学习），你可能对这些知识的理解会更加深刻。

2.83

我们把每位看做一个整体，前位中，每一位在十进制下的值依次为

那么接下来位代表的值就是上式求和再乘，以此类推，记上式的值为，所以整个串的数值就是

2.86

类比32位浮点数阶码（8位）的-126~127，80位浮点数阶码（15位）是-16382~16383。