CSAPP-1:家庭作业以及Data Lab要点

信息存储

1. 将一个$w$位的字中的字节0(最低位)开始编号，并将参数$x$的字节$i$替换为字节$b$，要考虑大小端：

    unsigned replace_byte(unsigned x, int i, unsigned char b)
    {
        unsigned int *p = &x;
        unsigned char *v = (unsigned char *) p;
           
        if (is_little_endian())
            v[i] = b;
        else 
            v[sizeof(unsigned) - i - 1] = b;
           
        return *p;
    }
   
    int is_little_endian(void)
    {
        int n = 1;
        int *p = &n;
        int *v = (void *) p;
           
        if (*v == 0x01)
            return 1;
        else
            return 0;
    }
   

2. 判断表达式是否满足以下任一条件： 通过逻辑反的判断来确保任何结果都是对的
   1. $x$的任何位都为1 !(x ^ 0xffffffff)
   2. $x$的任何位都为0 !(x ^ 0x0)
   3. $x$的最低有效字节的位都为1 !((x & 0xff) ^ 0xff)
   4. $x$的最低有效字节的位都为0 !((x & 0xff) ^ 0x0)

3. 判断机器是否为算术右移：

    int int_shifts_are_arithmetic()
    {
        int n = -1;
        int shifts = (n>>2);
        return shifts == n;
    }
   

4. 用算术右移来完成逻辑右移以及用逻辑右移完成算术右移，后面其他操作不能包含右移和除法。 在实现算术右移的时候注意 如何判断x的最高位是否为1

    // 算术右移到逻辑右移
    unsigned srl(unsigned x, int k)
    {
        /* perform shift arithmetically */
        unsigned xsra = (int) x >> k;
           
        int mask = -1;
           
        mask = mask << ((sizeof(int) << 3) - k);
        return ~mask & xsra;
    }
   
    unsigned sra(int x, int k)
    {
        /* perform shift logically */
        int xsrl = (unsigned) x >> k;
           
        unsigned mask = 1;
        int *p = &x;
        char *temp = (void *) p;
           
        // 判断x的最高位是否为1
        int h = (((mask << 7) & temp[sizeof(int) - 1]) == 128);
           
        h = (-h) << ((sizeof(int) << 3) - k);
        return h | xsrl;
    }
   

5. 判断是否$x$的任一奇数位为1：!(x & 0x55555555). 这里要用&是因为避免$x$偶数位的影响。

6. 判断$x$的位表示中是否有奇数个1：

    int odd_ones(unsigned x)
    {
        x ^= x >> 1;
        x ^= x >> 2;
        x ^= x >> 4;
        x ^= x >> 8;
        x ^= x >> 16;
        return x & 0x1;
    }
   

   第一次异或的结果，第$i$个位置上是1代表原数中第$i$位和第$i+1$位有一个为1，也就是奇数个1。也就是说，某个位为1，代表从它开始向左连续两位中1的个数是奇数（异或的本质）。第二次异或，就是两位两位的比较了，比如，若结果第6位为1，那么代表上一次的结果的第6位和第8位有奇数个1，也就是原数中第6,7,8,9位中有奇数个1。 整个过程就是不断的压缩信息。

7. 得到暗示x最左侧的1的掩码，例如0xFF00 -> 0x8000

    int leftmost_one(unsigned int x)
    {
        unsigned int base = 0x80000000;
        while(base)
        {
            if((x & base))
                break;
            base >>= 1;
        }
    }
   

   这样做可以返回0x8000，但是没有涉及到掩码：

    int leftmost_one(unsigned x)
    {
        x |= x >> 1;
        x |= x >> 2;
        x |= x >> 4;
        x |= x >> 8;
        x |= x >> 16;
        return (x & (~(x >> 1)));
    }
   

   假设此时的字长$w$ = 8，假设 x = 00010110，首先前五步将$x$最左侧的1的右侧全置为1，得到0x00011111，在此基础上右移一位再取反就可以得到掩码了。

8. 得到最低侧$n$位均为1的值：-1 >> (w-n)注意当$n=w$的情况，此时右移$n$位的实际操作是不变

9. 将$x$的最高$n$位交换到末尾，例如: n=4, x=0x12345678 -> 0x23456781

    unsigned rotate_left(unsigned x, int n)
    {
        int w = sizeof(int) << 3;
        unsigned temp = x >> (w - n - 1) >> 1;
           
        return (x << n) + temp;
    }
   

10. 判断一个数能否用$n$位补码来表示：

    正数需要要求第$n$位不为1，例如2是无法用2位来表示的。 负数要求$n$到$w$位均为1才可以。

    int fits_bits(int x, int n)
    {
        int neg = x >> (n - 1); //考虑算术右移
        int pos = x >> (n - 1); 
        return neg == -1 || pos == 0;
    }
    

11. $a^k$表示$a$重复$k$次，假设一个$w$位的类型，如何不适用$w$得到以下数值
    1. $1^{w-k}0^{k}$: (-1) << k
    2. $0^{w-k-j}1^k0^j$: a = -1 << (k-j), b = -1 << j, ~(a|~b)

整数运算

1. 符号整数饱和加法（正溢出返回TMax，负溢出返回TMin）以及对应的判断减法是否溢出（注意y=TMin的情况）

    int asturating_add(int x, int y)
    {
        int sum = x + y;
        int w = sizeof(int) << 3;
           
        // x, y, sum的最高位
        int h_x = (unsigned) x >> (w - 1);
        int h_y = (unsigned) y >> (w - 1);
        int h_sum = (unsigned) sum >> (w - 1);
           
        // neg = 1 表示负溢出， pos = 1 表示正溢出
        int neg = h_x && h_y && !h_sum;
        int pos = !h_x && !h_y && h_sum;
           
        return (-neg & INT_MIN) + (-pos & INT_MAX);
    }
   
    int tsub_ok(int x, int y)
    {
        if(y == INT_MIN){
            return x < 0;
        }
        int temp = asturating_add(x, -y);
        return temp != INT_MIN && temp != INT_MAX;
    }
   

2. 假设我们已有用于计算$x$和$y$采用补码形式下$x\cdot y$的高$w$位的函数

    int signed_high_prod(int x, int y);
   

   现在计算无符号变量$x\cdot y$的高$w$位：

   这里用到$x’\cdot y’ = x\cdot y + (x_{w-1}y+y_{w-1}x)2^w + x_{w-1}y_{w-1}2^{2w}$.

    int signed_high_prod(int x, int y) 
    {
    int64_t mul = (int64_t) x * y;
    return mul >> 32;
    }
   
    unsigned unsigned_high_prod(unsigned x, unsigned y)
    {
        int w = sizeof(int) << 3;
        int x_highest_bit = x >> w - 1;
        int y_highest_bit = y >> w - 1;
        return signed_high_prod(x, y) + (-y_highest_bit & x) + (-x_highest_bit & y);
    }
   

3. 实现calloc函数为一个数组分配内存，该数组有nmemb个元素，每个元素size字节：判断是否发生溢出！

    void *calloc(size_t nmemb, size_t size)
    {
        if (nmemb == 0 || size == 0)
            return NULL;
        size_t bytes = nmemb * size;
        if (nmemb == bytes / size) // 判断是否溢出
        {
            void* ptr = malloc(bytes);
            memset(ptr, 0, bytes);
            return ptr;
        }
        return NULL;
    }
   

4. 实现整数除以2的幂数： 如何不适用判断来做到合理偏置（-1\0 & mask）

    int divide_power2(int x, int k)
    {
        int sign = (x & INT_MIN) == INT_MIN;
        int mask = (1 << k) - 1;
        int bias = -sign & mask;
           
        return (x + bias) >> k;
    }
   

5. 对于整数参数$x$，分两种方式计算$3*x/4$的值：1.会出现溢出；2.向零舍入，不会溢出。 不溢出就需要用更大的类型来存储，计算完毕后再进行舍入。

    int mul3div4(int x)
    {
        int result = (x << 1) + x;
        return divide_power2(result, 2);
    }
   
    int threefourths(int x)
    {
        int64_t result = ((int64_t) x << 1) + x;
        int sign = (x & INT_MIN) == INT_MIN;
        int mask = (1 << 2) - 1;
        int bias = -sign & mask;
        return (result + bias) >> 2;
    }
   
   

浮点数运算

1. 实现浮点数小于号判断（假设两个参数都不是NaN）：
   1. +0.0等于-0.0
   2. 考虑NaN（默认比任何数都大）
   3. 考虑正负号
   4. 正数升序，负数降序（正负无穷也可以按照此规律）

    unsigned f2u(float x) 
    {
    return *(unsigned*)&x;
    }
   
    int float_le(float x, float y) 
    {
    unsigned ux = f2u(x);
    unsigned uy = f2u(y);
   
    unsigned sx = ux >> 31;
    unsigned sy = uy >> 31;
       
    return (ux << 1 == 0 && uy << 1 == 0) ||
            (sx > sy) ||
            (sx && sy && ux >= uy) ||
            (!sx && !sy && ux <= uy);
    }
   

2. 实现$2^x$的浮点表示：

    float u2f(unsigned u)
    {
        return *(float *) &u;
    }
    float fpwr2(int x)
    {
        /* Result exponent and fraction */
        unsigned exp, frac;
        unsigned u;
        if (x < -126 - 23)
        {
            /* Too small. Return 0.0 */
            exp = 0;
            frac = 0;
        }
        else if (x < -126)
        {
            /* Denormalized result */
            exp = 0;
            frac = 1 << (23 + x + 126);
        }
        else if (x < 128)
        {
            /* Normalized result. */
            exp = x + 127;
            frac = 0;
        }
        else
        {
            /* Too big. Return +oo */
            exp = 255;
            frac = 0;
        }
        /* Pack exp and frac into 32 bits */
        u = exp << 23 | frac;
        return u2f(u);
    }
   

3. 实现对一个浮点数求相反数： 关键是符号，阶码，尾码的获取与重组

    typedef unsigned float_bits;
       
    /* Compute -f. If f is NaN, then return f. */
    float_bits float_negate(float_bits f)
    {
        float_bits sign, exp, frac;
           
        sign = f >> 31;
        exp = f >> 23 & 0xff;
        frac = f & 0x7fffff;
           
        if (exp == 0xff && frac)
            return f;
        else
            return (~sign << 31) | (exp << 23) | frac;
    }
   

4. 实现浮点数绝对值函数：

    float_bits float_absval(float_bits f)
    {
        float_bits exp, frac;
           
        exp = f >> 23 & 0xff;
        frac = f & 0x7fffff;
           
        if (exp == 0xff && frac)
            return f;
        else
            return 0 << 31 | (exp << 23) | frac;
    }
   

5. 实现$2.0*f$：
   1. 考虑NaN
   2. 考虑非规格化： frac左移一位就相当于exp最低位有1
   3. 考虑2f溢出的情况，即exp=0xff或0xff-1
   4. 考虑规格化

    float_bits float_twice(float_bits f)
    {
        float_bits sign, exp, frac;
           
        sign = f >> 31;
        exp = f >> 23 & 0xff;
        frac = f & 0x7fffff;
           
        if (exp == 0xff && frac)
            return f;
           
        if (exp == 0)  // 非规格化的值
            frac <<= 1;
        else if (exp == 0xff - 1)  //无穷大时
        {
            frac = 0;
            exp = 0xff;
        }
        else
            exp += 1;
           
        return (sign << 31) | (exp << 23) | frac;
    }
   

6. 实现$0.5*f$：
   1. 考虑NaN
   2. 考虑非规格化时的舍入 学习如何向偶数舍入（只有11的情况才需要+1）
   3. 考虑exp=1 抛开符号位，整体右移一位再舍入
   4. 考虑其他规格化情况

    float_bits float_half(float_bits f)
    {
        float_bits sign, exp, frac, rest;
           
        sign = f >> 31;
        exp = f >> 23 & 0xff;
        frac = f & 0x7fffff;
        rest = f & 0x7FFFFFFF;
           
        if (exp == 0xff)
            return f;
           
        /* 向偶数舍入
        * round to even, we care about last 2 bits of frac
        *
        * 00 => 0 just >>1
        * 01 => 0 (round to even) just >>1
        * 10 => 1 just >>1
        * 11 => 1 + 1 (round to even) just >>1 and plus 1
        */
        int addition = (frac & 0x3) == 0x3;
   
        if (exp == 0) {
            /* Denormalized */
            frac >>= 1;
            frac += addition;
        } else if (exp == 1) {
            /* Normalized to denormalized */
            rest >>= 1;
            rest += addition;
            exp = rest >> 23 & 0xFF;
            frac = rest & 0x7FFFFF;
        } else {
            /* Normalized */
            exp -= 1;
        }
   
        return (sign << 31) | (exp << 23) | frac;
    }
   

7. 实现float到int的转换，向零舍入，如果超出表示范围则返回0x80000000：
   1. 考虑溢出或者NaN（int 最大只能表示$2^{31}$）
   2. 当exp < bias时，浮点数f的绝对值小于1，直接返回0
   3. 此时bias <= exp < 31+bias, 即 0 <= E < 31 时，由于浮点数小数部分只有23位，此时分为两种情况：
      1. E > 23 时，rest 左移 E-23位
      2. E <= 23 时，rest 右移 23-E位（将精确数字舍去一部分就是向零舍入）

    int float_f2i(float_bits f)
    {
        float_bits sign, exp, frac;
        float_bits M, E, bias;
           
        sign = f >> 31;
        exp = f >> 23 & 0xff;
        frac = f & 0x7fffff;
        bias = 0x7f;
           
        if (exp>= 31 + bias || exp == 0xff)  // overflow or f is NaN
            return 0x80000000;
        else if (exp < bias)  // 结果小于1
            return 0;
        else
        {
            M = frac | 0x800000;
            E = exp - bias;
            if (E > 23)
                return pow(-1, sign) * (M << (E - 23));
            else
                return pow(-1, sign) * (M >> (23 - E));
        }
    }
   

8. 实现int到float的转换：
   1. 0直接返回
   2. 如果是负数，先确定sign，然后取反+1获得其绝对值
   3. 算出最左侧的1在第k位，则exp = k+bias
   4. 如果k > 23，需要考虑如何舍入：
      1. 截断的部分大于截断的一半，向上舍入
      2. 截断的部分等于截断的一半，向偶数舍入 i&hide == hide是判断某一位是否为1，与判断符号数是否是负数一样
      3. 截断的部分小于截断的一半，向下舍入

    float_bits float_i2f(int i)
    {
            unsigned sign, exp, frac;
            unsigned leftmost, rightmost, t;
   
            if (i == 0)
                    return i;
   
            sign = (i & INT_MIN) == INT_MIN;
            if (sign)
                    i = ~i + 1;
            for (rightmost = 1, t = INT_MIN; (t & i) != t; t >>= 1)
                    rightmost++;
            leftmost = (sizeof(int) << 3) - rightmost; //最左侧的1的位置
            exp = leftmost + 127;
   
            int shift;
            if (leftmost > 23) { // 考虑舍入
                    shift = leftmost - 23;
                    int mask = ((1 << shift) - 1) & i;
                    int half = 1 << (shift - 1);
                    int hide = 1 << shift;
                    //mask == half时只有舍入位为1时才加1
                    int round = mask>half || (mask==half && (i&hide)==hide); 
                    frac = (i >> shift) & 0x7FFFFF; //考虑算术右移的影响
                    if (frac == 0x7FFFFF && round == 1) //+1有可能导致进位
                            frac = 0, exp++;
                    else
                            frac += round;
            } else { // 补满23位
                    shift = 23 - leftmost;
                    frac = (i << shift) & 0x7FFFFF;
            }
   
            return (sign << 31) | (exp << 23) | frac;
    }
   

• csapp