Zth's Blog

记录学习路上的点滴

0%

data lab

CSAPP lab1: data lab

自己做完后的bits.c文件

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
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
/* 
* CS:APP Data Lab
*
* <Please put your name and userid here>
*
* bits.c - Source file with your solutions to the Lab.
* This is the file you will hand in to your instructor.
*
* WARNING: Do not include the <stdio.h> header; it confuses the dlc
* compiler. You can still use printf for debugging without including
* <stdio.h>, although you might get a compiler warning. In general,
* it's not good practice to ignore compiler warnings, but in this
* case it's OK.
*/

#if 0
/*
* Instructions to Students:
*
* STEP 1: Read the following instructions carefully.
*/

You will provide your solution to the Data Lab by
editing the collection of functions in this source file.

INTEGER CODING RULES:

Replace the "return" statement in each function with one
or more lines of C code that implements the function. Your code
must conform to the following style:

int Funct(arg1, arg2, ...) {
/* brief description of how your implementation works */
int var1 = Expr1;
...
int varM = ExprM;

varJ = ExprJ;
...
varN = ExprN;
return ExprR;
}

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.


You may assume that your machine:
1. Uses 2s complement, 32-bit representations of integers.
2. Performs right shifts arithmetically.
3. Has unpredictable behavior when shifting if the shift amount
is less than 0 or greater than 31.


EXAMPLES OF ACCEPTABLE CODING STYLE:
/*
* pow2plus1 - returns 2^x + 1, where 0 <= x <= 31
*/
int pow2plus1(int x) {
/* exploit ability of shifts to compute powers of 2 */
return (1 << x) + 1;
}

/*
* pow2plus4 - returns 2^x + 4, where 0 <= x <= 31
*/
int pow2plus4(int x) {
/* exploit ability of shifts to compute powers of 2 */
int result = (1 << x);
result += 4;
return result;
}

FLOATING POINT CODING RULES

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.


NOTES:
1. Use the dlc (data lab checker) compiler (described in the handout) to
check the legality of your solutions.
2. Each function has a maximum number of operations (integer, logical,
or comparison) that you are allowed to use for your implementation
of the function. The max operator count is checked by dlc.
Note that assignment ('=') is not counted; you may use as many of
these as you want without penalty.
3. Use the btest test harness to check your functions for correctness.
4. Use the BDD checker to formally verify your functions
5. The maximum number of ops for each function is given in the
header comment for each function. If there are any inconsistencies
between the maximum ops in the writeup and in this file, consider
this file the authoritative source.

/*
* STEP 2: Modify the following functions according the coding rules.
*
* IMPORTANT. TO AVOID GRADING SURPRISES:
* 1. Use the dlc compiler to check that your solutions conform
* to the coding rules.
* 2. Use the BDD checker to formally verify that your solutions produce
* the correct answers.
*/


#endif
//1
/*
* bitXor - x^y using only ~ and &
* Example: bitXor(4, 5) = 1
* Legal ops: ~ &
* Max ops: 14
* Rating: 1
*/
int bitXor(int x, int y) {
int a = ~(x & y); // 10, 01, 00
int b = ~((~x) & (~y)); // 10, 01, 11
return a & b; // 10, 01
}

/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
int x = 1;

return x << 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) {
int n1 = ~0;
return (!(x ^ (x + 1) ^ n1)) & (!!(x ^ n1));
}
/*
* 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 c = 170;
int d = (c << 8) + c;
d = (d << 8) + c;
d = (d << 8) + c;
//line 185, 186 can be changed to: int f = (d << 16) + d, and d in line 188 change to f
return !((x & d) ^ d);
}
/*
* 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 res = !(x >> 6);
int a = !((x & 12) ^ 12);
int b = !((x & 10) ^ 10);
int c = a | b;

res = res & (!((x & 48) ^ 48));
return res & (c ^ 1);
}
/*
* 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 a = ((!x) << 31) >> 31; // if x is 0, a is all 1s; else a is all 0s
int b = a & (y ^ z); // if x is 0, b = y ^ z; else b = 0

return b ^ y; // if is 0, return z; else return y
}
/*
* 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 nx = (~x) + 1; // -x
int xs = (x >> 31) & 1; // sign of x
int ys = (y >> 31) & 1; // sign of y
int diff = xs ^ ys; // different sign or not
int less = xs & diff; // x is less than y
int subs = ((y + nx) >> 31) & 1; // sign of the subtraction

return less | ((!diff) & (!subs)); // two proper situation
}
//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) {
return (((x | ((~x) + 1)) >> 31) & 1) ^ 1; // if x != 0, then sign of (x | -x) is 1
// return ((x | ((~x) + 1)) >> 31) + 1; use less ops, achieve the same goal
}
/* 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) {
return 0;
}
//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) {
unsigned e1 = 2139095040;
unsigned e = e1 & uf;
unsigned s22 = 8388607;
unsigned m = s22 & uf;

if(!(e ^ e1)) return uf;

if(e == 0) return ((uf >> 23) << 23) + (m << 1);

return uf + (1 << 23);
}
/*
* 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 = 127;
unsigned sign = (uf >> 31) & 1;
int e = (uf >> 23) & 255;
int m = uf & 8388607;
int E = e - bias;
int len = E + 1;
int M = m;
int rb = 0;

if(e == 255) return 0x80000000u;
if((!e) || (E < 0)) return 0;
if(len > 32 || (len == 32 && sign)) return 0x80000000u;
if(E <= 23) rb = 23 - E;

M = M >> rb;
M = M << E;
M = M + (1 << E);

if(sign) M = (~M) + 1;

return M;
}
/*
* 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 0x7f800000;
if(x >= -126)
{
unsigned exp = x + 127;

return exp << 23;
}
if(x >= -149)
return 0x1 << (x + 149);
return 0;
}

其中howMangBits不会, 最后一个floatPower2做的是对的, 但是不知道为什么会超时

好像凭空多出来两行东西, 不知道为什么。

后续

小问题

后续去网上查了查, 可能最后一个的数据组数有点多, 需要把btest.cw文件中的define TIMEUOT_LIMIT 10改成20, 或者使用命令

1
./btest -T 20

也是可以的, 结果如下

题解

bitXor

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

第9行的语句将x中为1,y中为0、x中为0, y中为1、xy中都为0的位置为1

第10行的语句将x中为1,y中为0、x中为0, y中为1、xy中都为1的位置为1

两者取&就得到了需要的结果

tmin

1
2
3
4
5
6
7
8
9
10
11
/* 
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
int x = 1;

return x << 31;
}

比较水, 不赘述了

isTmax

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

这个就需要我们发现Tmax的特质:符号位为0, 其他位全为1

我们知道从二进制位的意义上讲, $x + 1$实际上会把x最低位的0变成1, 进一步说$x \oplus (x + 1)$会将包括最低位的0和其更低位都变成1, 而更高位都变成0

我们刚才说了只有Tmax最低位0位于符号位(最高位),那操作完后就不会有为0的位, 所以好像只有$Tmax \oplus (Tmax + 1) = -1$, 但是实际上$-1$也是可以的, 因为$-1$连0都没有, 所以加一个判断看看是不是$-1$

allOddBits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 
* 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 c = 170;
int d = (c << 8) + c;
d = (d << 8) + c;
d = (d << 8) + c;
//line 185, 186 can be changed to: int f = (d << 16) + d, and d in line 188 change to f
return !((x & d) ^ d);
}

也没什么含金量, 看了别人的博客发现自己的写法可以优化一下

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

更没有操作可言

isAsciiDigit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 
* 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 res = !(x >> 6); // 看看前26位有没有1, 有就不行, 肯定大了
int a = !((x & 12) ^ 12);
int b = !((x & 10) ^ 10);
int c = a | b;

res = res & (!((x & 48) ^ 48));
return res & (c ^ 1);
}

给定的范围是$0x110000 - 0x111001$, 也就是说x的前26位不能有1

如果上述条件满足, 继续判断后六位是不是也符合条件, 这里写的顺序有点不对(因为lab强制规定必须定义完所有变量才能有别的操作, 否则prase error)

我们用第16行判断x是不是$0x11xxxx$的形式

然后我们再判断后四位, 我们可以看出后四位是$11xx$或者$1x1x$是不行的, 别的都行, 所以用12、13行判断一下

然后整合一下就好了

conditional

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
* 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 a = ((!x) << 31) >> 31; // if x is 0, a is all 1s; else a is all 0s
int b = a & (y ^ z); // if x is 0, b = y ^ z; else b = 0

return b ^ y; // if is 0, return z; else return y
}

这题我觉得还是很有思维含量的, 刚开始卡了一会, 觉得应该可以用异或操作来解决, 就想出来了

看看别人的写法:

1
2
3
4
5
6
7
8
9
10
11
12
/* 
* conditional - same as x ? y : z
* Example: conditional(3,4,5) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int conditional(int x, int y, int z) {
x = !!x;
x = ~x+1;
return (x&y)|(~x&z);
}

这个感觉应该更容易想一点, 而且这里有一个技巧, 就是关于把x变成全0或者全1的操作, 应该记住

isLessOrEqual

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 
* 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 nx = (~x) + 1; // -x
int xs = (x >> 31) & 1; // sign of x
int ys = (y >> 31) & 1; // sign of y
int diff = xs ^ ys; // different sign or not
int less = xs & diff; // x is less than y
int subs = ((y + nx) >> 31) & 1; // sign of the subtraction

return less | ((!diff) & (!subs)); // two proper situation
}

根据$y - x$的正负性判断相对大小

但是当x, y符号位不同时可能会溢出, 但是显然符号位不同可以直接判断不用运算

然后两种情况了, 一种是x负y正, 一种是符号位相同但是差非负; 两种情况或一下就可以了

logicalNeg

1
2
3
4
5
6
7
8
9
10
11
12
/* 
* 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 | ((~x) + 1)) >> 31) & 1) ^ 1; // if x != 0, then sign of (x | -x) must be 1
// return ((x | ((~x) + 1)) >> 31) + 1; use less ops, achieve the same goal
}

如注释, 第二种是看了别人的博客的写法, 利用的是$-1 + 1 = 0, 0 + 1 = 1$, 可以对符号位操作得到0或1,因为负数右移31位是-1, 非负数是0

很巧妙, 应该记住, 以后用

howManyBits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 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) {
return 0;
}

就这一个自己不会的。 想了很多方法

  1. 对于负数找最前边的0, 非负数找最前边的0
  2. 负数不断右移直到为-1, 非负数不断右移直到为0
  3. 二分, 但是没想到怎么具体实现, 正解好像还真是二分

前两种都要位移至多30次, 肯定不行, 后续看看人家怎么写的再补

floatScale2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 
* 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) {
unsigned e1 = 2139095040;
unsigned e = e1 & uf;
unsigned s22 = 8388607;
unsigned m = s22 & uf;

if(!(e ^ e1)) return uf;

if(e == 0) return ((uf >> 23) << 23) + (m << 1);

return uf + (1 << 23);
}

先判断阶码位是不是全是1, 是的话按照题目要求发挥uf本身

再判断阶码位是不是全是0, 是不是非规格化的

如果是非规格化, 直接尾数整体左移一位, 这个时候其实分为尾数最高位是1还是0两种情况, 但是最后实现是一样的

如果是规格化, 就直接阶码加1就行了

floatFloat2

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
/* 
* 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 = 127;
unsigned sign = (uf >> 31) & 1;
int e = (uf >> 23) & 255;
int m = uf & 8388607;
int E = e - bias;
int len = E + 1;
int M = m;
int rb = 0;

if(e == 255) return 0x80000000u;
if((!e) || (E < 0)) return 0;
if(len > 32 || (len == 32 && sign)) return 0x80000000u;
if(E <= 23) rb = 23 - E;

M = M >> rb;
M = M << E;
M = M + (1 << E);

if(sign) M = (~M) + 1;

return M;
}

就是判断, 繁琐一点, 理清楚就好了

floatPower2

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
/* 
* 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 0x7f800000;
if(x >= -126)
{
unsigned exp = x + 127;

return exp << 23;
}
if(x >= -149)
return 0x1 << (x + 149);
return 0;
}

确定好非规格和规格, 规格和inf的边界就可以了