GCC314's BLOG
0%

CSAPP Labs | Datalab (Self study ver.)

Posted on Edited on In

感觉书看不进去惹，整点Lab做做。

Lab可以从这里下载

第一个做的是DataLab，对应书上的第二章。

运用限定种类和个数的运算符，来实现一个函数。主要考察了整型和浮点型在计算机中的表示和处理。

INTEGER PART

考察整型。需遵守以下规则：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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.

bitXor

1
2
3
4
5
6
7
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */

这三个位操作是独立的，所以只需考虑 $$ (x,y) \in {0,1}^2 $$ 的情况。可知结果：

1
2
3
int bitXor(int x, int y) {
	return ~(~(~x&y)&~(x&~y));
}

tmin

1
2
3
4
5
6
/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */

求int变量能表出的最小值的补码，即：

1
2
3
int tmin(void) {
	return 1<<31;
}

isTmax

1
2
3
4
5
6
7
/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */

判断x是否是 $$ 2^{31}-1 $$ ，即0x7fffffff。由于符号个数限制，没办法直接检验各位，那么我们得找这个数的别的特征。

注意到(int)(0x7fffffff + 1) == (1 << 31)，而 0x7fffffff ^ (1 << 31) == 0xffffffff == ~0，我们可以知道~(x ^ (x + 1)) == 0是x == 0x7fffffff的充分条件。

满足第一个条件的数还有0xffffffff，我们排除掉他，即要求~x != 0。

用!把0和非0数分别映射到1和0，再用&处理条件的交，可以得到最终式子：

1
2
3
int isTmax(int x) {
	return (!((~x)^(x+1)))&(!!(~x));
}

allOddBits

1
2
3
4
5
6
7
8
/* 
 * 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
 */

显然等价于x ^ 0xAAAAAAAA == 0，但是整数部分练习只能用0~255的常数。

我们转换一下，每次检查8位：

1
2
3
int allOddBits(int x) {
	return !(((x&0xAA)&(x>>8&0xAA)&(x>>16&0xAA)&(x>>24&0xAA))^0xAA);
}

negate

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

由补码可知：

1
2
3
int negate(int x) {
	return ~x+1;
}

isAsciiDigit

1
2
3
4
5
6
7
8
9
/* 
 * 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
 */

三个条件的交：

  1. 第6位之前都为0
  2. x & 0x30 == 0x30

此时 0x30 <= x <= 0x3f

将可行的答案分为两种情况，0x30 <= x <= 0x37和0x38 <= x <= 0x39。

第一种情况等价于x | 0x08 == 0，第二种情况(x & 0xF)的中间两位必为0，即(x & 0xF) | 0x9 == 0x9。

综合可得：

1
2
3
int isAsciiDigit(int x) {
	return (!((x|0x3F)^0x3F))&(!((x&0x30)^0x30))&((!(x&0x08))|(!(((x&0x0F)|0x09)^0x09)));
}

conditional

1
2
3
4
5
6
7
/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */

用!将整数x映射成0/1，然后-1，映射为p = ~0/0。

然后就是将p和yz进行一些交并的操作：

1
2
3
4
int conditional(int x, int y, int z) {
	int p = !x+~0;
	return (y&p)|(z&~p);
}

isLessOrEqual

1
2
3
4
5
6
7
/* 
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */

比较两个数，先看符号位，如果不同那么正肯定大于负。

如果两个同号，那么abs(x - y) 小于等于 $$ 2 ^ {31} - 1 $$，在int范围内。

那么我们用y + ~x + 1等价于y - x，然后看它的符号位。

综合如下：

1
2
3
4
int isLessOrEqual(int x, int y) {
	int p = (y^x)>>31;
	return (p&(!(y>>31)))|(!p&(!((y+~x+1)>>31)));
}

logicalNeg

1
2
3
4
5
6
7
8
/* 
 * 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 
 */

考虑0和非0的不同。

注意到x ^ (-x)的符号位为1等价于x != 0，可以从这里入手：

1
2
3
int logicalNeg(int x) {
	return ((~(x|(~x+1)))>>31)&1;
}

howManyBits

1
2
3
4
5
6
7
8
9
10
11
12
/* 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
 */

最难的一道。

从题意开始就不能理解，呃呃了。

进行了一些网络冲浪终于理解了。

1
2
3
0000 0000 0000 0000 0000 0000 0000 1100		12
1111 1111 1111 1111 1111 1111 1111 1011		-4
0000 0000 0000 0000 0000 0000 0000 0100		~(-4)

就是要找他的补码在前面去掉了最多多少位之后，还等于原数。

将负数取反之后，问题转化为找到highbit(y)。

从高到低枚举highbit(y)的每个位，

如果highbit(y) >= (1 << k)，即highbit(y) >> k & 1 != 0，

则y >> (1 << k) != 0，否则y >> (1 << k) == 0。

其中若highbit(y) >= (1 << k)，接下来要检测低位、即k - 1位。

需测试highbit(y) >= (1 << k) + (1 << (k - 1))，即highbit(y >> (1 << k)) >= (1 << (k - 1))。

如此迭代。

注意处理0和~0的特殊情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int howManyBits(int x) {
    int s16,s8,s4,s2,s1,s;
    int t1 = ((!x)<<31)>>31;
    int t2 = ((!~x)<<31)>>31;
    int op = x^(x>>31);
    s16 = (!!(op>>16))<<4;
    op = op>>s16;
    s8 = (!!(op>>8))<<3;
    op = op>>s8;
    s4 = (!!(op>>4))<<2;
    op = op>>s4;
    s2 = (!!(op>>2))<<1;
    op = op>>s2;
    s1 = (!!(op>>1));
    op = op>>s1;
    s = 2 + s16 + s8 + s4 + s2 + s1;
    return (t2&1)|((~t2)&((t1&1)|((~t1)&s)));
    return 0;
}

FLOAT PART

考察浮点型，条件有放宽：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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.

floatFloat2Int

1
2
3
4
5
6
7
8
9
10
11
12
/* 
 * 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
 */

分类讨论即可。细节比较多。

1
2
3
4
5
6
7
8
9
10
11
12
int floatFloat2Int(unsigned uf) {
    unsigned s = uf & 0x80000000;
    unsigned e = uf & 0x7f800000;
    unsigned f = (uf & 0x7fffff) | 0x800000;
    unsigned ee = e >> 23;
    if(ee <= 126) return 0;
    if(ee > 157) return 0x80000000u;
    if(ee >= 150) f <<= (ee - 150);
    else f >>= (150 - ee);
    if(s) return -f;
    return f;
}

floatPower2

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
 * 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
 */

对x分类讨论，要么就是非规格化的、小数部分有个1，要么是规格化的、指数部分为x+Bias：

1
2
3
4
5
6
unsigned floatPower2(int x) {
    if(x > 127) return 0x7f800000;
    if(x >= -126) return (x + 127u) << 23;
    if(x >= -149) return 1u << (x + 149);
    return 0;
}