头部背景图片
Alisa |
Alisa |

CSAPP data Lab

给大家讲个故事,学长说CSAPP的Lab很有意思。

故事讲完了。

哈哈哈哈哈哈

一点都不好玩。

已经写死了,还没写完。

我怀疑我是不是真看过CSAPP

另外复习计算思维的时候看CSAPP效果真差

拒绝考试周,从我做起

本次Lab主要是用来解决计算机中一些数字的问题…很有趣(并不

bitAnd - x&y using only ~ and |

  • Example: bitAnd(6, 5) = 4
  • Legal ops: ~ |
  • Max ops: 8
  • Rating: 1

思路:…太水了

1
2
3
int bitAnd(int x, int y) {
return ~((~x) | (~y));
}

getByte - Extract byte n from word x

  • Bytes numbered from 0 (LSB) to 3 (MSB)
  • Examples: getByte(0x12345678,1) = 0x56
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 6
  • Rating: 2

思路:就是把它右移相应为位数,然后取出来…

出现的问题是我竟然忘记了我应该右移的位数是1*2^3???

1
2
3
int getByte(int x, int n) {
return ((x >> (n << 3)) & (0xff));
}

logicalShift - shift x to the right by n, using a logical shift

  • Can assume that 0 <= n <= 31
  • Examples: logicalShift(0x87654321,4) = 0x08765432
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 20
  • Rating: 3

    思路:主要是为了解决算术右移情况未知的事情,构造一个掩码手动解决

    构造掩码的方法,把第(31-n)置为1,再把剩下的都填成一

1
2
3
4
5
6
7
8
9
int logicalShift(int x, int n) {
int mask = (1 << (31 - n));
mask |= mask >> 1;
mask |= mask >> 2;
mask |= mask >> 4;
mask |= mask >> 8;
mask |= mask >> 16;
return ((x >> n) & mask);
}

bitCount - returns count of number of 1’s in word

  • Examples: bitCount(5) = 2, bitCount(7) = 3
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 40
  • Rating: 4

思路:也是非常神奇了

参考

1
2
3
4
5
6
7
8
9
10
11
12
13
int bitCount(int x) {
int mask1 = 0x55555555;
int mask2 = 0x33333333;
int mask3 = 0x0f0f0f0f;
int mask4 = 0x00ff00ff;
int mask5 = 0x0000ffff;
int result = (x & mask1) + (mask1 & (x >> 1));
result = (result & mask2) + ((result >> 2) & mask2);
result = (result & mask3) + ((result >> 4) & mask3);
result = (result & mask4) + ((result >> 8) & mask4);
result = (result & mask5) + ((result >> 16) & mask5);
return result;
}

bang - Compute !x without using !

  • Examples: bang(3) = 0, bang(0) = 1
  • Legal ops: ~ & ^ | + << >>
  • Max ops: 12
  • Rating: 4
    思路:0和其他数的区别在于符号位,所以…判断一下符号位取反之后是不是跟原来一样就好了
1
2
3
int bang(int x) {
return (0x01) ^ (((x | ((~x) + 1)) >> 31) & 0x01);
}

tmin - return minimum two’s complement integer

  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 4
  • Rating: 1

    思路:emmm

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

n-bit, two’s complement integer.

  • 1 <= n <= 32
  • Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 15
  • Rating: 2

思路:左移右移没区别就好啦

1
2
3
4
int fitsBits(int x, int n) {
int m = 32 + ~n + 1;
return !((x << m >> m) ^ x);
}

divpwr2 - Compute x/(2^n), for 0 <= n <= 30

  • Round toward zero
  • Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 15
  • Rating: 2

思路:因为负数是向上取整正数是向下去整qaq

所以需要给负数加上一个(1<<n)-1

判断一下符号位确定加不加

1
2
3
int divpwr2(int x, int n) {
return ((x + (((x >> 31) & 1) << n)) + (~0) + (!((x >> 31) & 1))) >> n;
}

negate - return -x

  • Example: negate(1) = -1.
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 5
  • Rating: 2

    思路:emmmm

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

isPositive - return 1 if x > 0, return 0 otherwise

  • Example: isPositive(-1) = 0.
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 8
  • Rating: 3

思路:判断是不是大于0就是判一下符号位以及…注意0

1
2
3
int isPositive(int x) {
return ((((x >> 31) | (!x)) ^ 1) & 0x01);
}

isLessOrEqual - if x <= y then return 1, else return 0

  • Example: isLessOrEqual(4,5) = 1.
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 24
  • Rating: 3

思路:判断y-x是不是大于等于0,要判断是不是越界,所以需要判断是不是会出现极端情况然后在搞

1
2
3
4
5
6
7
int isLessOrEqual(int x, int y) {
int flagx = (x >> 31) & 0x01;
int flagy = (y >> 31) & 0x01;
int num = y + (~x + 1);
return ((((flagx) && (!flagy))) |
(!((!flagx) && (flagy))) & ((num >> 31) ^ 1));
}

ilog2 - return floor(log base 2 of x), where x > 0

  • Example: ilog2(16) = 4
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 90
  • Rating: 4
    思路:观察可得(并不
    一个数的log2这个数二进制出现1的最高位,so,统计最高为+bitcount
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int ilog2(int x) {
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    int mask1 = 0x55555555;
    int mask2 = 0x33333333;
    int mask3 = 0x0f0f0f0f;
    int mask4 = 0x00ff00ff;
    int mask5 = 0x0000ffff;
    int result = (x & mask1) + (mask1 & (x >> 1));
    result = (result & mask2) + ((result >> 2) & mask2);
    result = (result & mask3) + ((result >> 4) & mask3);
    result = (result & mask4) + ((result >> 8) & mask4);
    result = (result & mask5) + ((result >> 16) & mask5);
    return result - 1;
    }

接下来是我还没有做完的浮点数qaq

float_neg - Return bit-level equivalent of expression -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 representations of
  • single-precision floating point values.
  • When argument is NaN, return argument.
  • Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
  • Max ops: 10
  • Rating: 2

思路:特判NAN,符号位取反

1
2
3
4
5
6
unsigned float_neg(unsigned uf) {
unsigned ans = uf ^ 0x80000000;
if (((uf & 0x7f800000) == 0x7f800000) && (uf & 0x007fffff))
ans = uf;
return ans;
}

float_i2f - Return bit-level equivalent of expression (float) x

  • Result is returned as unsigned int, but
  • it is to be interpreted as the bit-level representation of a
  • single-precision floating point values.
  • Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
  • Max ops: 30
  • Rating: 4
1
咕咕咕

float_twice - 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

思路:特判NAN,无穷大

如果是非规格化数,阶码为0,后面直接*2,即使越界也不会有什么大问题TAT

如果是规格数,直接阶码+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
unsigned float_twice(unsigned uf) {
if ((((uf & 0x7f800000) == 0x7f800000)) || uf == (0x80000000))
return uf;
int sign = (uf >> 31) & 0x01;
int exponent = (uf >> 23) & 0xff;
int frcation = uf & 0x007fffff;

if ((exponent == 0x00000000)) {
frcation <<= 1;
} else {
exponent += 1;
}
return (sign << 31) | (exponent << 23) | frcation;
}

除掉我咕咕咕掉的那个(我不想写了qaq),这个Lab 假设做完了

(我要被赶出组了…qaq)