CSAPP 3e : Data lab _Data

从来好事天生俭，自古瓜儿苦后甜。这篇文章主要讲述CSAPP 3e : Data lab相关的知识，希望能为你提供帮助。

/* * 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. *//* * 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//指定n,获取第n个字节上的数字。0< =n< =3。 *Legal ops: ! ~ & ^ | + < < > > *Max ops: 6 *Rating: 2 */ int getByte(int x, int n) { n=n< < 3; //n*=8,因为每个字节占8个二进制位。 x=x> > n& 0xff; //x右移n位，即把需要获取的字节移到了最低号位，再用& 操作取得目标字节（其余位置0）。 return x; } /* * 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) { x=x> > n; //算数右移。 x=~((~0)< < (~n+32+1))& x; //将因算数右移可能补1的n个位置0。(~n+32+1)实现(32-n),~n等于(-n-1)。 return x; } /* * bitCount - returns count of number of 1‘s in word//要求计算参数值得二进制位中1的个数。 *Examples: bitCount(5) = 2, bitCount(7) = 3//用二分法。每次相加二分移位前后的值，则在相应的n个位上存储了该次 *Legal ops: ! ~ & ^ | + < < > > //二分中1的个数。eg:第一次移位操作移了移位，相加得的是相邻两个位中 *Max ops: 40//1的个数，最高值位2（b 10),需要两个位进行存储相加值。所以x& 5, *Rating: 4//因为5二进制为 b 0101。第二次操作移2位，每一个计算单元（2+2=4个位上1的个数）最大值为4(b 100) *///所以有x& 3,3=(b 0011); !重点应该发现x& (01)到(0011),再到(00001111)的变化，分别对应于二分移n位 int bitCount(int x) {//的操作。 x=(x& 0x55555555)+(x> > 1& 0x55555555); x=(x& 0x33333333)+(x> > 2& 0x33333333); x=(x& 0x0f0f0f0f)+(x> > 4& 0x0f0f0f0f); x=(x& 0x00ff00ff)+(x> > 8& 0x00ff00ff); x=(x& 0x0000ffff)+(x> > 16& 0x0000ffff); /*x=(x+(x> > 4))& 0x0f0f0f0f; x = x + (x > > 8); //此处是网上找到的方法，其实是一样的。这里后边没有0x00ff00ff是因为可以省略了。 x = x + (x > > 16); //不过需要最后x& 0x3f的操作消去从第8位开始可能存在的1(二进制中)。 x=x& 0x3f; */ return x; } /* * bang - Compute !x without using ! *Examples: bang(3) = 0, bang(0) = 1//如果x!=0,x=(x|(~x+1))符号位为1，只有x==0时才为0；（注意这里说的是 *Legal ops: ~ & ^ | + < < > > //符号位）。 *Max ops: 12 *Rating: 4 */ int bang(int x) { x=(~((x|(~x+1))> > 31))& 1; return x; } /* * tmin - return minimum two‘s complement integer //返回int的最小值。即0x80000000; *Legal ops: ! ~ & ^ | + < < > > *Max ops: 4 *Rating: 1 */ int tmin(void) { return (1< < 31); } /* * 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) { int shif=(~n+1+32); //shif=(32-n); int def=~(~0< < n); //def=1左移n位，但是不补0而是补1，比如得def=0x0000ffff; x=!!(x^((x< < shif)> > shif& def)); return x; } /* * 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) {//做这题的时候没有想到偏置量这个东西，后来在网上查了才知道的。 //全0或者全1 int signx = x > > 31; int mask = (1 < < n)-1 ; //+ (~0); //得到2^n - 1 int bias = signx & mask; //如果x是正数，则bias为0，即不用加，直接移位 //如果x为负数，加上偏置量之后再移位 return (x + bias) > > n; } /* * negate - return -x *Example: negate(1) = -1. *Legal ops: ! ~ & ^ | + < < > > *Max ops: 5 *Rating: 2 */ int negate(int x) { return ~x+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) { x=!(x> > 31& 0x1|!x); return x; } /* * isLessOrEqual - if x < = ythen return 1, else return 0 *Example: isLessOrEqual(4,5) = 1. *Legal ops: ! ~ & ^ | + < < > > *Max ops: 24 *Rating: 3 */ int isLessOrEqual(int x, int y) {//~~之后的慢慢理解，看着头疼。半个月之后回过来看这个简直了。。。 int signx=x> > 31; //如果x(y)为正数，则signx(signy)等于0；否则等于-1,即0xffffffff; int signy=y> > 31; int same=((x+(~y))> > 31)& (!(signx^signy)); //当x,y同号，求if x< =y; int differ=(!(y> > 31))& (signx^signy); //当x,y异号，求if x< =y; 异号的话其实y是正数则x< =y成立。 return same|differ } /* * ilog2 - return floor(log base 2 of x), where x > 0 *Example: ilog2(16) = 4 *Legal ops: ! ~ & ^ | + < < > > //理解方法是，在参数x的二进制位中，最左边的1是在第n位，则log(x)=n-1; *Max ops: 90//如：16的二进制是10000，最左边1在第5位，所以log(16)=5-1=4; 也可以看到1右边有4个0； *Rating: 4 */ int ilog2(int x) { int bitsNumber=0; bitsNumber=(!!(x> > 16))< < 4; bitsNumber=bitsNumber+((!!(x> > (bitsNumber+8)))< < 3); bitsNumber=bitsNumber+((!!(x> > (bitsNumber+4)))< < 2); bitsNumber=bitsNumber+((!!(x> > (bitsNumber+2)))< < 1); bitsNumber=bitsNumber+((!!(x> > (bitsNumber+1)))); bitsNumber=bitsNumber+((!!bitsNumber)+(~0)+(!(1^x))); return bitsNumber; } /* * 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 result; unsigned tmp; result=uf ^ 0x80000000; //将符号位改反 tmp=uf & (0x7fffffff); if(tmp > 0x7f800000)//此时是NaN result = uf; return result; } /* * float_i2f - Return bit-level equivalent of expression (float) x 返回int x的浮点数的二进制形式。 *Result is returned as unsigned int, but 返回的是unsigned型但是表示的时二进制单精度形式 *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 shiftLeft=0; unsigned afterShift, tmp, flag; unsigned absX=x; unsigned sign=0; //special case if (x==0) return 0; //if x < 0, sign = 1000...,abs_x = -x if (x< 0) { sign=0x80000000; absX=-x; } afterShift=absX; //count shift_left and after_shift while (1) { tmp=afterShift; afterShift< < =1; shiftLeft++; if (tmp & 0x80000000) break; } if ((afterShift & 0x01ff)> 0x0100) flag=1; else if ((afterShift & 0x03ff)==0x0300) flag=1; else flag=0; return sign + (afterShift> > 9) + ((159-shiftLeft)< < 23) + flag; } /* * float_twice - Return bit-level equivalent of expression 2*f for *floating point argument f. 返回以unsinged表示的浮点数二进制的二倍的二进制unsigned型 *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 f = uf; if ((f & 0x7F800000) == 0) // { //左移一位 f = ((f & 0x007FFFFF) < < 1) | (0x80000000 & f); } else if ((f & 0x7F800000) != 0x7F800000) { f =f + 0x00800000; } return f; }

【CSAPP 3e : Data lab】