写完 Lab2 拆炸弹的实验解析后，打算补一下实验 1 的内容。因为感觉自己把时间投入进去了，除了有无形的成果外还要有有形的成果。再说，实验课上没要求我们写报告，没点内容沉淀感觉不自在。

CSAPP LAB 实验

实验介绍

本实验主要包括一些有关位操作的编程题，我们的目标是实现这些编程题。所有要实现的代码都在 bits.c 文件中。

tar xvf datalab-handout.tar 解压代码，包含如下文件

  • bits.c：唯一需要修改的文件
  • btest.c：该文件的作用是对我们实现的 bits.c 功能的正确性行评估，
  • README：关于 btest 的一些说明。
  • dlc：语法检查

完成后用 ./dlc bits.c 检查 bits.c 的语法是否正确，就是是否按照要求使用规定数量的操作符。如果语法检查无误，那么使用 make btest，生成 btest 可执行文件，该文件检查 bits.c 中实现的函数功能是否与要求的一致，具体用法如下 ./btest

如果还需要修改 bits.c 那么需要 make clean。make btest 重新生成 btest 文件

./btest -fisPositive 单独测试某一个函数

rating 代表困难等级；max ops 代表最多可使用的操作符。

正确的测试结果为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Score   Rating  Errors  Function
 1      1       0       bitXor
 1      1       0       tmin
 1      1       0       isTmax
 2      2       0       allOddBits
 2      2       0       negate
 3      3       0       isAsciiDigit
 3      3       0       conditional
 3      3       0       isLessOrEqual
 4      4       0       logicalNeg
 4      4       0       howManyBits
 4      4       0       floatScale2
 4      4       0       floatFloat2Int
 4      4       0       floatPower2
Total points: 36/36

代码编写要求

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#if 0
/*
 * Instructions to Students:
 *
 * STEP 1: Read the following instructions carefully.
 */

You will provide your solution to the Data Lab by
editing the collection of functions in this source file.

INTEGER CODING RULES:
 
  Replace the "return" statement in each function with one
  or more lines of C code that implements the function. Your code 
  must conform to the following style:
 
  int Funct(arg1, arg2, ...) {
      /* brief description of how your implementation works */
      int var1 = Expr1;
      ...
      int varM = ExprM;

      varJ = ExprJ;
      ...
      varN = ExprN;
      return ExprR;
  }

  Each "Expr" is an expression using ONLY the following:
  1. Integer constants 0 through 255 (0xFF), inclusive. You are
      not allowed to use big constants such as 0xffffffff.
  2. Function arguments and local variables (no global variables).
  3. Unary integer operations ! ~
  4. Binary integer operations & ^ | + << >>
    
  Some of the problems restrict the set of allowed operators even further.
  Each "Expr" may consist of multiple operators. You are not restricted to
  one operator per line.

  You are expressly forbidden to:
  1. Use any control constructs such as if, do, while, for, switch, etc.
  2. Define or use any macros.
  3. Define any additional functions in this file.
  4. Call any functions.
  5. Use any other operations, such as &&, ||, -, or ?:
  6. Use any form of casting.
  7. Use any data type other than int.  This implies that you
     cannot use arrays, structs, or unions.

 
  You may assume that your machine:
  1. Uses 2s complement, 32-bit representations of integers.
  2. Performs right shifts arithmetically.
  3. Has unpredictable behavior when shifting if the shift amount
     is less than 0 or greater than 31.


EXAMPLES OF ACCEPTABLE CODING STYLE:
  /*
   * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31
   */
  int pow2plus1(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     return (1 << x) + 1;
  }

  /*
   * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31
   */
  int pow2plus4(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     int result = (1 << x);
     result += 4;
     return result;
  }

FLOATING POINT CODING RULES

For the problems that require you to implement floating-point operations,
the coding rules are less strict.  You are allowed to use looping and
conditional control.  You are allowed to use both ints and unsigneds.
You can use arbitrary integer and unsigned constants. You can use any arithmetic,
logical, or comparison operations on int or unsigned data.

You are expressly forbidden to:
  1. Define or use any macros.
  2. Define any additional functions in this file.
  3. Call any functions.
  4. Use any form of casting.
  5. Use any data type other than int or unsigned.  This means that you
     cannot use arrays, structs, or unions.
  6. Use any floating point data types, operations, or constants.


NOTES:
  1. Use the dlc (data lab checker) compiler (described in the handout) to 
     check the legality of your solutions.
  2. Each function has a maximum number of operations (integer, logical,
     or comparison) that you are allowed to use for your implementation
     of the function.  The max operator count is checked by dlc.
     Note that assignment ('=') is not counted; you may use as many of
     these as you want without penalty.
  3. Use the btest test harness to check your functions for correctness.
  4. Use the BDD checker to formally verify your functions
  5. The maximum number of ops for each function is given in the
     header comment for each function. If there are any inconsistencies 
     between the maximum ops in the writeup and in this file, consider
     this file the authoritative source.

/*
 * STEP 2: Modify the following functions according the coding rules.
 * 
 *   IMPORTANT. TO AVOID GRADING SURPRISES:
 *   1. Use the dlc compiler to check that your solutions conform
 *      to the coding rules.
 *   2. Use the BDD checker to formally verify that your solutions produce 
 *      the correct answers.
 */


#endif

实验内容

所有问题的答案均不唯一。因为我也在同时学习《离散数学》所以里面用到了不少命题表达。

异或的实现（难度：⭐）

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
  // A 异或 B
  int a = x & (~y);  //10
  int b = (~x) & y;  //01
  return ~((~a)&(~b));  //
}

如果你读过《离散数学》就会知道，任意的命题公式都可以仅包含 {¬,∨}\{ \neg,\vee \} 或 {¬,∧}\{ \neg,\wedge \} 的命题公式等价代换。因为：

  1. 由 P↔Q  ⟺  (P→Q)∧(Q→P)P\leftrightarrow Q \iff(P\to Q)\wedge(Q\to P)。故我们可以把 ↔\leftrightarrow 替换为 →,∧\to,\wedge
  2. 由 P→Q  ⟺  ¬P∨QP\to Q\iff \neg P\vee Q。故我们可以把 →\to 替换为 ¬,∨\neg,\vee
  3. 由 P∧Q  ⟺  ¬(¬P∨¬Q),P∨Q  ⟺  ¬(¬P∧¬Q)P\wedge Q\iff \neg(\neg P \vee \neg Q),P\vee Q \iff \neg(\neg P\wedge \neg Q)，说明 ∨,∧\vee,\wedge 可以互相转换。

如果定义了 ↑\uparrow（与非）、↓\downarrow（或非），那么最小的联结词组亦可为 {↑}\{ \uparrow \} 或 {↓}\{ \downarrow \}。

那么上面的编程题就变为求只用 ¬,∧\neg,\wedge 表示异或：

P⊕Q  ⟹  (P∧¬Q)∨(¬P∧Q)  ⟹  ¬(¬(P∧¬Q)∧¬(¬P∧Q))\begin{aligned} P \oplus Q & \implies (P\wedge \neg Q)\vee (\neg P \wedge Q) \\ & \implies \neg(\neg (P\wedge \neg Q)\wedge \neg (\neg P \wedge Q)) \end{aligned}

补码的最小值（难度：⭐）

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

多翻翻书看看定义。

补码的最大值（难度：⭐⭐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
 * 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) {
  int res = x+1;
  // 测res是不是0x80000000;
  int is_not_zero =!!((res^0x00)); // res不是0
  int is_neg_self_equals = !(((~res)+1)^res); // res 的负数等于自身
  return is_neg_self_equals&is_not_zero;
}

补码的最大值为：0x7fffffff，我们可以换个思路，变成判断该数是否为补码的最小值 0x80000000。

关于补码的最小值 INT_MIN 有以下特点：

  • INT_MIN == - INT_MIN
  • 一个补码取反加 1 等于自身的数只有两个：INT_MIN 和 0。

根据以上两点构造命题逻辑即可。

所有的奇数位是否为 1（难度：⭐⭐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 
 * 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) {
  int mask = 0xAA; // 10101010.......
  mask |= mask<<8;
  mask |= mask<<16;

  x&=mask;
  x|=x>>1;
  x=~x;
  return !x;
}

巧用移位和掩码。

补码的非（难度：⭐⭐）

看过书的都知道，这也是最简单的了。

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;
}

附一张理解补码「取反加一」的图：image.png

是否为 ASCII 数字（难度：⭐⭐⭐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 
 * 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) {
  // 0x30:  ...00110000
  // 0x39:  ...00111001
  int high_check = !((x>>4)^0x03); // 1 则正确
  int p3 = x&0x08;
  int p2 = x&0x04;
  int p1 = x&0x02;
  int low_check = (!p3)|(!(p2|p1));  // p3 -> !(p2|p1)
  return high_check&low_check;
}

观察 ASCII 数字的十六进制代码可以发现，0x30 到 0x39 的特点：

  • 高 28 位一定是 0x0000003。对应上面代码的 high_check
  • 低 4 位的特点，从右往左，0 位开始计数：
    • 如果第 3 位为 0，则这个数满足要求
    • 如果第 3 为为 1，第 2 位或者第 1 位不能为 1

代码中 p3-p1 对应命题这些位是否为 1。很容易构造出命题：

P3→¬(P2∨P1)  ⟺  ¬P3∨¬(P2∨P1)P_3 \to \neg(P_2 \vee P_1) \iff \neg P_3 \vee \neg(P_2 \vee P_1)

三元运算符（难度：⭐⭐⭐）

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
 * 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 mix = y^z;
  int signal = !!x;
  signal = (signal<<31)>>31;
  return ((signal&z)|((~signal)&y))^mix; // y^z^y =z; z^y^z = y
}

两个非 ! 操作压缩位，很容易理解，仔细想想这个操作还是挺骚气的（后面会让你使用位运算实现这个 ! ）。

利用了异或的运算律：

\begin{align} a\oplus 0&=a \\ a\oplus a &= 0 \\ a\oplus b &= b\oplus a \\ (a \oplus b) \oplus c &= a \oplus( b \oplus c) \end{align}

小于等于（难度：⭐⭐⭐）

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) {
  int y_x = y  + ((~x)+1);
  int sx = (x>>31);//&0x01;
  int sy = (y>>31);//&0x01;
  int s_y_x = (y_x>>31);//&0x01;
  int condition1= (!sy)&(sx);
  int condition2 = (!s_y_x)&!((!sx)&sy); // x为正 y为负


  return condition1|condition2;
}

取非（难度：⭐⭐⭐⭐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* 
 * 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) {
  int res=x;
  // 相当于把x折半压缩
  res |=  res>>16;
  res |=  res>>8;
  res |=  res>>4;
  res |=  res>>2;
  res |=  res>>1;  // 只要原来x任何一位存在1，当前res[0]结果就为1
  res = ~res;      // 模拟取反（我们只关心res[0]）
  res &= 0x01;     // 将不关心的位清除
  return res;
}

其实挺简单的，使用了折半压缩的思想。

需要的 bit 的个数（难度：⭐⭐⭐⭐）

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
/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5  01100
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4  1011;0100
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
  int sign = x>>31;
  int high16,high8,high4,high2,high1,high0;

  // sign ? -x : x;
  int mix = x^(~x);
  x = ((sign&(x))|((~sign)&(~x)))^mix;
  
  high16 = !!(x>>16);
  x >>= (high16<<4);

  high8 = !!(x>>8);
  x >>= (high8<<3);

  high4 = !!(x>>4);
  x >>= high4<<2;

  high2 = !!(x>>2);
  x >>= high2<<1;

  high1 = !!(x>>1);
  x >>= high1;

  high0 = x; //

  return (high16<<4) + (high8<<3) + (high4<<2) + (high2<<1) + high1 + high0 + 1 ; // WHY
}

浮点数翻倍（难度：⭐⭐⭐⭐）

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
//float
/* 
 * 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) {
  unsigned M = 0x7FFFFF&uf;
  unsigned E = (uf>>23)&0xFF;
  unsigned S = (uf>>31)&0x01;

  if(E==0xFF){
    return uf;
  }
  if(E==0x00){
    M<<=1;
    return (S<<31)|(E<<23)|M;
  }
  E+=1;
  // M<<=1;

  return (S<<31)|(E<<23)|M;
}

浮点数转换为整数（难度：⭐⭐⭐⭐）

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
/* 
 * 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 M = 0x7FFFFF&uf;
  unsigned E = (uf>>23)&0xFF;
  unsigned S = (uf>>31)&0x01;

  int exp = E-127;
  int res;

  if(exp<0)
    return 0;

  if(exp>=31)
    return 0x80000000u;

  // 不会有非规格化数的参与
  res = 1<<23; // 隐含位
  res |= M;
  // 确定小数点的位置
  if(exp<23){
    res >>= (23 - exp);
  }else{
    res <<= (exp - 23);
  }
  // 符号位计算
  if (S)
    res = -res;
  return res;
}

浮点数表示 2 的幂（难度：⭐⭐⭐⭐）

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
/* 
 * 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) {
  
    // 无穷大
    if(x>127){
      return 0xFF<<23;
    }

	// 无法表示
    if(x<-148)
      return 0;

	// exp的指数范围：-126~127
	// 规格化数2^-126
    if(x>=-126) 
      return (x+127)<<23;

    // 大于等于-148，小于-126
    // 非规格化数
    return (1<<(148+x));
}

后续任务

  • 详细理解并完善后续几个函数。

本文参考