记录一下自己所完成CSAPP的第一次Lab。
在限制了条件和循环的情况下，使用位运算进行各种操作的实现，的的确确需要对Int和Float的存储有比较深入的认知。

我所完成的Lab，一共有13个函数需要实现，满分为36分。

Lab

1 bitXor 位异或

只允许使用&和~进行异或Xor的实现，结合上一张的知识，实际上就是类似于NMOS和PMOS电路的组装，如何利用真值表和高低电压保证输出。
最后使用了8/14个ops完成，具体代码如下

/* * bitXor - x^y using only ~ and & *   Example: bitXor(4, 5) = 1*   Legal ops: ~ &*   Max ops: 14*   Rating: 1*/
int bitXor(int x, int y) {int a=(~x)&y;int b=x&(~y);int c=~((~a)&(~b));return c;
}

2 tmin 有符号整数最小值

理解了补码最高位的负权，就很容易知道最小值为0x80000000

/* * tmin - return minimum two's complement integer *   Legal ops: ! ~ & ^ | + << >>*   Max ops: 4*   Rating: 1*/
int tmin(void) {int a=1<<31;return a;
}

3 isTmax 判断是否是有符号整数最大值

Tmax=0x7FFFFFFF，本体不能使用移位操作，因此必须想办法通过~运算得到较高位为1的数字。
思路上大概有两种：

• 利用Tmax+1=Tmin，而Tmin和0都是补码==自身性质进行判断，之后排除特殊项0即可。
• 利用移位操作，只有Tmax<<1=-2 和 -1<<1=-2，所以对-1进行排除即可，使用-1+1=0进行排除。

下列代码使用了思路2，思路1是做完后从别人那借鉴来的。

/** isTmax - returns 1 if x is the maximum, two's complement number,*     and 0 otherwise *   Legal ops: ! ~ & ^ | +*   Max ops: 10*   Rating: 1*/
int isTmax(int x) {// ! can transfer any number that is not zero to zero , but transfer zero to 1int sum=x+x;int pattern=(~0)^1;int add=x+1;int code1=!(sum^pattern);int code2=!(!add);int result=code1&code2;return result;
}

4 allOddBits 判断是否所有奇数位都为1

利用&和|操作，将符合条件的数转化为0xFFFFFFFF，之后利用！进行转化即可。

/* * 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*/
int allOddBits(int x) {int hex_pattern=(85<<8)+85;int pattern1=(hex_pattern<<16)+hex_pattern;int pattern2=pattern1<<1;int code=(x&pattern2)|pattern1;int result=!(~code);return result;
}

5 negate 返回相反数

补码在实现上可以利用反码+1实现，当在理解上这很不利。

/* * negate - return -x *   Example: negate(1) = -1.*   Legal ops: ! ~ & ^ | + << >>*   Max ops: 5*   Rating: 2*/
int negate(int x) {int result=(~x)+1;return result;
}

6 isAsciiDigit 判断是否是Ascii的数字

利用之后的isLessOrEqual思想实现即可，本质上是整数加法+符号判断。

/* * 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*/
int isAsciiDigit(int x) {int com=(~48)+1;int sub=x+com;int code1=sub>>31;int com2=(~x)+1;int sub2=57+com2;int code2=sub2>>31;int code=(code1|code2);code=code+1;return code;
}

7 conditional 实现三元运算符x？y：z

利用！运算符，实现对于0和非0的转化，实现0和-1的编码，之后利用不同的编码对y和z进行&运算。

/* * conditional - same as x ? y : z *   Example: conditional(2,4,5) = 4*   Legal ops: ! ~ & ^ | + << >>*   Max ops: 16*   Rating: 3*/
int conditional(int x, int y, int z) {//x=0, a=0xFFFFFFFF//x!=0,a=0int a=(!x)<<31>>31;int result=(z&a)+((~a)&y);return result;
}

8 isLessOrEqual 判断x<=y

等价于y-x>=0，即y-x的符号位为0。
在将y-x转化为y+x_com时，另外还有两个需要额外注意的点：

1. overflow溢出，因此需要对y、x_com和sub的符号位进行检查，以确定真实结果的符号位。
2. Tmin，Tmin的补码为自身，但好在x=Tmin时，必然返回1

/* * isLessOrEqual - if x <= y  then return 1, else return 0 *   Example: isLessOrEqual(4,5) = 1.*   Legal ops: ! ~ & ^ | + << >>*   Max ops: 24*   Rating: ./*/
int isLessOrEqual(int x, int y) {int y_sign=y>>31;int x_com=(~x)+1;int x_sign=x_com>>31;//codeMin is used for x=Tminint codeMin=!(x^(1<<31));int sub=y+x_com;int sub_sign=sub>>31;int overflow_flag=(x_sign^y_sign)|(x_sign^(~sub_sign));int code1=!!(sub_sign);int code2=!!(overflow_flag);int result=(code1^code2)|codeMin;           return result;
}

9 logicalNeg 判断是否为0

0具有特点：0的补码还是0，且符号位为0。
因此利用补码和自身的Xor，以及排除Tmin的干扰即可。

/* * 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 */
int logicalNeg(int x) {// use ~&|+<<>> to achieve !// only x=0 st x>=0 and x<=0// x>=0 & x_com>=0// Tmin is also same to Tmin_com, but Tmin<0int x_com=(~x)+1;int x_sign=x>>31;int xcom_sign=x_com>>31;int code=(x_sign|xcom_sign)+1;return code;}

10 howManyBits 当前数所需的最小位数

首先观察到负数x所需的位数和其反码的结果一致，因此将所有负数都转化为正数进行讨论。
其次，因为操作数ops的限制没有办法，进行32次的移位以及是否为0判断，采用二分思想，分割到只剩8位时，剩余ops够用就直接ctrl c+v了。
因此代码有点丑陋。

/* 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*/
int howManyBits(int x) {int code=x>>31;int pos=((~code)&x)+(code&(~x));int cur=1;//halfint mid=1<<16;int mid_com=(~mid)+1;int sub=pos+mid_com;// 1<<16<=x,larger_one=0xFFFFFFFF;1<<16>x,larger_one=0int larger_one=~(sub>>31);pos=pos>>(16&larger_one);cur+=(16&larger_one); //16 ops//half of halfmid=1<<8;mid_com=(~mid)+1;sub=pos+mid_com;larger_one=~(sub>>31);pos=pos>>(8&larger_one);cur+=(8&larger_one); //26 ops//now at least 24 bit is zerocur=cur+(!!pos);pos=pos>>1;cur=cur+(!!pos);pos=pos>>1;cur=cur+(!!pos);pos=pos>>1;cur=cur+(!!pos);pos=pos>>1;cur=cur+(!!pos);pos=pos>>1;cur=cur+(!!pos);pos=pos>>1;cur=cur+(!!pos);pos=pos>>1;cur=cur+(!!pos);return cur;
}

11 floatScale2 浮点数×2

可以使用if后，只需要进行分情况讨论即可。

1. 对于无穷和NaN，返回uf即可。
2. 对于阶码为0，直接相加即可。
3. 对于阶码规范，阶码+1。

/* * 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 a rgument*   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while*   Max ops: 30*   Rating: 4*///finish
unsigned floatScale2(unsigned uf) {unsigned a=uf>>23;unsigned b=a&255;unsigned c=(b<<8)+b;unsigned code=(c<<16)+c;unsigned m=uf<<9>>9;unsigned result=m+uf;unsigned add=1<<23;unsigned result2=uf+add;// E is 11111111if(!(~code))return uf;// E is 00000000if(!code)return result;// 00000001<=E<=11111110return result2;
}

12 floatFloat2Int 浮点转整型

只能说还好舍入规则简单，而且可以使用大于>和小于<符号，不然一直补码+移位+！+！的操作进行逻辑判断，ops完全不够用。
一样针对，<0、>=2^31、<- 2^31的情况进行特殊处理，之后利用M* 2 ^ E的方法进行计算，并且对负数取补码。

/* * 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*/
int floatFloat2Int(unsigned uf) {//E<=125 -> int=0//unsigned is 0 fillint S=(uf>>31);int E=(uf<<1)>>24;unsigned M=((uf<<9)>>9)+(1<<24);//6 opsint Bias=127;int Bias_com=(~Bias)+1;int iE=E+Bias_com;int minus24=(~24)+1;int Diff=iE+minus24;int Diff_com=(~Diff)+1;int result1=(M<<Diff);int result2=(M>>Diff_com);int result3=(~result1)+1;int result4=(~result2)+1;//too smallif(iE<0)return 0;//too largerif(iE>30)return 1<<31;// <0if(S>0){if(Diff>0)return result3;return result4;}if(Diff>0)return result1;return result2;
}

13 loatPower2 返回2^x

使用浮点数返回2的次方，进行分情况讨论即可。

/* * 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*/
unsigned floatPower2(int x) {//x>=128  7int a=128;int a_com=(~a)+1;int sub1=a_com+x;int code1=sub1>>31;unsigned inf=255<<23;unsigned zero=0;unsigned normal=(x+127)<<23;unsigned non_normal=1<<(x+149);int a1=150;int a_com1=(~a1)+1;int x_com=(~x)+1;int sub2=x_com+a_com1;int code2=sub2>>31;int a2=127;int a_com2=(~a2)+1;int sub3=a_com2+x_com;int code3=sub3>>31;if(!code1)return inf;//x<=-150  7if(!code2)return zero;//-149<=x<=-127  6if(!code3)return non_normal;//126<=x<=127  2return normal;
}

总结

不得不承认，这些实验的设计着实让我费尽心思地去思考Int和Float的存储格式，受益匪浅。
第一次提交的时候来了个20/36的分数，其中logicalNeg和floatFloat2Int两道4分题，直接理解错题意，真的好笑。
Lab算是写了1天，然后Debug花了额外1天，算是花了两天才写完吧，有点费劲的。
——2023.3.17