禅茶一味

明天再说的自留地

0%

CSAPP lab01

发表于 分类于 Valine：
本文字数： 5.9k 阅读时长 ≈ 5 分钟

知识点：浮点数，整数，逻辑运算，信息存储，补码

CSAPP的第一个lab, 难度不大，代码如下。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
int bitXor(int x, int y) {
  return ~(~(x & ~y) & ~(~x & y)); // (x & ~y) | (~x & y)
}
/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return 1 << 31;
}
//2
/*
 * 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) {
  return !(x ^ ~(tmin()));
}
/* 
 * 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) {
  return !((x & 0xAAAAAAAA) ^ 0xAAAAAAAA);
}
/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return ~x + 1;
}
//3
/* 
 * 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 a = x + (~(0x30) + 1); // x-0x30   0b00110000
	int b = (~x + 1) + 0x39;	// 0x39-x    0b00111001
	int c = a  >> 31;
	int d = b >> 31;
	return !c & !d; // c,d >= 0
}
/* 
 * 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 tmp = !!x; // 1 or 0
  int con = (~tmp + 1); // 0x11111111 or 0x00000000
  return (con & y) | (~con & z);
}
/* 
 * 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 ans = y + (~x + 1);
  int sign = (ans >> 31) & 1;
  int xSign = (x >> 31) & 1;
  int ySign = (y >> 31) & 1;
  int sign_not_equal = xSign ^ ySign;
  return (!sign_not_equal & !sign) | (sign_not_equal & xSign);
}
//4
/* 
 * 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) {
  int ans = x | (~x + 1);
  int sign = ans >> 31; // -1 or 0
  return sign + 1;
}
/* 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的符号
	x = (sign & ~x) | (~sign & x);/*如果x为正则不变，如果x为负则按位取反，因为要去掉符号位计算剩下需要几位，最后return值有+1，不影响
				   例如1111 1111 1111 1111 1111 1111 1111 1101表示-3，其按位取反得0000 0000 0000 0000 0000 0000 0000 0010
				   计算b16+b8+b4+b2+b1+b0=2，return 2+1=3，即-3最少需要3位比特位表示补码（相当101）*/
// 不断缩小范围
	b16 = !!(x >> 16) << 4;//b16用于计数，检查最高十六位(32-16)是否有1，如果有，则!!(x>>16)=1, (1<<4)=0000...10000=2^4=16；如果没有，则为0
	x = x >> b16;//如果有（b16=16,至少需要16位），则将x右移16位；如果没有（b16=0）,x不变
	b8 = !!(x >> 8) << 3;//如果上一步移动了，则检查最高8位(32-16-8)是否有1；如果上一步没移动，则检查最高24位(32-8)是否有1
					 //如果有，b8=2^3=8；如果没有，则为0
	x = x >> b8;//如果有，x右移8位；如果没有，x不变
	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表示加上符号位
}
//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 sign = (uf >> 31) & 1; // 0 or 1
  int e = (uf << 1) >> 24;
  int frac = (uf << 9) >> 9;
  unsigned ans;
  if (e == 0xFF) {
    return uf;
  } else if (e == 0) {
    frac <<= 1;
    ans = (sign << 31) | (e << 23) | frac;
    return ans;
  } else {
    e += 1;
    ans = (sign << 31) | (e << 23) | frac;
    return ans;
  }
}
/* 
 * 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 bias = 0b01111111;
  int sign = (uf >> 31) & 1; // 0 or 1
  int e = (uf << 1) >> 24;
  int frac = (uf << 9) >> 9;
  unsigned ans;
  int E = e - 127;
  if(E < 0) {
    return 0;
  }
  else if (E >= 31) {
      return 1 << 31;
  }
  else {
      frac = frac | 1 << 23;
      if (E < 23) {
          frac >>= (23 - E);
      } else {
          frac <<= (E - 23);
      }
  }
  if (sign) {
      return -frac;
  }
  else {
      return frac;
  }
}
/* 
 * 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) {
    if(x > 127) {
      return 0xFF<<23;
    }
    else if (x < -148) return 0;
    else if (x >= -126){
        int exp = x + 127;
        return (exp << 23);
    } else{
        int t = 148 + x;
        return (1 << t);
    }
}