CSAPP —— lab1 datalab

准备工作

1. 阅读 README && bits.c 中的要求；

2. ./dlc -e bits.c 用来检测代码是否合规；

3. make btest 用来编译，而后键入 ./btest 测试所写代码的正确性；

4. ./ishow || ./fshow 可查看对应数字的十六进制表示；

5. 对 op 的作用理解：

   • !：逻辑判断，是否为 0

   • ~：二进制补码转换

   • &、|：构造特定位上的 0 / 1

   • <<、>>：二进制乘除

WriteUp

1. bitAnd 根据离散数学的知识，对 x & y 取反再取反，得到 ~(~x | ~y)。

2. getByte 要得到什么？某一字节的数据。那么如何处理其它字节的数据 —— &0 / ^self，方便起见这里采用 &0 的方式。因为所有的数据在底层都是一串 01，所以要想进行乘除，可以采用 shift。做法：将特定字节右移到最低位字节，再 &0xff。

3. logicalShift 正数直接右移没问题，主要处理一下负数右移产生的多余的 1（算术右移，空位补符号位导致），采用 & 的方式将其转变成 0。

4. bitCount 在不允许使用 looping && control statement 的情况下，完全没思路。参考别人的想法——二分法，分组判断有几个 1，最后累加求解。

5. bang 这题比较 tricky，用到的性质 self | self's complement = full 1（即 -1），所以除了 0 以外（0 | 0 = 0），其它所有的值最终都转变为 -1，求解结果再 +1，实现非 0 值 → 0、0 → 1，bang！

6. tmin 根据补码的二进制计算公式，1 << 31 顺理成章。

7. fitsBits 两个点。第一点，如何在 Legal ops: ! ~ & ^ | + << >> 的情况下实现减去某个数（假设为 n），答案是：~n + 1；第二点：怎么证明用 n bits 可以表示某个数？!(x ^ ((x << shift) >> shift))。能不能先右移再左移？肯定是不行的，因为右移数据会失真，原位上如果有 1，那么通过左移的方式就会变成 0，导致无法匹配。算法错误 → 结果错误。

8. divpwr2 对于正数，向下取整 no problem。对于负数，为了向 0 看齐，得加上一个偏移量，使得自身低 n 位为偶数。奇妙之处就在于，自己 + 自己 = 偶数（对低 n 位而言），因为奇 + 奇 = 偶，偶 + 偶 = 偶。

9. negate 根据反码的计算公式，~x + 1 水到渠成。

10. isPositive 首先得非负，所以判断其最高位。其次不为 0，逻辑判断 !! 就派上用场了。

11. isLessOrEqual 考虑到 overflow 的情况，因此分情况讨论。当 x 与 y 同号，判断二者差的符号位；当 x 与 y 异号，判断 x 的符号位。表达式为：((!same) & x_sign) | (same & !(diff_sign)) ，对于结果为 0 / 1 的情况，可以参考此种手法，实现选择性返回。

12. ilog2 目标：返回最高位 1 所在位数。借鉴 bitCount 思路，采用二分法，分组查询累加。

13. float_neg tip：从此题开始，可以用各式各样的 op && condition control && looping。若 NaN 返回 argument，否则返回 -argument。NaN 的判断依据是 exp == full 1 && frac ！= 0。可以通过先将 argument 左移一位，去除符号位的影响，再通过 if 判断。

14. float_i2f 将 int → float，逐步求 sign、exp、frac 即可。注意对有进位的情况进行修正。

15. float_twice 基本思路同 float_i2f。注意讨论 exp 全0、全1、非全0全1，三种情况下，应该对 frac / exp 做怎样的处理。

Code

/* 
 * bitAnd - x&y using only ~ and | 
 *   Example: bitAnd(6, 5) = 4
 *   Legal ops: ~ |
 *   Max ops: 8
 *   Rating: 1
 */
int bitAnd(int x, int y) {
    /* To achieve "x & y" expression */
    
    return ~(~x | ~y);
}
/* 
 * getByte - Extract byte n from word x
 *   Bytes numbered from 0 (LSB) to 3 (MSB)
 *   Examples: getByte(0x12345678,1) = 0x56
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int getByte(int x, int n) {
   /*
    *  All number is 0 | 1 in nature 
    *  so if you wanna mutiplie, consider shift
    *  First, deal parameter 'n', make it * 8
    *  then shift 'x', last clear
    */

    return (x >> (n << 3)) & 0xFF;
}
/* 
 * logicalShift - shift x to the right by n, using a logical shift
 *   Can assume that 0 <= n <= 31
 *   Examples: logicalShift(0x87654321,4) = 0x08765432
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3 
 */
int logicalShift(int x, int n) {
    /* Deal negative number high bit 1 */
    
    int recover = (1 << 31) >> n << 1;
    return ((x >> n) & ~recover);
}
/*
 * bitCount - returns count of number of 1's in word
 *   Examples: bitCount(5) = 2, bitCount(7) = 3
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 40
 *   Rating: 4
 */
int bitCount(int x) {
    int count;
    int tpMask1 = 0x55 | (0x55 << 8);
    int mask1 = tpMask1 | (tpMask1 << 16);  //01010101
    
    int tpMask2 = 0x33 | (0x33 << 8);
    int mask2 = tpMask2 | (tpMask2 << 16);  //00110011 

    int tpMask3 = 0x0f | (0x0f << 8);
    int mask3 = tpMask3 | (tpMask3 << 16);  //00001111 

    int mask4 = 0xff | (0xff << 16);        //00000000 11111111 
    int mask5 = 0xff | (0xff << 8);         //00000000 00000000 11111111 11111111
    count = (x & mask1) + ((x>>1) & mask1); 
    count = (count & mask2) + ((count >> 2) & mask2);  //每4位一组，先计算低位的两位，右移2位后再计算高位两位
    count = (count + (count >> 4)) & mask3;  //每8位一组
    count = (count + (count >> 8)) & mask4;  //每16位一组
    count = (count + (count >> 16)) & mask5;  //总共32位为一组，将前16位的结果与后16位的结果相加即得最终答案
    return count;
}
/* 
 * bang - Compute !x without using !
 *   Examples: bang(3) = 0, bang(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int bang(int x) {
    /* Self | self own complement get full 1 and then shift sign bit */
    
    int complement = ~x + 1;
    return ((x | complement) >> 31) + 1; 
}
/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
    /* According to the two's complement computation rule */

    return (1 << 31);
}
/* 
 * fitsBits - return 1 if x can be represented as an 
 *  n-bit, two's complement integer.
 *   1 <= n <= 32
 *   Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
int fitsBits(int x, int n) {
    /* 
     * Judge how many bits we need to represent this num 
     * Which means using shift operation doesn't change value
     * First expand to higher bit and move back
     * Meanwhile, ~n + 1 == -n (two's complement)
     */

     int shift = 32 + (~n + 1);
     return !(x ^ ((x << shift) >> shift)); 
}
/* 
 * divpwr2 - Compute x/(2^n), for 0 <= n <= 30
 *  Round toward zero
 *   Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
int divpwr2(int x, int n) {
    /* Check and then shift, negative low n bit add themself */
    
    int mask = ~((1 << 31) >> 31 << n); /* 00001111 */
    int b = (x >> 31) & mask; /* self += self must be even  */ 
    return (x + b) >> n;
}

/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
    return ~x + 1;
}
/* 
 * isPositive - return 1 if x > 0, return 0 otherwise 
 *   Example: isPositive(-1) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 3
 */
int isPositive(int x) {
    /* Judge from highest bit & 0? */
    
    int sign = x >> 31;
    int is_not_zero = !!x;
    return (is_not_zero & !sign);
}
/* 
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
int isLessOrEqual(int x, int y) {
    /* Use substraction, and then observe signed bit */
    
    int difference = y + (~x) + 1; 
    int x_sign = x >> 31; 
    int y_sign = y >> 31;  
    int same = !(x_sign ^ y_sign); 
    int diff_sign = difference >> 31; 
    return ((!same) & x_sign) | (same & !(diff_sign));  
}

/*
 * ilog2 - return floor(log base 2 of x), where x > 0
 *   Example: ilog2(16) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 90
 *   Rating: 4
 */
int ilog2(int x) {
    /* Dichotomy to find the highest one */
 
    int count = 0;
    count = !!(x >> 16) << 4;
    count += !!(x >> (count + 8)) << 3;
    count += !!(x >> (count + 4)) << 2;
    count += !!(x >> (count + 2)) << 1;
    count += !!(x >> (count + 1));
    
    return count;  
}
/* 
 * float_neg - Return bit-level equivalent of expression -f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representations of
 *   single-precision floating point values.
 *   When argument is NaN, return argument.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 10
 *   Rating: 2
 */
unsigned float_neg(unsigned uf) {
    /* Whether a NaN */
  
    if (((0xFF000000 & (uf << 1)) == 0xFF000000) /* exp == 11111111 */
          && (uf << 1) != 0xFF000000)            /* frac != 0 */
       return uf;
    else return uf ^ 0x80000000;
}

/* 
 * float_i2f - Return bit-level equivalent of expression (float) x
 *   Result is returned as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point values.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned float_i2f(int x) {
    /* int -> float, sign + exp + frac */

    /* special cases */
    if (x == 0x80000000) return 0xcf000000;
    if (x == 0) return 0;
    
    /* sign */
    unsigned sign = (x >> 31) << 31;
    
    /* exp */
    int abs_x = x; 
    /* get abs x */
    if (abs_x < 0) abs_x = -x; 

    int tmp = abs_x;
    int highest_bit = 0;
    while (tmp) {
        highest_bit++;
        tmp >>= 1;
    }
    int weight = highest_bit - 1;

    unsigned exp = (127 + weight) << 23;

    /* frac */
    unsigned frac, frac_cut;
    if (weight > 23) {
        frac = (abs_x >> (weight - 23)) & 0x7fffff;
        frac_cut = (abs_x << (31 - weight)) & 0xff;
        /* carry */
        if ((frac_cut > 0x80) || (frac_cut == 0x80 && (frac & 1))) {
            frac++;
        }
    } else frac = (abs_x << (23 - weight)) & 0x7fffff;

    return sign + exp + frac;
}
/* 
 * float_twice - Return bit-level equivalent of expression 2*f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representation of
 *   single-precision floating point values.
 *   When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned float_twice(unsigned uf) {
    /* sign + exp + frac */
    /* sign */
    unsigned sign = (uf >> 31) << 31;

    /* exp & frac */
    unsigned exp = uf & 0x7f800000;
    unsigned frac = uf & 0x7fffff;

    /* Deal with different situations */
    if (exp == 0x7f800000) return uf;
    else {
        if (exp == 0) frac <<= 1;
        else exp += 0x800000;
    }

    return sign + exp + frac;
}