/* * 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: intFunct(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 */ intpow2plus1(int x){ /* exploit ability of shifts to compute powers of 2 */ return (1 << x) + 1; }
/* * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31 */ intpow2plus4(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 andunsigned constants. You can use any arithmetic, logical, or comparison operations on intorunsigned 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 intorunsigned. 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 */ intbitXor(int x, int y){ int a = ~(x & y); // 10, 01, 00 int b = ~((~x) & (~y)); // 10, 01, 11 return a & b; // 10, 01 }
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 */ intisTmax(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 */ intallOddBits(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 */ intnegate(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 */ intisAsciiDigit(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 */ intconditional(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 */ intisLessOrEqual(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 */ intlogicalNeg(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 */ inthowManyBits(int x){ return0; } //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 */ unsignedfloatScale2(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 */ intfloatFloat2Int(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) return0x80000000u; if((!e) || (E < 0)) return0; if(len > 32 || (len == 32 && sign)) return0x80000000u; 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 */ unsignedfloatPower2(int x){ if(x > 127) return0x7f800000; if(x >= -126) { unsignedexp = x + 127;
/* * 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 */ intallOddBits(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); }
/* * conditional - same as x ? y : z * Example: conditional(2,4,5) = 4 * Legal ops: ! ~ & ^ | + << >> * Max ops: 16 * Rating: 3 */ intconditional(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 */ intconditional(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 */ intisLessOrEqual(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 */ intlogicalNeg(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 }
/* * 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 */ unsignedfloatScale2(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);
/* * 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 */ intfloatFloat2Int(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) return0x80000000u; if((!e) || (E < 0)) return0; if(len > 32 || (len == 32 && sign)) return0x80000000u; if(E <= 23) rb = 23 - E; M = M >> rb; M = M << E; M = M + (1 << E);
/* * 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 */ unsignedfloatPower2(int x){ if(x > 127) return0x7f800000; if(x >= -126) { unsignedexp = x + 127;
