Data Lab记录

by Gu Wei
2021年9月

在bits.c文件中

​x
1
//1
2
/* 
3
 * bitXor - x^y using only ~ and & 
4
 *   Example: bitXor(4, 5) = 1
5
 *   Legal ops: ~ &
6
 *   Max ops: 14
7
 *   Rating: 1
8
 */
9
/*实现异或运算，用离散知识易得*/
10
int bitXor(int x, int y) {
11
  return ~(~(~x&y)&~(x&~y));
12
}
13
/* 
14
 * tmin - return minimum two's complement integer 
15
 *   Legal ops: ! ~ & ^ | + << >>
16
 *   Max ops: 4
17
 *   Rating: 1
18
 */
19
/*最小的二进制补码就是100...0*/
20
int tmin(void) {
21
  return 1 << 31;
22
}
23
//2
24
/*
25
 * isTmax - returns 1 if x is the maximum, two's complement number,
26
 *     and 0 otherwise 
27
 *   Legal ops: ! ~ & ^ | +
28
 *   Max ops: 10
29
 *   Rating: 1
30
 */
31
/**
32
 * 题意：判断x是否为最大的二进制补码数
33
 * 相反数等于自己的数有min以及0，这里利用该性质实现函数
34
 * 若x是max，x+1后成了min
35
 * 又利用-x == ~x+1 （这是显然的
36
 * 通过异或^运算判断是否相等：a^b == 0 iff a == b
37
 * 最后还要排除x==0的情况
38
*/
39
int isTmax(int x) {
40
  x += 1;
41
  return (!(x^(~x+1)))&(!!x);
42
}
43
/* 
44
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
45
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
46
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
47
 *   Legal ops: ! ~ & ^ | + << >>
48
 *   Max ops: 12
49
 *   Rating: 2
50
 */
51
/**
52
 * 题意：判读x的奇数位是否全为1
53
 * 照着移移就知道了
54
 */
55
int allOddBits(int x) {
56
  x = x & (x >> 2);
57
  x = x & (x >> 4);
58
  x = x & (x >> 8);
59
  x = x & (x >> 16);
60
  return (x & 2) >> 1;
61
}
62
/* 
63
 * negate - return -x 
64
 *   Example: negate(1) = -1.
65
 *   Legal ops: ! ~ & ^ | + << >>
66
 *   Max ops: 5
67
 *   Rating: 2
68
 */
69

70
/**
71
 * 题意：实现相反数
72
 * 这为什么会是rating2？这不是简单的结论吗，甚至之前的isTmax也用到了该性质
73
 */
74
int negate(int x) {
75
  return ~x + 1;
76
}
77
//3
78
/* 
79
 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
80
 *   Example: isAsciiDigit(0x35) = 1.
81
 *            isAsciiDigit(0x3a) = 0.
82
 *            isAsciiDigit(0x05) = 0.
83
 *   Legal ops: ! ~ & ^ | + << >>
84
 *   Max ops: 15
85
 *   Rating: 3
86
 */
87
/**
88
 * 题意：return 1 if 0x30 <= x <= 0x39 
89
 * 注意：!x == 1 iff x == 0, e.g.!(-1) = 0;
90
 * 利用a + ~b+1 实现a-b
91
 * 利用最高位（31位）是否为1来判断x是否为负数：当a<0时，a>>31==-1；当a>=0时，a>>31==0
92
 * 故当a<0时!(a>>31)==0；当a>=0时!(a>>31)==1
93
 */
94
int isAsciiDigit(int x) {
95
  return !((~0x30 + x + 1)>>31) & !((~x + 0x39 + 1)>>31);
96
}
97
/* 
98
 * conditional - same as x ? y : z 
99
 *   Example: conditional(2,4,5) = 4
100
 *   Legal ops: ! ~ & ^ | + << >>
101
 *   Max ops: 16
102
 *   Rating: 3
103
 */
104
/**
105
 * 题意：x ? y : z 
106
 * 利用掩码选择y与z
107
 * 利用x设置掩码mask为0xFFFFFFFF或者0x0
108
 */
109
int conditional(int x, int y, int z) {
110
  int tmp = !x;
111
  int mask = ~tmp + 1;
112
  return (~mask & y) + (mask & z);
113
}
114
/* 
115
 * isLessOrEqual - if x <= y  then return 1, else return 0 
116
 *   Example: isLessOrEqual(4,5) = 1.
117
 *   Legal ops: ! ~ & ^ | + << >>
118
 *   Max ops: 24
119
 *   Rating: 3
120
 */
121
/**
122
 * 题意：if x <= y  then return 1, else return 0
123
 * 简单地利用!((y+~x+1)>>31)存在溢出问题，使判断式出错。需要由符号是否相同分类。
124
 * 利用difSign作为掩码，当正负性相同时，difSign为0，否则为-1
125
 * 这样综合利用conditional和isAsciiDigit中的方法即可解决
126
 */
127
int isLessOrEqual(int x, int y) {
128
  int difSign = (x^y)>>31;
129
  return (~difSign&!((y+~x+1)>>31))+(difSign&(!(y>>31)));
130
}
131
//4
132
/* 
133
 * logicalNeg - implement the ! operator, using all of 
134
 *              the legal operators except !
135
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
136
 *   Legal ops: ~ & ^ | + << >>
137
 *   Max ops: 12
138
 *   Rating: 4 
139
 */
140
/**
141
 * 题意：实现！
142
 * 利用 只有0和它的相反数同时满足最高位为0 的特点实现
143
 */ 
144
int logicalNeg(int x) {
145
  return ~((x|(~x+1))>>31)&1;
146
}
147
/* howManyBits - return the minimum number of bits required to represent x in
148
 *             two's complement
149
 *  Examples: howManyBits(12) = 5
150
 *            howManyBits(298) = 10
151
 *            howManyBits(-5) = 4
152
 *            howManyBits(0)  = 1
153
 *            howManyBits(-1) = 1
154
 *            howManyBits(0x80000000) = 32
155
 *  Legal ops: ! ~ & ^ | + << >>
156
 *  Max ops: 90
157
 *  Rating: 4
158
 */
159
/**
160
 * 题意：求表示x的二进制补码的最小位数
161
 * 我这么理解的：二分查找最高位1的位置，最后加上符号位即可
162
 * 一开始把负数x取非，为了把最前面无效的1给去掉
163
 */
164
int howManyBits(int x) {
165
  int b16,b8,b4,b2,b1,b0;
166
  int sign=x>>31;
167
  x = (sign&~x)|(~sign&x);//如果x为正，则x不变；如果x为负，则x改为~x
168
  // 不断缩小范围
169
  b16 = !!(x>>16)<<4;//高十六位是否有1
170
  x = x>>b16;//如果有（至少需要16位），则将原数右移16位
171
  b8 = !!(x>>8)<<3;//剩余位高8位(i.e.8-15位）是否有1
172
  x = x>>b8;//如果有（至少需要16+8=24位），则右移8位
173
  b4 = !!(x>>4)<<2;//同理
174
  x = x>>b4;
175
  b2 = !!(x>>2)<<1;
176
  x = x>>b2;
177
  b1 = !!(x>>1);
178
  x = x>>b1;
179
  b0 = x;
180
  return b16+b8+b4+b2+b1+b0+1;//+1表示加上符号位
181
}
182
//float
183
/* 
184
 * floatScale2 - Return bit-level equivalent of expression 2*f for
185
 *   floating point argument f.
186
 *   Both the argument and result are passed as unsigned int's, but
187
 *   they are to be interpreted as the bit-level representation of
188
 *   single-precision floating point values.
189
 *   When argument is NaN, return argument
190
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
191
 *   Max ops: 30
192
 *   Rating: 4
193
 */
194
/**
195
 * 注释：float数都是把unsigned int当作float来使的
196
 */
197
/**
198
 * 题意：如果uf为特殊值（i.e.exp全为1）返回uf，否则返回2*uf
199
 */ 
200
unsigned floatScale2(unsigned uf) {
201
  unsigned exp = uf>>23;
202
  unsigned ans;
203
  //NaN and inf，i.e.exp全为1，直接返回uf
204
  if(!((exp&0xFF)^0xFF))
205
      return uf;
206
  //non-normalized 直接左移
207
  /**
208
   * 这里有一个精妙的点，关于frac的最高位为1的情况
209
   * 此时把uf左移一位，frac最高位变成了exp的最低位，uf从非规格化数变成了规格化数
210
   * 由于规格化和非规格化E和M的精妙设置，uf左移一位就直接正确了，做到了很好的平稳过渡
211
   */ 
212
  if(!(exp&0xFF))
213
  {
214
      unsigned sign = uf>>31<<31;
215
      return (uf<<1)|sign;
216
  }
217
  //normalized 指数部分加一
218
  /**
219
   * 这里也有一个小细节，我们无法通过修改frac来使uf变成两倍，只能通过exp加一的方法
220
   * 于是，当exp加一后变成全是一后，就是inf情况，需要再把frac置零即可
221
   */
222
  ans = (1<<23)+uf;
223
  //inf
224
  if (!((exp&0xFF)^0xFF))
225
      return ans>>23<<23;
226
  else
227
      return ans;
228
}
229
/* 
230
 * floatFloat2Int - Return bit-level equivalent of expression (int) f
231
 *   for floating point argument f.
232
 *   Argument is passed as unsigned int, but
233
 *   it is to be interpreted as the bit-level representation of a
234
 *   single-precision floating point value.
235
 *   Anything out of range (including NaN and infinity) should return
236
 *   0x80000000u.
237
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
238
 *   Max ops: 30
239
 *   Rating: 4
240
 */
241
/**
242
 * 题意：实现float到int的强制类型转换
243
 * 特别的，Anything out of range (including NaN and infinity) should return 0x80000000u.
244
 */ 
245
int floatFloat2Int(unsigned uf) {
246
  int E = ((uf>>23)&0xFF)-127;
247
  int sign = uf>>31;
248
  unsigned M = (uf&0x7FFFFF)|0x800000; //加上1，非规格化数已经在E<0的时候被排除了。严格的说这里的M是M * 2^23
249
  
250
  if(E<0) return 0; //由于M<2，所以E<0时必为纯小数
251
  if(E>=31) return 0x80000000u; //超出范围。提示：int范围为-2^31~2^31-1，0x80000000u=-2^31，NaN和inf也涵盖
252
  
253
  //M是一个23位小数，又注意到这里的M其实是M * 2^23
254
  if(E>23) M <<= E-23;
255
  else M >>= 23-E;
256

257
  if(sign) return ~M+1;//负数
258
  else return M;//正数
259
}
260
/* 
261
 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
262
 *   (2.0 raised to the power x) for any 32-bit integer x.
263
 *
264
 *   The unsigned value that is returned should have the identical bit
265
 *   representation as the single-precision floating-point number 2.0^x.
266
 *   If the result is too small to be represented as a denorm, return
267
 *   0. If too large, return +INF.
268
 * 
269
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while 
270
 *   Max ops: 30 
271
 *   Rating: 4
272
 */
273
/**
274
 * 题意：返回2^x的浮点型
275
 * 其实不难，就分类讨论
276
 */ 
277
unsigned floatPower2(int x) {
278
    //float最大为(2-2^-23)·2^127，小于2^128
279
    if (x>127)
280
        return 0xFF<<23; //返回+inf
281
    else if (x<-149) return 0;//float最接近0的数为2^-149，[00..001]
282
    else if (x>=-126) //规格化数
283
    {
284
        int exp = x + 127;
285
        return exp << 23;
286
    }
287
    else //-126>x>=-149，非规格化
288
    {
289
        int t = 149 + x;
290
        return (1 << t);
291
    }
292
}

测试如下：

xxxxxxxxxx
18
1
linux> ./dlc bits.c
2
# 无输出则说明代码符合要求
3
linux> ./btest
4
Score   Rating  Errors  Function
5
 1      1       0       bitXor
6
 1      1       0       tmin
7
 1      1       0       isTmax
8
 2      2       0       allOddBits
9
 2      2       0       negate
10
 3      3       0       isAsciiDigit
11
 3      3       0       conditional
12
 3      3       0       isLessOrEqual
13
 4      4       0       logicalNeg
14
 4      4       0       howManyBits
15
 4      4       0       floatScale2
16
 4      4       0       floatFloat2Int
17
 4      4       0       floatPower2
18
Total points: 36/36

满分即可