做得有点慢，位运算确实不太容易想到……
写出来的代码如果没有注释也不容易看懂。
1 /* 2 * CS:APP Data Lab 3 * 4 * <Please put your name and userid here> 5 * 6 * bits.c - Source file with your solutions to the Lab. 7 * This is the file you will hand in to your instructor. 8 * 9 * WARNING: Do not include the <stdio.h> header; it confuses the dlc 10 * compiler. You can still use printf for debugging without including 11 * <stdio.h>, although you might get a compiler warning. In general, 12 * it's not good practice to ignore compiler warnings, but in this 13 * case it's OK. 14 */ 15 #if 0 16 /* 17 * Instructions to Students: 18 * 19 * STEP 1: Read the following instructions carefully. 20 */ 21 You will provide your solution to the Data Lab by 22 editing the collection of functions in this source file. 23 INTEGER CODING RULES: 24 Replace the "return" statement in each function with one 25 or more lines of C code that implements the function. Your code 26 must conform to the following style: 27 int Funct(arg1, arg2, ...) { 28 /* brief description of how your implementation works */ 29 int var1 = Expr1; 30 ... 31 int varM = ExprM; 32 varJ = ExprJ; 33 ... 34 varN = ExprN; 35 return ExprR; 36 } 37 Each "Expr" is an expression using ONLY the following: 38 1. Integer constants 0 through 255 (0xFF), inclusive. You are 39 not allowed to use big constants such as 0xffffffff. 40 2. Function arguments and local variables (no global variables). 41 3. Unary integer operations ! ~ 42 4. Binary integer operations & ^ | + << >> 43 Some of the problems restrict the set of allowed operators even further. 44 Each "Expr" may consist of multiple operators. You are not restricted to 45 one operator per line. 46 You are expressly forbidden to: 47 1. Use any control constructs such as if, do, while, for, switch, etc. 48 2. Define or use any macros. 49 3. Define any additional functions in this file. 50 4. Call any functions. 51 5. Use any other operations, such as &&, ||, -, or ?: 52 6. Use any form of casting. 53 7. Use any data type other than int. This implies that you 54 cannot use arrays, structs, or unions. 55 You may assume that your machine: 56 1. Uses 2s complement, 32-bit representations of integers. 57 2. Performs right shifts arithmetically. 58 3. Has unpredictable behavior when shifting an integer by more 59 than the word size. 60 EXAMPLES OF ACCEPTABLE CODING STYLE: 61 /* 62 * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31 63 */ 64 int pow2plus1(int x) { 65 /* exploit ability of shifts to compute powers of 2 */ 66 return (1 << x) + 1; 67 } 68 /* 69 * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31 70 */ 71 int pow2plus4(int x) { 72 /* exploit ability of shifts to compute powers of 2 */ 73 int result = (1 << x); 74 result += 4; 75 return result; 76 } 77 FLOATING POINT CODING RULES 78 For the problems that require you to implent floating-point operations, 79 the coding rules are less strict. You are allowed to use looping and 80 conditional control. You are allowed to use both ints and unsigneds. 81 You can use arbitrary integer and unsigned constants. 82 You are expressly forbidden to: 83 1. Define or use any macros. 84 2. Define any additional functions in this file. 85 3. Call any functions. 86 4. Use any form of casting. 87 5. Use any data type other than int or unsigned. This means that you 88 cannot use arrays, structs, or unions. 89 6. Use any floating point data types, operations, or constants. 90 NOTES: 91 1. Use the dlc (data lab checker) compiler (described in the handout) to 92 check the legality of your solutions. 93 2. Each function has a maximum number of operators (! ~ & ^ | + << >>) 94 that you are allowed to use for your implementation of the function. 95 The max operator count is checked by dlc. Note that '=' is not 96 counted; you may use as many of these as you want without penalty. 97 3. Use the btest test harness to check your functions for correctness. 98 4. Use the BDD checker to formally verify your functions 99 5. The maximum number of ops for each function is given in the 100 header comment for each function. If there are any inconsistencies 101 between the maximum ops in the writeup and in this file, consider 102 this file the authoritative source. 103 /* 104 * STEP 2: Modify the following functions according the coding rules. 105 * 106 * IMPORTANT. TO AVOID GRADING SURPRISES: 107 * 1. Use the dlc compiler to check that your solutions conform 108 * to the coding rules. 109 * 2. Use the BDD checker to formally verify that your solutions produce 110 * the correct answers. 111 */ 112 #endif 113 /* 114 * bitAnd - x&y using only ~ and | 115 * Example: bitAnd(6, 5) = 4 116 * Legal ops: ~ | 117 * Max ops: 8 118 * Rating: 1 119 */ 120 int bitAnd(int x, int y) { 121 //德摩根律 122 return ~(~x|~y); 123 } 124 /* 125 * getByte - Extract byte n from word x 126 * Bytes numbered from 0 (LSB) to 3 (MSB) 127 * Examples: getByte(0x12345678,1) = 0x56 128 * Legal ops: ! ~ & ^ | + << >> 129 * Max ops: 6 130 * Rating: 2 131 */ 132 int getByte(int x, int n) { 133 134 x=x>>(n<<3); 135 x=0xFF&x; 136 return x; 137 } 138 /* 139 * logicalShift - shift x to the right by n, using a logical shift 140 * Can assume that 0 <= n <= 31 141 * Examples: logicalShift(0x87654321,4) = 0x08765432 142 * Legal ops: ! ~ & ^ | + << >> 143 * Max ops: 20 144 * Rating: 3 145 */ 146 int logicalShift(int x, int n) { 147 /* if x is neg, will add 1s on left , change them to 0. 148 & a number as 00000...111111 149 1<<31->0x80000000 right shift to get 1111...000 then ~ 150 if n==0 , left shift 1 -> 0, else left shift 0 151 the number right shift (n-1) bits(n!=0, right n ,then left 1) 152 or 0 bit(right 0 left 0). */ 153 /*at first, tried change sign ,then shift, failed at 0*/ 154 155 return (x>>n)&~(1<<31<<!n>>n<<!!n); 156 } 157 /* 158 * bitCount - returns count of number of 1's in word 159 * Examples: bitCount(5) = 2, bitCount(7) = 3 160 * Legal ops: ! ~ & ^ | + << >> 161 * Max ops: 40 162 * Rating: 4 163 */ 164 int bitCount(int x) { 165 //divide conquer 166 //due to limiting const(max 0xff), my ops over 40, answer from cnblosg:liqiuhao 167 int mask1 = (((((0x55 << 8) + 0x55) << 8) + 0x55) << 8) + 0x55; 168 int mask2 = (((((0x33 << 8) + 0x33) << 8) + 0x33) << 8) + 0x33; 169 int mask3 = (((((0x0f << 8) + 0x0f) << 8) + 0x0f) << 8) + 0x0f; 170 x = (x & mask1) + ((x >>1) & mask1); 171 x = (x & mask2) + ((x >>2) & mask2); 172 x = (x & mask3) + ((x >>4) & mask3); 173 x = x + (x>>8);//4 bytes:3,2,1,0->3,3+2,2+1,1+0 174 x = x + (x>>16);//->3,3+2,3+2+1,3+2+1+0 175 return x & 0x3F;//max=0x0010,0000 thus & 0x0011,1111 176 } 177 /* 178 * bang - Compute !x without using ! 179 * Examples: bang(3) = 0, bang(0) = 1 180 * Legal ops: ~ & ^ | + << >> 181 * Max ops: 12 182 * Rating: 4 183 */ 184 int bang(int x) { 185 return (((~x+1)|x)>>31)+1; 186 } 187 /* 188 * tmin - return minimum two's complement integer 189 * Legal ops: ! ~ & ^ | + << >> 190 * Max ops: 4 191 * Rating: 1 192 */ 193 int tmin(void) { 194 return 1<<31; 195 } 196 /* 197 * fitsBits - return 1 if x can be represented as an 198 * n-bit, two's complement integer. 199 * 1 <= n <= 32 200 * Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1 201 * Legal ops: ! ~ & ^ | + << >> 202 * Max ops: 15 203 * Rating: 2 204 */ 205 int fitsBits(int x, int n) { 206 //didn't make out, answer from cnblogs:liqiuhao 207 int y; 208 n = ~n + 1; 209 y = (x << (32 + n)) >> (32 + n); 210 //shift to most left,truncate 32-n 211 return !(y ^ x); 212 } 213 /* 214 * divpwr2 - Compute x/(2^n), for 0 <= n <= 30 215 * Round toward zero 216 * Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2 217 * Legal ops: ! ~ & ^ | + << >> 218 * Max ops: 15 219 * Rating: 2 220 */ 221 int divpwr2(int x, int n) { 222 /* 223 pos:x>>n 224 neg:(x+2^n-1)/2^n, (x + (1<<n)-1) >> n 225 */ 226 int mask=((1<<n)+~0)&x>>31; //>> prior of & , 227 return (x + mask) >> n; 228 } 229 /* 230 * negate - return -x 231 * Example: negate(1) = -1. 232 * Legal ops: ! ~ & ^ | + << >> 233 * Max ops: 5 234 * Rating: 2 235 */ 236 int negate(int x) { 237 return ~x+1; 238 } 239 /* 240 * isPositive - return 1 if x > 0, return 0 otherwise 241 * Example: isPositive(-1) = 0. 242 * Legal ops: ! ~ & ^ | + << >> 243 * Max ops: 8 244 * Rating: 3 245 */ 246 int isPositive(int x) { 247 return (!!x)&((x>>31)+1);// 0 248 } 249 /* 250 * isLessOrEqual - if x <= y then return 1, else return 0 251 * Example: isLessOrEqual(4,5) = 1. 252 * Legal ops: ! ~ & ^ | + << >> 253 * Max ops: 24 254 * Rating: 3 255 */ 256 int isLessOrEqual(int x, int y) { 257 /* 258 1. x has same sign with y(wont overflow), and y-x>=0 259 2. different sign,y is pos. 260 */ 261 int sum=((~x+1+y)>>31)+1;//y-x>=0, (pos>>31)+1=1,(neg>>31)+1=0 262 //int xsign=(x>>31)+1; 263 int ysign=(y>>31)+1; 264 int same=((x^y)>>31)+1; 265 return (same&sum)|(!same&ysign); 266 } 267 /* 268 * ilog2 - return floor(log base 2 of x), where x > 0 269 * Example: ilog2(16) = 4 270 * Legal ops: ! ~ & ^ | + << >> 271 * Max ops: 90 272 * Rating: 4 273 */ 274 int ilog2(int x) { 275 //binary search 276 //1. if in former 16 bits? 277 int mask0=0xff<<8; 278 int mask1=(mask0+0xff)<<16; 279 int res1=!!(mask1&x);//if in? 280 int shift1=res1<<4; 281 int res2,res3,res4,res5,shift2,shift3,shift4,shift5,ans; 282 x=x>>shift1;//mask1>> 0 or 16 bits 283 //2. 8 bits 284 res2=!!(mask0&x); 285 shift2=res2<<3; 286 x=x>>shift2; 287 //3. 4bits 288 res3=!!(0xf0&x); 289 shift3=res3<<2; 290 x=x>>shift3; 291 //4. 2 bits 292 res4=!!(0xc&x); 293 shift4=res4<<1; 294 x=x>>shift4; 295 //5. 1 bits 296 res5=!!(0x2&x); 297 shift5=res5; 298 ans=shift1+shift2+shift3+shift4+shift5; 299 return ans; 300 } 301 /* 302 * float_neg - Return bit-level equivalent of expression -f for 303 * floating point argument f. 304 * Both the argument and result are passed as unsigned int's, but 305 * they are to be interpreted as the bit-level representations of 306 * single-precision floating point values. 307 * When argument is NaN, return argument. 308 * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while 309 * Max ops: 10 310 * Rating: 2 311 */ 312 unsigned float_neg(unsigned uf) { 313 /* 314 if NaN,return uf,else return -uf 315 1^A=~A,0^A=A 316 judge NaN:==0x7fc00000,0xffc00000 317 */ 318 unsigned mask1=0x80000000;//1<<31; 319 unsigned mask2=0x7f800000;//=uf<<1; 320 unsigned mask3=0x007fffff; 321 unsigned mask4=0x7fc00000; 322 //if(!((mask2&uf)^mask2)&&(mask3&uf)) successful 323 if(!((mask4&uf)^mask4))//another way 324 {return uf;} 325 else { 326 uf = uf ^ mask1 ; 327 return uf; 328 } 329 } 330 /* 331 * float_i2f - Return bit-level equivalent of expression (float) x 332 * Result is returned as unsigned int, but 333 * it is to be interpreted as the bit-level representation of a 334 * single-precision floating point values. 335 * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while 336 * Max ops: 30 337 * Rating: 4 338 */ 339 unsigned float_i2f(int x) { 340 341 if(!x){return 0;} 342 else{ 343 int exp=~0; 344 int E; 345 unsigned mask1=x; 346 unsigned mask2,mask3; 347 int shift; 348 int sign=0x80000000&x;// pos=0, neg=1 349 if(sign){ 350 mask1=-mask1; 351 } 352 mask3=mask2=mask1; 353 while(mask1){ 354 exp=exp+1; 355 mask1=mask1>>1; 356 } 357 E=exp; 358 // exp=(exp+0x7f)<<23; 359 shift=31-E-8; 360 // mask2=mask2<<(31-exp); 361 // mask2=mask2>>8; 362 if(shift>=0){//forgot "=" 363 // left shift 364 // mask2<<shift;//mdzz, debug for a long time 365 mask3=mask3<<shift; // fotgot "=" 366 } 367 else{ 368 /* shift < 0, right shift.deal with round.round to even 369 if odd,add 0.5 (if deserted frac > 0.5 , +1 ;if = , +1); 370 if even ,add 0.499...(if deserted frac > 0.5 , +1 ;if = , +0)*/ 371 shift=-shift; 372 // mask2>>shift; 373 mask2=mask2>>shift; 374 mask3+=(1<<(shift-1)); 375 if(mask2&1){ 376 } 377 else{ 378 mask3+=-1; 379 } 380 mask3=mask3>>shift; 381 } 382 exp=((exp+0x7f)<<23)+(mask3>>1);//round may cause overflow 383 exp=exp&0xff800000; // get rid of influence of adding frac 384 mask3=mask3&0x7fffff; 385 return sign|exp|mask3; 386 } 387 } 388 /* 389 * float_twice - Return bit-level equivalent of expression 2*f for 390 * floating point argument f. 391 * Both the argument and result are passed as unsigned int's, but 392 * they are to be interpreted as the bit-level representation of 393 * single-precision floating point values. 394 * When argument is NaN, return argument 395 * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while 396 * Max ops: 30 397 * Rating: 4 398 */ 399 unsigned float_twice(unsigned uf) { 400 /* 401 1. special:inf or NaN 402 2. denorm 403 2.1 0 404 2.2 close to 0 405 3. norm ,exp++*/ 406 unsigned res; 407 int mask1=uf&0x7f800000; 408 int sign = uf&0x80000000; 409 if(!(mask1^0x7f800000)){//exp all 1 410 res= uf; 411 } 412 else if(!(mask1)){//exp all 0 413 if(!(uf&0x7fffffff)){// 0 414 res= uf; 415 } 416 else{ 417 res=uf<<1; 418 res=res|sign; 419 } 420 } 421 else{ 422 res = uf + 0x800000; 423 } 424 return res; 425 }
//