CSAPP datelab（伪）报告

发表于

CSAPP的第一个Lab

CSAPP datelab

读CSAPP这本书的过程中出现了很多的困难，同时，我读这本书时间耗时很长但是
又完全没有弄懂很多东西，在迷迷糊糊的把书看完一遍后开始准备做配套的lab已以及准备南大的计算机系统配套的实验在这个过程中重新把书看一遍。

另外做这个Lab感觉难度不小，后面可能要补补离散

datelab分为3个部分，位操作，整数操作，浮点操作

位操作

第一题

1
2
3
4
5
6
7
/* 1 √
 * 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));
}

第二题

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

提取一个数字的n字节,这里使用掩码0xFF来取一个字节

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

第三题

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

取出高位，然后把高位变为0（使用掩码）
最后把取出的高位放回去

1
2
3
4
5
6
7
int logicalShift(int x,int n)
{
  int a=x&(1<<31);
  int b=x&(~(1<<31));
  b>>=n;
  b |= (a>>n)&(1<<32+~n)/*大坑.....注意a也是逻辑右移所以要用掩码取位*/
}

第四题

/* 4 √

  • bitCount - returns count of number of 1’s in word
  • Examples: bitCount(5) = 2, bitCount(7) = 3
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 40
  • Rating: 4

ACM做题的时候分治法的时候讲过，把32位的数分为16组，每组的两个数相加，得到16个数，然后重复即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
int bitCount(int x) {
    int bits = 0;
    int mask = 0x1 | (0x1 << 8) | (0x1 << 16) | (0x1 << 24);
    bits += (x & mask);
    bits += ((x >> 1) & mask);
    bits += ((x >> 2) & mask);
    bits += ((x >> 3) & mask);
    bits += ((x >> 4) & mask);
    bits += ((x >> 5) & mask);
    bits += ((x >> 6) & mask);
    bits += ((x >> 7) & mask);
    return (bits & 0xFF) + ((bits >> 8) & 0xFF) + ((bits >> 16) & 0xFF) + ((bits >> 24) & 0xFF);
}

第五题

1
2
3
4
5
6
7
/* 5 √
 * bang - Compute !x without using !
 *   Examples: bang(3) = 0, bang(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4
 */

计算数字的逆（！）
很巧妙，0的特征，0和0的相反数首位按位或为0

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

补码运算

第六题

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

第七题

1
2
3
4
5
6
思路：
分正负数，分别前面为0或1，只需判断32-n是否全0或1，通过掩码取这些位即可
```c
int fitsBits(int x, int n) {
    return !((x << (33 + ~n) >> (33 + ~n))^x);
}

第八题

题意：数除以2^n
对于正数直接算术右移即可，对于负数

第九题

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

第十题

判断正数，高位为0避开0；

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