写在前面

暑假要结束了，今天最后一天，就不干什么了，打算把暑假做的一些东西整理一下，虽然也没做什么吧……Data Lab应该是8月底做的，鸽到现在才写文章总结，感觉还是得刚做完就写文章，这个lab的技巧性很强，现在要是想把文章写得很明白的话，恐怕要花不少功夫理解我之前的思路，所以如果文章写的不是很详细的话还请见谅，可以问ai什么的。我更多还是展示自己的解法以供参考，能自己完成并通过测试当然是更好的，至少对我来说，我费劲写完一道题后，根本也没精力看别人的解法如何了……

好消息是买的泡沫第4卷要到了(❁´◡`❁)，当时看有首刷限定的现货，犹豫了一会后买了，因为听说又要再版了？现在看来还挺极限的，毕竟明天就走了，要是买晚点而且国庆不回来的话，可能就要1月份才能看到了

补充，下午五点到的，吃完晚饭去拿的（也可能间接导致了晚上啥也没干（￣︶￣）↗　
明信片的图案好像是夏织头像吧
全家福~

bitXor

注释已经对解法做出了说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
  /*
   * x ^ y = ~x&y | ~y&x
   * x | y = ~ (~x & ~y)
   */
  int x_and_not_y = x & ~y;
  int not_x_and_y = ~x & y;
  int result = ~ (~x_and_not_y & ~not_x_and_y);
  return result;
}

tmin

这题比较简单，理解补码表示后就知道哪个数最小了

1
2
3
4
5
6
7
8
9
10
/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  /* The most significant bit is 1. */
  return 1 << 31;
}

isTmax

第一道难题出现，这题最难的地方在于证明充要条件，即最大数确实满足加上1取反后是自己，但满足加上1取反后是自己的数一定是最大数吗？这是不一定的，事实上111…11也满足加上1取反后是自己，但它并不是最大数，我们需要证明只有这两个数满足~(x + 1) == x，这样排除掉全1后，就能判断是不是最大数

如果x满足加上1后取反等于自己，那么~(x+1) ^ x就会得到全0，反过来，如果~(x+1) ^ x得到全0，说明~(x+1)和x长得一样，这是用来判断两个数完全一样的方法

关于充要条件的数学证明我先不写了，以（ke）后（neng）有（bu）时（hui）间（zai）再（xie）补（le）吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTmax(int x) {
  /* 
   * 0111...1 + 1 = 1000...0 
   * ~ 1000...0 = 0111...1
   *
   * But there is another circumstance !
   * 1111...1 + 1 = 0000...0
   * ~ 0000...0 = 1111...1

   * And we need to prove that there are only these two numbers that satisfy
   * ~(x + 1) == x
   */
  return !(~(x+1)^x) & !!(~x);
}

allOddBits

第一道利用掩码的题出现了，如果没想到用掩码可能比较难，注释写得比较详细了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x) {
  /*
   * Return 1 if all odd-numbered bits in word are 1s.
   * We can use 0xAA(170) to construct 0xAAAAAAAA.
   * 
   * Notice that we only demand the odd-numbered bits are 1s, for
   * example, allOddBits(0xFFFFFFFF) should return 1. 
   * They satisfy that x & mask == mask. On the other hand, if
   * x satisfy x & mask == mask, x's all odd-numbered bits are 1s.
   */
  int mask = 0xAA;              // 10101010
  mask = (mask << 8) + mask;    // 0xAAAA
  mask = (mask << 16) + mask;   // 0xAAAAAAAA
  return !((x & mask) ^ mask);
}

negate

书里的知识

1
2
3
4
5
6
7
8
9
10
/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return ~x + 1;
}

isAsciiDigit

我一开始的解法是用掩码，利用了在0x30和0x39间的数字在格式上的特殊性
更一般的做法是翻译0x30 <= x <= 0x39这个条件，可能需要担心的是如果x是负数会不会溢出，导致low大于等于0而up也大于等于0，如果是这种情况，那么x−0x30<−2w−1x - 0x30 < -2^{w-1}，这时0x39−x>0x30−x>2w−10x39 - x > 0x30 - x > 2^{w-1}一定positive overflow，所以up一定小于0，因此不需要担心这种情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* 
 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
 *   Example: isAsciiDigit(0x35) = 1.
 *            isAsciiDigit(0x3a) = 0.
 *            isAsciiDigit(0x05) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 3
 */
int isAsciiDigit(int x) {
  /*
   * x should be 00...0011 0xxx
   * or
   * 00...0011 100x
   */
  /*
  int situation_1 = 0x06;
  int situation_2 = 0x1c;
  return !(x>>3 ^ situation_1) | !(x>>1 ^ situation_2);
  */

  /**
   * Of course you can add the condition that x>>31 == 0 to avoid
   * overflow. However, the codes below are enough.
   * This requires a mathematical proof.
   */
  int low = x + (~0x30 + 1); // x - 0x30 >= 0
  int up = 0x39 + (~x + 1);  // 0x39 - x >= 0
  return !(low >> 31) & !(up >> 31);
}

conditional

1
2
3
4
5
6
7
8
9
10
11
/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
  int mask = !x + ~1 + 1;     // !x-1 is 00...0 if x==0 and 11...1 otherwise.
  return (mask & y) | (~mask & z);
}

isLessOrEqual

比较麻烦的是异号时，做减法可能会溢出，好在这种情况下谁是正的谁大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 
 * 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) {
  /**
   * If x and y have same signs, then we can use y-x to judge.
   * However, if x>0 and y<0, or x<0, y>0, overflow may happen.
   * In this situation, we only need to see whether the sign bit of x is 1.
   */
  int neg_and_pos = (x ^ y) >> 31;      // 11...1 if xy < 0.
  int x_msb = (x>>31) & 1;              // 00...00 or 00...01
  int same_sign_result = y + (~x + 1);  // y-x
  return (neg_and_pos & x_msb) | (!neg_and_pos & !(same_sign_result>>31));
}

logicalNeg

如果x不是0，那么它和它的补(逆元)的符号位是不一样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 
 * logicalNeg - implement the ! operator, using all of 
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int logicalNeg(int x) {
  /**
   * Notice that if x is not 0, then the MSB of x is 1 
   * or the MSB of -x is 1
   */
  int neg_x = ~x + 1;
  int res = neg_x | x;
  return (res >> 31) + 1;
}

howManyBits

能不看提示做出来的是个人物，现在有点懒得复盘了，可以问ai或者自己琢磨一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/* 
 * howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
  int b_16, b_8, b_4, b_2, b_1;
  int shift_16, shift_8, shift_4, shift_2, shift_1;
  int set_high_repeat_to_zero = (x>>31) ^ x;
  x = set_high_repeat_to_zero;
  // Find the first 1 from right to the left. Then add the sign bit (counts 1).
  // Use binary search.
  b_16 = !!(x >> 16); // If there is 1 in the high 16 bits, b_16 = 1.
  shift_16 = b_16 << 4;
  x = x >> shift_16;
  b_8 = !!(x >> 8);
  shift_8 = b_8 << 3;
  x = x >> shift_8;
  b_4 = !!(x >> 4);
  shift_4 = b_4 << 2;
  x = x >> shift_4;
  b_2 = !!(x >> 2);
  shift_2 = b_2 << 1;
  x = x >> shift_2;
  b_1 = !!(x >> 1);
  shift_1 = b_1;
  x = x >> shift_1;  // If x = 00...0, then now x = 0. It should return 0 + 0 + 1 = 1.
  return shift_16 + shift_8 + shift_4 + shift_2 + shift_1 + x + 1; 
}

floatScale2

根据浮点数是什么类型来分类讨论，书本上说过三个类型，依次讨论即可，第一次做可能要做很久，这是正常的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/* 
 * floatScale2 - 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 floatScale2(unsigned uf) {
  int msb = uf >> 31;
  unsigned sp_mask = 0x7f800000;
  unsigned denormalized_mask = 0x807fffff;
  if ((uf & sp_mask) == sp_mask) {
    return uf; // f is NaN, infinity.
  } else if ((uf | denormalized_mask) == denormalized_mask) {
    // f is a denormalized value including +0 and -0.
    /**
     * It's interesting that just left shifting 1 and adding the sign bit is enough.
     * Because if the 22th bit is 1, left shift is equivalent to times 2 although f
     * is normalized now. The exponent is the same and normalized just add a implict 1.
     * If the 22th bit is 0, we only need to time the fraction field by left shift.
     */
    uf = (msb << 31) + (uf << 1); 
  } else {
    // f is a normalized value.
    uf = uf + 0x00800000;
    if ((uf & sp_mask) == sp_mask) {
      // f overflows.
      uf = (msb << 31) + sp_mask;
    }
  }
  return uf;
}

floatFloat2Int

提取exponent和小数部分，然后分类讨论，具体的有点忘了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/* 
 * floatFloat2Int - Return bit-level equivalent of expression (int) f
 *   for floating point argument f.
 *   Argument is passed as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point value.
 *   Anything out of range (including NaN and infinity) should return
 *   0x80000000u.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
int floatFloat2Int(unsigned uf) {
  unsigned shift;
  unsigned sign;
  unsigned frac_mask = 0x007fffffu;
  unsigned exp_mask = 0x7f800000u;
  unsigned frac = uf & frac_mask;
  unsigned exp = uf & exp_mask;
  sign = uf >> 31; // 0 or 1
  sign = ~sign + 1; // 00...0 or 11...1
  
  if (exp == 0x7f800000u) {
    return 0x80000000u; // Infinity or NaN.
  } else if (exp < 0x3f800000) {
    return 0; // Less than 1.
  } else {
    // f is a normalized value and greater than 1.
    shift = (exp >> 23) - 127;
    if (shift > 30) {
      // Overflow
      return 0x80000000u;
    } else if (shift > 23) {
      frac = (frac + 0x00800000) << (shift - 23);
      return frac + (sign << (1 + shift));
    } else {
      frac = (frac + 0x00800000) >> (23 - shift);
      return frac + (sign << (1 + shift));
    }
  }
}

floatPower2

这题好像网上很多答案是错的，不要忽略了非规格化数，非规格化数的阶码为−126-126，小数部分最小可以是2−232^{-23}，所以最小可以表达2−1492^{-149}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* 
 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
 *   (2.0 raised to the power x) for any 32-bit integer x.
 *
 *   The unsigned value that is returned should have the identical bit
 *   representation as the single-precision floating-point number 2.0^x.
 *   If the result is too small to be represented as a denorm, return
 *   0. If too large, return +INF.
 * 
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while 
 *   Max ops: 30 
 *   Rating: 4
 */
unsigned floatPower2(int x) {
    unsigned result;
    if (x < -149) {
      result = 0;
    } else if (x < -126) {
      // Denormalized value.
      result = 0x00000001u << (x + 149);
    } else if (x > 127) {
      result = 0x7f800000u;
    } else {
      x = x + 127;
      result = x << 23;
    }
    return result;
}

写在后面

最后一题可能会超时，用./btest -T 20即可
后面的题比较难，我隔了一段时间没什么思路了，有些题没有详细说明思路，也不太有必要重新去想了，这个lab主要是考察对第二章的理解程度，但技巧性是很强的，感觉如果不会做但是看答案能看懂的话也算掌握得差不多了