继续更新习题。

参考资料：

https://code.woboq.org/gcc/libiberty/calloc.c.html

https://dreamanddead.gitbooks.io/csapp-3e-solutions/content/

Chapter 2

72

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//有符号数和无符号数运算的结果为无符号数
void copy_int(int val, void *buf, int maxbytes){
    if (maxbytes - sizeof(val) >= 0){
        printf("copy_int copy successfully, size of val is %d, maxbytes is %d\n", sizeof(val), maxbytes);
        memcpy(buf, (void *) &val, sizeof(val));
    }
}

void copy_int_correct(int val, void *buf, int maxbytes){
    int bytes = sizeof(val);
    if (maxbytes - bytes >= 0){
        printf("copy_int_correct copy successfully, size of val is %d, maxbytes is %d\n", sizeof(val), maxbytes);
        memcpy(buf, (void *) &val, sizeof(val));
    }
}

void test(){
    void *buf = malloc(100);
    int d = sizeof(int);
    int maxbytes[2] = {d - 1, d};
    int val = 0;
    for (int i = 0; i < 2; i++){
        copy_int(val, buf, maxbytes[i]);
        copy_int_correct(val, buf, maxbytes[i]);
    }

}

int main(){
    test();

    return 0;
}

73

#include <stdio.h>

int d;
long long TMin;
long long TMax;

/* Addition that saturates to TMin or TMax */
int saturating_add(int x, int y){
    int z = x + y;
    if (x >= 0 && y >= 0){
        if (z < 0){
            return TMax;
        }else{
            return z;
        }
    }else if (x < 0 && y < 0){
        if (z >= 0){
            return TMin;
        }else{
            return z;
        }
    }else{
        return z;
    }
}

int judge(int x, int y){
    long long x1 = x;
    long long y1 = y;
    long long r1 = x1 + y1;
    long long r2 = saturating_add(x1, y1);
    if (r1 > TMax){
        return r2 == TMax;
    }else if (r1 < TMin){
        return r2 == TMin;
    }else{
        return r1 == r2;
    }
}

void test(){
    long long data[5] = {TMin, -1, 0, 1, TMax};
    int flag = 1;
    for (int i = 0; i < 5; i++){
        for (int j = 0; j < 5; j++){
            int r = judge(data[i], data[j]);
            if (!r){
                long long r1 = data[i] + data[j];
                long long r2 = saturating_add(data[i], data[j]);
                printf("Wrong answer!\n");
                printf("(%lld)+(%lld)=(%lld), answer of saturating_add is (%d)\n", data[i], data[j], r1, r2);
                return;
            }
        }
    }
    printf("Pass test!\n");
}

int main(){
    //初始化
    d = sizeof(int) * 8;
    TMin = 1 << (d - 1);
    TMax = ~TMin;
    //测试
    test();

    return 0;
}

74

#include <stdio.h>
#include <limits.h>

/* Determine whether arguments can be subtracted without overflow */
int tadd_ok(int x, int y){
    int sum = x + y;
    if (x >= 0 && y >= 0 && sum < 0){
        return 0;
    }else if (x < 0 && y < 0 && sum >= 0){
        return 0;
    }

    return 1;
}

int tsub_ok(int x, int y){
    //y=INT_MIN时-y=y
    if (y == INT_MIN){
        return x < 0;
    }else{
        return tadd_ok(x, -y);
    }
}

void test(){
    int num[5] = {INT_MIN, -1, 0, 1, INT_MAX};
    for (int i = 0; i < 5; i++){
        for (int j = 0; j < 5; j++){
            int a = num[i];
            int b = num[j];
            long long c = (long long) a - (long long) b;
            int d = a - b;
            //判断结果
            int f1 = (c == d);
            int f2 = tsub_ok(a, b);
            if (f1 != f2){
                printf("Wrong answer for %d, %d!\n", a, b);
                return;
            }
        }
    }
    printf("Pass test!\n");
}

int main(){
    test();
    
    return 0;
}

75

#include <stdio.h>
#include <limits.h>

int w = sizeof(int) * 8;
unsigned UNSIGNED_MAX = -1;

int signed_high_prod(int x, int y){
    long long z = (long long) x * y;
    z >>= w;
    
    return z;
}

unsigned unsigned_high_prod(unsigned x, unsigned y){
    int x1 = x;
    int y1 = y;
    //首位
    int x0 = (x >> (w - 1)) & 1;
    int y0 = (y >> (w - 1)) & 1;
    //根据68页公式
    unsigned z = signed_high_prod(x1, y1) + (x0 * y + y0 * x);

    return z;
}

//实际结果
unsigned unsigned_high_prod_(unsigned x, unsigned y){
    unsigned long long x1 = x;
    unsigned long long y1 = y;
    unsigned long long z = (x1 * y1) >> w;

    return z;

}

void test(){
    int n = 100;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            unsigned long long x = UNSIGNED_MAX - i;
            unsigned long long y = UNSIGNED_MAX - j;
            unsigned long long z = x * y;
            
            unsigned r1 = unsigned_high_prod(x, y);
            unsigned r2 = unsigned_high_prod_(x, y);
            //判断结果
            if (r1 != r2){
                printf("%x\n", r1);
                printf("%x\n", r2);
                printf("Wrong answer for %u, %u!\n", x, y);
                return;
            }
        }
    }
    printf("Pass test!\n");
}

int main(){
    test();
    
    return 0;
}

76

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//参考https://code.woboq.org/gcc/libiberty/calloc.c.html
void *calloc(size_t nmemb, size_t size){
    if (nmemb == 0 || size == 0){
        return NULL;
    }
    size_t n = nmemb * size;
    void * s = malloc(n);
    if (s){
        memset(s, 0, n);
    }
    
    return s;
}

int main(){
    return 0;
}

77

#include <stdio.h>

int alu(int x, int k){
    int res = 0;
    if (k == 17){
        //17=16+1
        res = (x << 4) + x;
    }else if (k == -7){
        //-7=1-8
        res = x - (x << 3);
    }else if (k == 60){
        //60=64-4
        res = (x << 6) - (x << 2);
    }else if (k == -112){
        //-112=16-128
        res = (k << 4) - (k << 7);
    }
}

int main(){
    return 0;
}

78

#include <stdio.h>

/* Divide by power of 2. Assume 0 <= k < w-1 */
int divide_power2(int x, int k){
    if (x >= 0){
        return x >> k;
    }else{
        return (x + (1 << k) - 1) >> k;
    }
}

int main(){
    return 0;
}

79

题意理解：

题目中说该函数会产生溢出，所以应该是先做乘法，再做除法，即$(3\times x )/4$，代码如下，其中mul3div4_是一开始写的版本，思路是带余除法：

不过求模运算应该替换掉比较好：

#include <stdio.h>
#include <limits.h>

/* Divide by power of 2. Assume 0 <= k < w-1 */
int divide_power2(int x, int k){
    if (x >= 0){
        return x >> k;
    }else{
        return (x + (1 << k) - 1) >> k;
    }
}

int mul3div4_(int x){
    int k = x / 4;
    int r = x % 4;
    int res = 3 * k + (3 * r) / 4;

    return res;
}

int mul3div4(int x){
    int res = divide_power2((x << 1) + x, 2);

    return res;
}

void test(){
    int num[5] = {-100, -1, 0, 1, 100};
    for (int i = 0; i < 5; i++){
        int x = num[i];
        int r1 = mul3div4(x);
        long long r2 = (long long) x * 3 / 4;
        if (r1 != r2){
            printf("%d %d\n", r1, r2);
            printf("Wrong answer for %d!\n", x);
            return;
        }
    }
    printf("Pass test!\n");
}

int main(){
    test();

    return 0;
}

80

和上题不同的是，此题不会产生溢出，所以运算顺序是$(x/4)\times 3$，此题的思路如下，首先将$x$写成：

当$x\ge 0$时，$0\le r< 4$；当$x<0$时，$-4<r \le 0$；$k$可以通过divide_power2计算，从而计算出$r$，那么我们的结果为

所以代码如下：

#include <stdio.h>
#include <limits.h>

/* Divide by power of 2. Assume 0 <= k < w-1 */
int divide_power2(int x, int k){
    if (x >= 0){
        return x >> k;
    }else{
        return (x + (1 << k) - 1) >> k;
    }
}

int mul3(int x){
    return (x << 1) + x;
}

int threefourths(int x){
    //向0舍入的除法
    int k = divide_power2(x, 2);
    //计算"余数", x < 0时"余数"为负
    int r = x - (k << 2);
    //向0舍入, 注意要考虑余数
    int res = mul3(k) + divide_power2(mul3(r), 2);

    return res;
}

void test(){
    int num[7] = {INT_MIN, -99, -1, 0, 1, 99, INT_MAX};
    for (int i = 0; i < 5; i++){
        int x = num[i];
        int r1 = threefourths(x);
        long long r2 = (long long) x * 3 / 4;
        if (r1 != r2){
            printf("%d %d\n", r1, r2);
            printf("Wrong answer for %d!\n", x);
            return;
        }
    }
    printf("Pass test!\n");
}

int main(){
    test();

    return 0;
}