剛剛完成注冊博客，想寫一篇隨筆，方便以后自己回顧，如果恰好也能幫助到你，是我的榮幸，
這次隨筆是記載我的計算機系統（CS:APP，Computer Systems:A Programer's Perspective)課程的一次實驗
為了實作這15個函式，參考了（抄襲了- -）網上很多大佬的解答，但是程序中也有了自己的一些體會，
下面分享一下自己的理解，每個函式的實作都附有相應解釋，有個別自己還不是很理解就沒有寫解釋，見諒啊，
注：實驗環境 ubuntu 12.04
每次修改bits.c時，都要make btest才能用btest測驗函式的正確性
/* * CS:APP Data Lab * * * 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 an integer by more than the word size. 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 implent 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 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 operators (! ~ & ^ | + << >>) that you are allowed to use for your implementation of the function. The max operator count is checked by dlc. Note that '=' 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 /* * bitAnd - x&y using only ~ and | * Example: bitAnd(6, 5) = 4 * Legal ops: ~ | * Max ops: 8 * Rating: 1 */ int bitAnd(int x, int y) { return ~((~x) | (~y)); } //利用德摩根律 /* * getByte - Extract byte n from word x * Bytes numbered from 0 (LSB) to 3 (MSB) * Examples: getByte(0x12345678,1) = 0x56 * Legal ops: ! ~ & ^ | + << >> * Max ops: 6 * Rating: 2 */ int getByte(int x, int n) { return ((x >> (n << 3)) & 0xFF); } //將所要取的位元組移到最右端然后其余位通過與運算置0 /* * logicalShift - shift x to the right by n, using a logical shift * Can assume that 0 <= n <= 31 * Examples: logicalShift(0x87654321,4) = 0x08765432 * Legal ops: ! ~ & ^ | + << >> * Max ops: 20 * Rating: 3 */ int logicalShift(int x, int n) { int tmp = 32 + (~n); return (x >> n) & ((1 << tmp) + (~0) + (1 << tmp)); } //運用機器的算術右移，然后高位置0和低位保持 //右移n位后原最高位到了第31-n位，31-n表示為31+((~n)+1) = 32+(~n) //通過與高n位全為0，第32-n位全為1的數實作高位置0和低位保持 //這個數是(1 << ((32+(~n)+1)) - 1 //由于n可能為0，這樣左移32位會根據gcc編譯規則左移 32 % 32(型別位長) = 0位 //故將該數表示為(1 << (32+(~n)+1)) + (~0) + (1 << (32+(~n)+1)) /* * bitCount - returns count of number of 1's in word * Examples: bitCount(5) = 2, bitCount(7) = 3 * Legal ops: ! ~ & ^ | + << >> * Max ops: 40 * Rating: 4 */ int bitCount(int x) { //造數 int _tmp1 = 0x55 | (0x55 << 8); //0x00005555 int _tmp2 = 0x33 | (0x33 << 8); //0x00003333 int _tmp3 = 0xf | (0xf <<8); //0x00000f0f int tmp1 = _tmp1 | (_tmp1 << 16); //0x55555555 int tmp2 = _tmp2 | (_tmp2 << 16); //0x33333333 int tmp3 = _tmp3 | (_tmp3 << 16); //0x0f0f0f0f int tmp4 = 0xff | (0xff << 16); //0x00ff00ff int tmp5 = 0xff | (0xff << 8); //0x0000ffff //求和 int res = 0; res = (x & tmp1) + ((x >> 1) & tmp1); res = (res & tmp2) + ((res >> 2) & tmp2); res = (res & tmp3) + ((res >> 4) & tmp3); res = (res & tmp4) + ((res >> 8) & tmp4); res = (res & tmp5) + ((res >> 16) & tmp5); //回傳 return res; } //類似遞回分治的思想，以統計二進制數x=10中1的個數為例 //方法是將高位移到低位和0x1相與，(x & 0x1) + ((x >> 1) & 0x1) //造出5個數，0x55555555,0x33333333,0x0f0f0f0f,0x00ff00ff,0x0000ffff //這五個數寫成二進制，分別隔著1,2,4,8,16個0 /* * bang - Compute !x without using ! * Examples: bang(3) = 0, bang(0) = 1 * Legal ops: ~ & ^ | + << >> * Max ops: 12 * Rating: 4 */ int bang(int x) { return ((~((x | ((~x)+1)) >> 31)) & 0x1); } //將一個非零數的補碼與其相反數的補碼相或，最高位一定是1 //但如果對0進行此操作，最高位還是0 /* * tmin - return minimum two's complement integer * Legal ops: ! ~ & ^ | + << >> * Max ops: 4 * Rating: 1 */ int tmin(void) { return (0x1 << 31); } //最小負整數的二進制補碼是1000...0000 /* * fitsBits - return 1 if x can be represented as an * n-bit, two's complement integer. * 1 <= n <= 32 * Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1 * Legal ops: ! ~ & ^ | + << >> * Max ops: 15 * Rating: 2 */ int fitsBits(int x, int n) { return !(((x >> (n+(~0))) + 1) >> 1); } //若n位能表示這個數 //正數的1只能出現在低n-1位，其余位全為0 //負數的0只能出現在低n-1位，其余位全為1 //故將該數右移n-1位后所得結果，正數全為0，負數全為1 //此時再+1后右移1位，可以得到全0 //若n位不能表示這個數，則一定不會有以上結論 //n-1表示為n+(-1)，即n+(~0) /* * divpwr2 - Compute x/(2^n), for 0 <= n <= 30 * Round toward zero * Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2 * Legal ops: ! ~ & ^ | + << >> * Max ops: 15 * Rating: 2 */ int divpwr2(int x, int n) { return ( x + (((x >> 31) & 0x1) << n) + (~0) + (!((x >> 31) & 0x1)) ) >> n; } //本題是對于標準除法/的實作，全正取下整，有負取上整 //而通過移位實作除以2的冪，都是取下整 //故對于負數要加一個偏移量(1 << n) - 1 (證明在深入理解計算機系統第9版P73) //因為是負數才要加偏移量，所以式子中的1剛好可以用符號位((x >> 31) & 0x1)表示 //若x > 0，(((x >> 31) & 0x1) << n)的結果為0，會導致多減去了1即(~0) //巧妙多加一個符號位的邏輯非結果即(!((x >> 31) & 0x1))，負數為0，整數為1，恰好彌補 /* * negate - return -x * Example: negate(1) = -1. * Legal ops: ! ~ & ^ | + << >> * Max ops: 5 * Rating: 2 */ int negate(int x) { return ((~x) + 1); } //對一個數的補碼進行按位取反加1就能得到其相反數的補碼 /* * isPositive - return 1 if x > 0, return 0 otherwise * Example: isPositive(-1) = 0. * Legal ops: ! ~ & ^ | + << >> * Max ops: 8 * Rating: 3 */ int isPositive(int x) { return !( ((x >> 31) & 0x1) | (!(x << 1)) ); } //正數和零的符號位為0，負數為1 //左移1位后用！，正數的結果一定為0，負數的結果可0可1,零的結果一定是1 //將以上兩個結果相或，正數的結果為0,負數一定為1，零的結果一定是1 /* * 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 xSign = (x >> 31) & 0x1; int ySign = (y >> 31) & 0x1; int signDiff = xSign & (!ySign); int signSame = !(((y + (~x+1)) >> 31) & 0x1) & !(xSign ^ ySign); return signDiff | signSame; } //作差法判斷大小 //首先要判斷符號位，因為可能存在溢位 //正數符號位為0，負數符號位為1，列出x,y的真值表 //x y z //0 0 符號相同要進行下一步作差 //0 1 0(表示x > y) //1 0 1(表示x < y) //1 1 符號相同要進行下一步作差 //可以看到若用一個運算式(xSign & !(ySign))可以實作只用第三種情況為1,就可以完成符號位的判斷 //接下來還要看其他三種情況，通過與上!(xSign ^ ySign)保證兩者同號，因為第二種不同號的情況在該運算式下結果為0，與0就置0 //前面取y-x的符號位，為0說明，y >= x，否則y < x，再取邏輯非配合與操作 /* * ilog2 - return floor(log base 2 of x), where x > 0 * Example: ilog2(16) = 4 * Legal ops: ! ~ & ^ | + << >> * Max ops: 90 * Rating: 4 */ int ilog2(int x) { int res = 0; res = res + ((!!(x>>(16 + res)))<<4); res = res + ((!!(x>>(8 + res)))<<3); res = res + ((!!(x>>(4 + res)))<<2); res = res + ((!!(x>>(2 + res)))<<1); res = res + ((!!(x>>(1 + res)))<<0); return res; } /* * float_neg - Return bit-level equivalent of expression -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 representations of * single-precision floating point values. * When argument is NaN, return argument. * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while * Max ops: 10 * Rating: 2 */ unsigned float_neg(unsigned uf) { unsigned exp = (uf >> 23) & 0xFF; unsigned frac = uf & 0x7FFFFF; unsigned res = uf ^ 0x80000000; if(exp == 0xFF && frac) { res = uf; } return res; } //取exp和frac判斷是否為NaN //異或改變符號位 /* * float_i2f - Return bit-level equivalent of expression (float) x * Result is returned as unsigned int, but * it is to be interpreted as the bit-level representation of a * single-precision floating point values. * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while * Max ops: 30 * Rating: 4 */ unsigned float_i2f(int x) { unsigned ans; int xSignx = x & (1 << 31); int res = 31; int ss = 0; int ff = 0; int tmp; if(x == 0) ans = 0; else{ if(xSignx) x = (~x) + 1; while(!((1 << res) & x)) { res--; } x = x ^ (1 << res); if(res < 23) x = x << (23 - res); else { tmp = res - 24; if(tmp >= 0) ss = (x >> tmp) & 1,ff = ((1 << tmp) - 1) & x; x = (x >> (res-23)); } x = x | ((res+127) << 23); if(ff == 0) { ss = (ss & x); } x = x + ss; x = x | xSignx; ans = x; } return ans; } /* * float_twice - 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 float_twice(unsigned uf) { unsigned tmp = uf; unsigned exp = (tmp >> 23) & 0xFF; unsigned frac = tmp & 0x007fffff; if(exp == 0x0) { //非規格化數 tmp = (tmp & 0x80000000) | (frac << 1); } else if(exp != 0xFF) { //規格化數 tmp += (1 << 23); if(((tmp >> 23) & 0xFF) == 0xFF) { tmp = tmp >> 23 << 23; } } return tmp; }
如果讀者看完后有自己獨到的實作方式，歡迎一起交流學習，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/3623.html
標籤：C
上一篇：文字渲染一探