前言

终于开始学大名鼎鼎的CSAPP，一开始配环境就把我配得想退坑。。幸亏配好了

lab1真的很难想，实在想不出来就瞅眼别人的思路，然后又再嗯造自己的

所有注释都是作者一点一点想一点一点敲出来的喵

环境配置参考：
CSAPP LAB —— 0. 实验环境搭建_何人听我楚狂声 csdn-CSDN博客

代码思路参考：
CSAPP 之 DataLab详解，没有比这更详细的了 - 知乎 (zhihu.com)
cSAPP lab1 datalab - 知乎 (zhihu.com)

完整代码

1. bitXor

1
2
3
4
5
6
7
8
9
10
11
12
/* 
 * 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)
  // 由德摩根律
  return (~(x & y)) & (~(~x & ~y)) ;
}

2. 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) {
  // int 占 4 bite即 32 bit
  return 1 << 31;
}

3. isTmax

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) {
  // 当x = 0111 1111时，令y = ~x = 1000 0000，则有 2y = 0

  // 但是, 令2y = 0，得y = 1000 0000 或 0000 0000
  // 1000 0000对应的x为 0111 1111，0000 0000对应的x为1111 1111
  // 即，当x = 1111 1111 时，y = 0000 0000，也有 2y = 0
  // 因此需要构造条件过滤x = 1111 1111 的情况

  // 令z = !y，当x = 0111 1111时，z = 0, 当x = 1111 1111时，z = 1
  // 因此只有当x = 0111 1111时，才有2y + z = 0
  int y = ~x; 
  int z = !y; 
  return !(y + y + z);
}

4. allOddBits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* 
 * 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) {
  // 0x55 = 0101 0101 所有偶数位为1
  // x | 0x55555555 中偶数位全为1，
  // 那么，当且仅当x的奇数位全为1时，结果为0xffffffff
  // 对0xffffffff按位取反得0，再取反得到真
  int temp = 0x55;
  temp = temp + (temp << 8);
  temp = temp + (temp << 16);
  return !~(x | temp);

  // 0x55555555 其实也是 ~(0xAAAAAAAA)，按照德摩根律
  // return !(~x & 0xAAAAAAAA);
  // 这种写法也是正确的
}

5. negate

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  // 求负数得操作是取反加一
  // 取反：1111 1111 - x = -1 -x
  // 加一：(-1 - x) + 1 = -x
  return ~x + 1;
}

6. isAsciiDigit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* 
 * 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 >= 0x30 && x <= 0x39
  // 那么 x - 0x30 >= 0, x - 0x39  <= 0

  // x - 0x30 >= 0, x - 0x39 - 1 < 0
  // 又 -0x30 = ~0x30 + 1, -0x39 = ~0x39 + 1
  // 即 (x + ~0x30 + 1) >> 31 = 0, (x + ~0x39) >> 31 = -1  
  // 注意：c语言右移补符号位(坑死我了)
  
  int judgeUpper = (x + ~0x39) >> 31; 
  int judgeLower = (x + ~0x30 + 1) >> 31;
  return !(~judgeUpper | judgeLower); //当且仅当judgeUpper为-1而且judgeLower为0时,返回true
}

7. conditional

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 
 * 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) {
  // 先得到x的布尔值：0或者1：x = !!x
  // 全0或全1会更好处理，全0就是0，全1是-1
  // 取反加一得相反数：x = ~x + 1 

  x = ~(!!x) + 1;
  return (x & y) | (~x & z);  //确实很牛逼
}

8. isLessOrEqual

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 
 * 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) {
  // 跟isAsciiDigit差不多
  // x <= y 得 x - y <= 0  得 x + ~y < 0 得(x + ~y) >> 31 = -1
  // 当 x 和 y 同号时 两数相减不会出现溢出 异号则会 所以需要判断符号
  int flag = (x ^ y) >> 31; // x y同号时，flag = 00..00 否则为 11..11

  // 当 x 和 y 同号时
  int signEq = !~((x + ~y) >> 31 );  // 满足 x <= y 时 signEq = 1

  // 当 x 和 y 不同号时，y是正数时返回true
  int signNeq = !(y >> 31);           // 满足 x <= y 时 signNeq = 1

  // 当 flag = 00..00，flag & signEq = signEq, ~flag & signNeq = 0, 结果为signEq
  // 当 flag = 11..11，flag & signEq = 0, ~flag & signNeq = signNeq, 结果为signNeq
  return (~flag & signEq) | (flag & signNeq); // 受conditional的启发，很牛逼(再次)
}

9. logicalNeg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 
 * 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) {

  // 0要变成1，直接加一呗
  // 其他数要变成0，还得跟上述操作兼容qwq
  // 思路：有一个操作能使0变成0，除了0的其他所有数变成-1，得到的结果再加一

  // 当x不为0时, x | -x 符号为一定为1, 再右移31位得到-1
  // 当x为0时, x | -x = 0, 右移31位还是0
  return ((x | (~x + 1)) >> 31) + 1;
}

10. howManyBits

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) {
  // 101 表示 -4+2+1 = -3, 1101表示 -8+4+2+1 = -3, 11101表示 -16+8+4+2+1 = -3
  // 由此可见, 在负数的补码前面加很多位1, 得到的值是一样的, 
  // 同理, 去掉前面重复的1，所表达的值也是一样的
  // 因此, 负数找最高位0就能确定需要多少位就能表达这个数
  // 总之：正数找最高位1，负数找最高位0
  int b_0, b_1, b_2, b_4, b_8, b_16;
  int sign = x >> 31; 
  x = (~sign & x) | (sign & ~x); // 正数负数统一处理, 转化为找x的最高位1

  // 别人的办法真是十分巧妙啊（
  b_16 = !!(x >> 16) << 4;  // b_16 = (高16位有1)? 16 : 0
  x = x >> b_16;            // 高16位有1就继续看高16位, 没有就看后面的
  b_8 = !!(x >> 8) << 3;    // 同理 b_8 = (高8位有1)? 8 : 0
  x = x >> b_8;
  b_4 = !!(x >> 4) << 2;    
  x = x >> b_4;
  b_2 = !!(x >> 2) << 1;    
  x = x >> b_2;
  b_1 = !!(x >> 1);         
  x = x >> b_1;
  b_0 = x;                  

  return 1 + b_0 + b_1 + b_2 + b_4 + b_8 + b_16;  // 1 是符号位
}

11. 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
/* 
 * 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) {
  // 单精度浮点数32位 符号位1 指数位8 数值位23

  // 取符号, 铁定用的着
  int filter = 1 << 31;
  int sign = uf & filter ; 
  int val;

  // 先判断传入的值是否为非规格化值, 进行特殊处理
  // 只看指数位：(filter >> 8) ^ filter = 0111 1111 1000 00..
  int exp = (((filter >> 8) ^ filter) & uf) >> 23;   
  if (!exp)
    return (uf << 1) | sign;  // 指数为为0, 可以向指数为1平滑转化, 太绝了
  if (exp == 255)
    return uf;

  ++exp;                      // 指数+1就是把值乘2
  if(exp == 255)
    return ((filter >> 8) ^ filter) | sign; // 判断越界

  // 取数值位
  val = ~(filter >> 8) & uf;
  return sign | (exp << 23) | val;
}

12. floatFloat2Int

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
/* 
 * 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) {
  // 同上, 先判断非规格化值
  int filter = 1 << 31;
  // int sign = uf & filter;
  int exp = (((filter >> 8) ^ filter) & uf) >> 23;
  int val, sign;

  exp = exp - 127;  // 添加bias 
  if(exp < 0)
    return 0;
  if(exp > 31)
    return filter;  // 超过int范围的数按要求返回0x800..00u 包括inf和NaN

  val = (~(filter >> 8) & uf) | (1 << 23); // 取数值位, 加上隐藏的1
  // 这里的val已经是1.*** 小数点向右移了23位的结果了, 因此只需要再向右移exp - 23 位
  if(exp > 23)
    val = val << (exp - 23);
  else 
    val = val >> (23 - exp); 

  // 负数用补码表示
  sign = filter & uf;
  if(!sign)
    return val;
  else 
    return ~val + 1;
}

13. floatPower2

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
/* 
 * 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) {
  // 求2^x = 1.0 * 2^x, 数值部分为0, 指数部分为x

  // float 不能超过 2^127
  // x过大使超过浮点数表示范围时, 按要求返回inf = 0x7f800000
  // x过小按要求返回0
  if(x > 127)
    return 0x7f800000;
  if(x < -126)
    return 0;
  return ((x + 127) << 23) ; // 注意加上bias = 127
}

运行结果

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
root@Andrew:/mnt/d/.c/csapp/datalab-handout# ./dlc bits.c
root@Andrew:/mnt/d/.c/csapp/datalab-handout# make clean
rm -f *.o btest fshow ishow *~
root@Andrew:/mnt/d/.c/csapp/datalab-handout# make ./btest
gcc -O -Wall -m32 -lm -o btest bits.c btest.c decl.c tests.c
btest.c: In function ‘test_function’:
btest.c:334:23: warning: ‘arg_test_range’ may be used uninitialized [-Wmaybe-uninitialized]
  334 |     if (arg_test_range[2] < 1)
      |         ~~~~~~~~~~~~~~^~~
btest.c:299:9: note: ‘arg_test_range’ declared here
  299 |     int arg_test_range[3]; /* test range for each argument */
      |         ^~~~~~~~~~~~~~
root@Andrew:/mnt/d/.c/csapp/datalab-handout# ./btest
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