CSAPP Datalab

发表于 | 分类于 |

CSAPP大概都过了一遍，但是很多东西不实践一下理解还是不到位，趁这个假期尽量把11个lab做一下。

0x1 bitXor

只用位运算实现一个异或

1
2
3
4
5
6
7
8
9
10
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
  return ~(~x&~y)&~(x&y);
}

思路

~(x&y)是把x和y中同时为1的位置为0,~(~x&~y)是把x和y同时为0的位置为0，其他位都是1，然后再把两个相与，组合一下。

0x2 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) {
  return 1<<31;

}

思路

根据补码的规则，只有符号位为1时，这个数最小为-2^31^。

0x3 isTmax

返回1，如果输入的x是补码中的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * 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 i = x + 1;
  x = x + i;
  x = ~x;
  i = !i;
  x = x + i;
  return !x;
}

思路

首先补码的最大值就是符号位为0，其它位为1，我们要做的就是把这个数转化成0。这个数有个特点就是将这个数+1然后再加自己等于-1，然后再取反就等于0了，但是-1如此操作也可以得到同样的结果，所以在x = ~x后面几行就是为了排除这种情况。

0x4 allOddBits

如果所有奇数位都为1，就返回1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* 
 * 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 + (0xaa<<8);
    mask += mask<<16;
    return !((x&mask)^mask);
}
/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */

思路

构造出0xaaaaaaaa，然后相与保留该数所有奇数位上为1的位，最后再异或，如果全为0则满足条件。

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

思路

思路，变负就是按位取反再+1.

0x6 isAsciiDignit

判断输入的ascii值是否大于等于字符0的小于等于字符9的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * 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) {
  int sign = 1<<31;
  int lower = ~0x30;
  int higher = ~(sign|0x39);
  lower = sign&(lower+x+1)>>31;
  higher = sign&(higher+x)>>31;
  return !(lower|higher);
}

思路

  • lower是加上比0x30小会是负数的数字
  • higher是加上比0x39大的数会是负数的数字
  • 最后看看lower和higher是否同时满足条件

0x7 conditional

用位运算符实现三目运算

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

思路

先把x转化成真值0或者1，然后注意0和1的特性，0取负以后还是0，1取负以后是-1也就是全1。最后用0和全1对y和z进行选择。

0x8 isLessOrEqual

判断参数1是否小于等于参数2

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 negX = ~x + 1;
  int addX = negX + y;
  int checkSign = (addX>>31)&1;
  int sign = 1<<31;
  int xLeft = x&sign;
  int yLeft = y&sign;
  int same = xLeft ^ yLeft;
  same = (same>>31)&1;
  return ((!same)&(!checkSign))|(same&(xLeft>>31));
}

思路

分两种情况：

  1. x和y符号不一样，那么x如果是负号的话就可以返回1
  2. x和y符号一样，那么就看y-x的符号是正是负

0x9 logicalNeg

实现逻辑非

1
2
3
4
5
6
7
8
9
10
11
/* 
 * 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) {
  return (((~x+1)|x)>>31) + 1;
}

思路

还是利用0的特性，只有0和它的补码符号位相与为全零，其它的符号位都会为1。这里+1是考虑到了最小值的特点，它和它的补码符号位都为1。

0x10 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
/* 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 b16,b8,b4,b2,b1,b0;
  int sign = x>>31;
  x = (sign&~x)|(~sign&x);

  b16 = !!(x>>16)<<4;
  x = x>>b16;
  b8 = !!(x>>8)<<3;
  x = x>>b8;
  b4 = !!(x>>4)<<2;
  x = x>>b4;
  b2 = !!(x>>2)<<1;
  x = x>>b2;
  b1 = !!(x>>1);
  x = x>>b1;
  b0 = x;
  return b16+b8+b4+b2+b1+b0+1;
}

思路

  • 如果是一个正数，那么只要找到它最高的那个1，然后再加上一个符号位就行了
  • 如果是一个负数，那么找到它最高位的0然后再加上一个符号位就行，因为从符号位往右到第一个0的1都没意义。
  • 所以如果x是正数，则不变，如果x是负数就给x取反
  • 然后依次缩小范围，返回结果。

浮点数简介

IEEE 浮点标准用 V=(-1)^s^M2^E^的形式表示一个数

  • 符号, s 决定这个数是正数(s = 0)，还是负数(s = 1)
  • 尾数 M 是一个二进制小数, 它的范围是 1 ~ 2-e，(标准化数)或者是0 ~ 1-e（非标准化数)
  • 阶码 E 的作用是对浮点数加权

单精度浮点格式 s=1位，E=8位，M=23位

双精度浮点格式 s=1位，E=11位, M=52位

0x11 floatScale2

求2乘一个浮点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//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) {
  int exp = (uf&0x7f800000)>>23;
  int sign = uf&(1<<31);
  if(exp == 0)  return uf<<1|sign;
  if(exp == 255) return uf;
  exp++;
  if(exp == 255) return 0x7f800000|sign;
  return (exp<<23)|(uf&0x807fffff);
}

思路

  • 如果是非规格化数，直接乘2返回
  • 如果是无穷大或者NaN，返回原值
  • 再判断乘2后有没有溢出，如果没有溢出就返回更改exp后的uf
  • 如果有溢出就返回无穷大

0x12 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
/* 
 * 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 s = uf>>31;
  int exp = ((uf&0x7f800000)>>23)-127;
  int frac = (uf&0x007fffff)|0x00800000;
  if(!(uf&0x7fffffff)) return 0;
  
  if(exp>31)  return 0x80000000;
  if(exp<0)   return 0;

  if(exp>23)  frac<<=(exp-23);
  else  frac >>= (23-exp);

  if(!((frac>>31)^s)) return frac;
  else if(frac>>31) return 0x80000000;
  else return ~frac+1;
}

思路

  • 首先考虑特殊情况，如果是0则返回0
  • 如果直接阶码部分就溢出了就返回 0x80000000
  • 如果是小于0的也返回0（因为尾码的部分肯定不会大于2）
  • 然后判断结果跟原来符号一样不一样
  • 不一样的话，然后溢出是一种情况
  • 原来是负数也是一种情况

0x13 floatPower2

求2.0^x^

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* 
 * 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) {
    int INF = 0xff<<23;
    int exp = x + 127;
    if(exp <= 0)  return 0;
    if(exp >= 255)  return INF;
    return exp << 23;
}

思路

就直接改exp的值呗，把exp改成x+127就行，再看看是不是无穷大，是不是0就行了。

尾数部分全0，代表1.

-------------本文结束感谢您的阅读-------------
+ +