写在前面：出于 hornor code 要求，这些答案本不应出现在这里，但是考虑到这些 lab 已经成型了，不同于 CMU15-445 这种每年的 lab 都会变的变态课，csapp 的 lab 答案早已被解析透了，我这里权当个人记录，而且这个 lab “奇技淫巧”的感觉多一些，认真思考后见识一下答案并没有坏处
CSAPP官网：http://csapp.cs.cmu.edu/3e/labs.html
答案版本1：https://github.com/Exely/CSAPP-Labs
答案版本2：https://www.zhihu.com/column/c_1325107476128473088
答案版本3：https://www.bilibili.com/video/BV183411k7VM?p=4
题目一：bitXor
题目描述：请仅使用 ~ 和 & 实现 ^ 操作
允许的操作符：~ &
允许的最大操作数：14
题目分析：德摩根律的运用
题目解答：
int bitXor(int x, int y) {
return ~(~x&~y)&~(x&y);
}
题目二：tmin
题目描述：请返回补码表示的最小integer值
允许的操作符：! ~ & ^ | + << >>
允许的最大操作数：4
题目分析：integer为32bit，为方便分析，以4bit为例，4bit补码中最小的数为-8，即1000，观察可知是由0001左移3位得到
题目解答：
int tmin(void) {
int a = 1;
return a << 31;
}
题目三：isTmax
题目描述：判断x是否为最大integer值，是的话返回1，否则返回0
允许的操作符：! ~ & ^ | + << >>
允许的最大操作数：12
题目分析：integer为32bit，为方便分析，以4bit为例，最大补码值为7，即0111，观察0111有何独特的特征？0111 + 1 的结果和 0111 按位取反的结果是相同的，都是1000，即 (0111 + 1) ^ (~0111) = 0 ，判断两个值相等会经常用到“两数相等异或结果为0”的原理。出于一些对于位操作敏感的嗅觉，还会发现除了0111,1111也具有这个特征，所以还应该排除1111这种情况
题目解答
int isTmax(int x) {
//这里双感叹号的操作可以理解为一个规格化的操作，使所有非0的数都为标准的1，使所有为0的数都为标准的0
return !((x + 1) ^ (~x)) & !!(~x);
}
题目四：allOddBits
题目描述：判断一个数的奇数位是否为1，是的话返回1，否则返回0
允许的操作符：! ~ & ^ | + << >>
允许的最大操作数：10
题目分析：若输入为0xAAAAAAAA，即返回1，以4bit为例，思考1010的结构有什么特点，即如何判断一个数是不是101010...这样的结构，要判断一个数字是不是1010结构，只需要判断这个数和 1010 相 & 的结果是不是 1010 即可，比如1000，他和1010相&的结果是 ：1000 & 1010 = 1000，即1000破坏了1010这种结构，得到了1000。
使用 ^ 判断相等，传统艺能了。
作业要求常量不能大于255即0XFF，所以还有一个问题就是如何得到 0xAAAAAAA? 借用移位的妙招，先构造允许的AA，然后左移为AA00，和AA相加，得到AAAA，然后依次循环得到AAAA
题目解答
int allOddBits(int x) {
int AA = 0xAA;
int AAAA = (AA << 8) + AA;
int A8 = (AAAA << 16) + AAAA;
return !((x & A8) ^ A8);
}
题目五：negate
题目描述：请返回入参x的相反数
允许的操作符：! ~ & ^ | + << >>
允许的最大操作数：5
题目分析：相反数，形式很简单，但是背后却有很深的原理，~x+1，顺便一提，以4bit为例，按位取反加1还是自己的数有两个（0000 和 1000）0和最小值-8
题目解答：
int negate(int x) {
return ~x + 1;
}
题目六：isAsciiDigit
题目描述： return 1 if 0x30 <= x <= 0x39
允许的操作符：! ~ & ^ | + << >>
允许的最大操作数：15
题目分析：间接使用减法
题目解答
int isAsciiDigit(int x) {
int Tmin = 1 << 31;
int diff1 = x + (~0x30 + 1); // x-low
int diff2 = x + (~0x3A + 1);// x-high 303A很灵性
//若x-low为非负数（最高位为0）且x-high为负（最高位为1），就是返回1
int res = (!(diff1 & Tmin)) & (!!(diff2 & Tmin));
return res;
}
题目七：conditional
题目描述：使用位操作实现三元运算符 x ? y : z
允许的操作符：! ~ & ^ | + << >>
允许的最大操作数：16
题目解答
int conditional(int x, int y, int z) {
// !!x为 0000 和 0001， pure 变为了 0000 和 1111
int pure = ~(!!x) + 1;
//原方案为 !!x + (~1 +1) ,即0000和0001变为1111和0000，为了省一步操作，变成了上面的
return (pure&y)|(~pure&z);
}
题目八：isLessOrEqual
题目描述：if x <= y then return 1, else return 0
允许的操作符：! ~ & ^ | + << >>
允许的最大操作数：24
题目分析：直接使用y-x反而会复杂，所以分情况讨论
题目解答
int isLessOrEqual(int x, int y) {
// y-x
// 这个方案有边界bug，对于最小值 1000，-8 ~1000+1结果还是1000，1000 + 1000 得到0000
// 所以增加 | 后面的作为补充这种情况，判断是不是0000，是的话也返回1
//这种减法的方案实现起来有太多边界条件需要考虑，所以需要换一种思路来解决这个问题
//这个不想前面的0x30~0x39的问题有明确的边界，那个不需要考虑边界问题
//减法什么情况下会溢出？在书中学过，是XY不同号的情况下减法会溢出，若xy同号，怎么减都不会溢出的
int signX = (x>>31)&0x1;
int signY = (y>>31)&0x1;
// x == y con1仅在x=y的情况下返回1
int con1 = !(x ^ y);
// x - 最高位1 y + 最高位0，con2仅在 x- y+的情况下返回1 signX & (!signY)
int con2 = (signX) & (!signY);
// x +最高位0 y -最高位1，con3在仅x+ y-的情况下返回0 !signX & signY
int con3 = !((!signX) & (signY));
// x y 同号，con4是x-y的最高位，仅在x<y的情况下返回1
int con4 = (((x + (~y+1))>>31) & 0x1);
return con1 | (con2 | (con3 & con4));
}
题目九：logicalNeg
题目描述：实现逻辑“非”，使用除了!之外的一切操作符
允许的操作符：! ~ & ^ | + << >>
允许的最大操作数：12
题目解答
int logicalNeg(int x) {
//性质：一个非0数和自己的相反数 (都是补码表示），按位或 的结果最高位一定是1 如5 = 0101 -5=1011 4=0100 -4=1100
int negX = ~x+1;
//当x为0时，sign为0000（32bit）；当x非0时，sign为1111（32bit）
int sign = (negX | x) >> 31;
return sign + 1;
}
题目十：howManyBits（此题我分析的不好，建议看其他人的）
题目描述：返回最小的数字-可以表示一个int类型数字的补码
思路：
从右边的最低位一直往左找，直到找到最左边的1
/* howManyBits - return the minimum number of bits re to represent x in
* two's complement
* Examples: howManyBits(12) = 5 0+1100
* howManyBits(298) = 10 0+1 0010 1010
* howManyBits(-5) = 4 1 + 011
* howManyBits(0) = 1
* howManyBits(-1) = 1
* howManyBits(0x80000000) = 32
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/
int howManyBits(int x) {
int isZero = !x; //当x为0时特殊处理
int mask = (!!x << 31) >> 31;
int bit16, bit8, bit4, bit2, bit1, bit0;
int flag = x >> 31;
x = (~flag & x) | (flag & ~x); // 0111 1111 1111 1111 1111 1111 1111 1111
bit16 = (!((!!(x >> 16)) ^ 0b1)) << 4;//16 低位16bit算进去了
x >>= bit16; // 0111 1111 1111 1111
bit8 = (!((!!(x >> 8)) ^ 0b1)) << 3;//8 低位8bit算进去了
x >>= bit8; // 0111 1111
bit4 = (!((!!(x >> 4)) ^ 0b1)) << 2; //4 低位4bit算进去了
x >>= bit4; // 0111
bit2 = (!((!!(x >> 2)) ^ 0b1)) << 1; //2 低位2bit算进去了
x >>= bit2; // 01
bit1 = (!((!!(x >> 1)) ^ 0b1)) << 0; //0 高一半位没1了，所以低一半位不能算进去 bit1=0，合理
x >>= bit1; // x依旧为01
bit0 = x; // x为01 001 0001 均可能
// 最后的+1是符号位
return isZero | (mask & (bit16 + bit8 + bit4 + bit2 + bit1 + bit0 + 1));
}
题目十一：floatScale2
题目描述：入参是unsigned类型的32bit数字，但我们做题人要把这32bit想象成 一个浮点数来对待，因为要求出参为这个浮点数*2 的32bit表示
题目分析：
本题考察对IEEE754标准的是否掌握，需要根据IEEE754的标准，分别取出float中的1bit符号位、8bit解码位、23bit小数位
int floatFloat2Int(unsigned uf) {
//取出1bit符号位，这种取法保持了符号位在最高位，方便后续直接使用或运算将符号位还原到最高位
int sign = uf & (1 << 31);
int exp = (uf >> 23) & 0xFF; //取出8bit阶码位
int frac = uf & 0x7FFFFF; //取出23bit小数位
}
接下来是最关键的地方，要分情况讨论，至于为什么要分情况讨论，我觉得是出于阅读了IEEE754标准后的直觉、再加上一点聪明的头脑、或者是Google了答案哈哈哈
根据754标准，依据exp的不同，把浮点数划分为：规格化、非规格化、特殊值 三类：
//特殊值,依据题目要求，返回自己
if(exp == 0XFF) {
retuen uf;
}
//非规格化的值
if(exp == 0X0) {
retuen uf;
}
//规格化的值
if(exp != 0X0 && exp != 0xFF) {
retuen uf;
}
非规格化的值
在非规格化值的情况下，如何表示2*f ，观察浮点数表达式：
$$
V = (-1)^s \cdot M \cdot 2^E
$$
很显然只要在E的基础上加1，最后的结果就是2倍。
以这个数字为例，exp的8bit都是0，所以这是非规格化的浮点数，E = 1 - Bias = -126，M = 0.f = 1/2 ，V = 2^(-127)：
$$
0， 0000 0000， 100 0000 0000 0000 0000 0000 = 2^{-127}
$$
E+1后，exp的8bit就是0000 0001 ，导致整个数变为规格化的浮点数，E = e - Bias = -126，M = 1.f = 1.5 ，V = 2^(-126) * 1.5：
$$
0， 0000 0001， 100 0000 0000 0000 0000 0000 = 2^{-126} \cdot 1.5
$$
发现不对了，没有变为2倍，而是变成了1.5倍！所以这启发了我们，对于非规格化的浮点数，若使用E+1这种方案，就需要改变exp的解码，但是exp解码一改变，就变成了规格化的浮点数，这就导致M的解释方法变了（从M=0.f变为M=1.f），最终导致计算出来的V值不是乍看上去的2倍了，所以就不要考虑在2^E项上做手脚了，那就考虑让M变为2倍，M作为一个二进制小数，是可以通过左移变为2倍的
然后检查一下边界情况，如果左移把位数M的最高位1移没了怎么办：（即左移把一个非规格化的值变成了一个规格化的值）
$$
0， 0000 0000， 100 0000 0000 0000 0000 0000= 2^{-127}
$$
左移1bit后变成了规格化的值：
$$
0， 0000 0001， 000 0000 0000 0000 0000 0000= 2^{-126}
$$
这得益于IEEE754标准中规格化的值和非规格化的值之间过渡平滑的特性，所以得到结论，如果是非规格化的值，要使用左移，来求得2*f的32bit正确表达
//非规格化的值
if(exp == 0X0) {
retuen (sign | uf << 1);
}
规格化的值
对于规格化的值，就可以通过E+1的方式，但要考虑一下边界情况：比如我们很快能想到exp为1111 1110的情况，E+1后，规格化的值左移变成了特殊值，以这个数字为例：
这是规格化的浮点数，E = e - Bias = 127，M = 1.f = 1.0 ，V = 1：
$$
0， 1111 1110， 000 0000 0000 0000 0000 0000 = 2^{127}
$$
E+1后，变成了正无穷：
$$
0， 11111111， 000 0000 0000 0000 0000 0000 = 正无穷
$$
发现也是合理的，因为float的规格化值上限就是（2-δ）* 2^{127}， 所以2^128在float看来就是会溢出为正无穷
//规格化的值
if(exp != 0X0 && exp != 0xFF) {
retuen sign | (exp + 1) | frac;
}
总结：
int floatScale2(unsigned uf) {
//取出1bit符号位，这种取法保持了符号位在最高位，方便后续直接使用或运算将符号位还原到最高位
int sign = uf & (1 << 31);
int exp = (uf >> 23) & 0xFF; //取出8bit阶码位
int frac = uf & 0x7FFFFF; //取出23bit小数位
//特殊值,依据题目要求，返回自己
if(exp == 0XFF) {
retuen uf;
}
//非规格化的值
if(exp == 0X0) {
retuen (sign | uf << 1);
}
//规格化的值
if(exp != 0X0 && exp != 0xFF) {
retuen sign | (exp + 1) << 23 | frac;
}
}
题目十二：floatFloat2Int
题目描述：要求返回浮点数f的表达式 (int)f 的等效位级表示。入参是unsigned类型的32bit数字，但我们做题人要把这32bit想象成 一个浮点数来对待，因为要求出参为这个浮点数的转换为int后的值，超过范围的返回 0x80000000u
举个例子，输入为：
$$
0,10000010,00110100000000000000000
$$
这32bit按照IEEE754标准代表浮点数9.625：
$$
V = (-1)^s \cdot M \cdot 2^E = 1\cdot1.001101\cdot2^{130-127} = (1+1/8+1/16+1/64) \cdot2^3 = 9.625
$$
在C语言中，浮点数转整形是向零舍入的，所以
$$
int(9.625) = 9
$$
输出应为：
$$
0000 0000, 0000 0000, 0000 0000,00001001
$$
题目分析
对于绝对值小于1的浮点数，返回的值应该是0
对于绝对值大于1的浮点数，返回的值是这个浮点数的整数部分
按照上一题的思路，尝试进行分类讨论，依旧是先取出三元组：符号位、阶码位、尾数位：
int floatFloat2Int(unsigned uf) {
//取出1bit符号位，这种取法保持了符号位在最高位，方便后续直接使用或运算将符号位还原到最高位
int sign = uf & (1 << 31);
int exp = (uf >> 23) & 0xFF; //取出8bit阶码位
int frac = uf & 0x7FFFFF; //取出23bit小数位
int E = exp - 127;//这里E = 1-Bias的情况其实会包含在E<0的情况中
}
这道题用IEEE754浮点数公式的“二进制理解”更容易理解，回顾公式：
$$
V = (-1)^s \cdot M \cdot 2^E
$$
这个公式可以理解成将M代表的二进制小数（1.xxx或0.xxx）的小数点左移或者右移，比如：
$$
V = (-1)^0 \cdot 1.0011 \cdot 2^3
$$
就可以解释为将1.0011的小数点往右移动3bit，所以V的值就是$1001.1$，而小数点左边的1001就是我们要的整数答案
所以这题的解题思路就是：想办法得到小数点移位结束之后的、小数点左边的二进制表示的十进制数字（比如上面这个例子中的1001）
分情况讨论的关键在于：E的值，即小数点到底右移、左移几位？
情况1：E < 0，由于M是1.xxx或0.xxx，M表示的二进制小数 小数点左边只有一位，E小于0表示小数点至少往左边移动一位，所以移动完成后，小数点的右边一定是0，即整数部分是0，这种情况下，直接返回0就是要求的答案。
情况2：E>= 32，表示M一定是1.xxx（因为E等于-126时M才是0.xxx），如果E >= 32，表示小数点要往右移动32bit，但是int类型最多32bit，所以会爆掉，按照题目要求返回 0x80000000u
情况3：0 <= E < 32
这里需要先把frac23bit前面的1补上，即$(1<<23) | frac$，这个表达式代表M，如M = 1.11001，则这个表达式就是11100100......000（共24bit）
当E>=23时，表示小数点右移可以把M小数点右边的23bit小数都吃掉，还能给后面继续补0，所以直接返回24bit+（补的几个0） 即可。
当E<23时，表示小数点右移不能把M小数点右边的23bit小数都吃掉，只能吃掉一部分，所以返回24bit右移“割舍的bit”
frac = frac|1<<23;
if(E<23) {
frac>>=(23 - E);//割舍
} else{
frac <<= (E - 23);//继续补0
}
总结：
int floatFloat2Int(unsigned uf) {
int sign = uf & (1 << 31);
int exp = (uf >> 23) & 0xFF; //取出8bit阶码位
int frac = uf & 0x7FFFFF; //取出23bit小数位
int E = exp - 127;//这里E = 1-Bias的情况其实会包含在E<0的情况中
frac=frac|1<<23;
if(E<0) return 0;
if(E >= 31){
return 0x80000000u;
}
if(E<23) {//需要舍入
frac>>=(23-E);
}else{
frac <<= (E - 23);
}
if(sign) {
return ~frac + 1;
} else {
}
}
题目十三：floatPower2
题目描述：要求返回浮点数f的表达式 2.0^x 的等效位级表示。入参是 int 类型的32bit数字，出参是unsigned类型；结果太小的话返回0，太大的话返回+INF
unsigned floatPower2(int x) {
return 2;
}
题目分析：本题考察浮点数的表示范围。与前面两道题目不同，入参是一个int类型的数字，前两题入参形式上是unsifgned，但是出题人要求我们看成32bit的单精度浮点数float，然后去表达2*f、int(f)等的位级表示；但是此题输入的确就是一个整型，题目要求也是把入参看成整型。但是出参是一个浮点数
先回答一个问题，2.0x次方长什么样，float如何存储2.0x？
情况一，都是0：
……
2-150的二进制表示为0|00000000|00000000000000000000000
情况二，阶码0，可以观察到是由1左移获得的，从理论上分析是因为M = 0.000x，E = -126
-------------------------------------------------------------------
2-149的二进制表示为0|00000000|00000000000000000000001
2-148的二进制表示为0|00000000|00000000000000000000010
2-147的二进制表示为0|00000000|00000000000000000000100
……
2-129的二进制表示为0|00000000|00100000000000000000000
2-128的二进制表示为0|00000000|01000000000000000000000
2-127的二进制表示为0|00000000|10000000000000000000000
情况三，阶码非0：
-------------------------------------------------------------------
2-126的二进制表示为0|00000001|00000000000000000000000
2-125的二进制表示为0|00000010|00000000000000000000000
2-124的二进制表示为0|00000011|00000000000000000000000
……
20 的二进制表示为0|01111111|00000000000000000000000
21 的二进制表示为0|10000000|00000000000000000000000
……
2127 的二进制表示为0|11111110|00000000000000000000000
情况四，无穷大：
2^128 的二进制表示为0|11111111|00000000000000000000000
2^129 的二进制表示为0|11111111|00000000000000000000000
看到本题要敏感，2.0的x次幂，正好是IEEE754标准的最后一项：
$$
V = (-1)^s \cdot M \cdot 2^E
$$
只要保证M是1.000......00，s是0，或者（M是0.000x,小数点右边只有一个1），最后的结果就是本题要求的结果，所以尝试把入参x看作最后一项的E来进行思考
单精度浮点数的表示范围如上图所示：
分析题目，2.0x一定是个正数，所以最后的表达式一定大于0，float的符号位一定是0，就从图上零点右边开始分析：
情况1：非规格化值能表示的最小2.0x是2-149，所以x<-149时，float无法表示，直接返回0
情况2：规格化值能表示的最小2.0x是2-126，所以-149 <= x < -126时，是非规格化的值可以表示的，非规格化的值特点是阶码exp为0，E = 1 - Bias = -126,，比如x是-130，$V = 2^{-126} * 2^{-4}$，所以M = 2-4，要返回2-130的float表示就是0 ，0000 0000， 000 01000 00000 00000 00000，可以看到是1左移了19bit，19=23-4
情况3：规格化值能表示的最大2.0x是2127，所以 -126 <= x <= 127时，要使V是2.0x，需要M是1.000......00，这个很简单，直接把exp的值<<23bit即可，exp = E +Bias(E就是x)
情况4：x > 127时，float无法表示了，返回+INF
unsigned floatPower2(int x) {
//比float最小值还小，无法使用float表示，return 0
if(x < -149) return 0;
//非规格化的数，M=0.000x,E = 1-Bias = -126，exp = 0000 0000
if(x < -126){
int shift = 23 + (x + 126);
return 1 << shift;
}
//规格化的数
if(x <= 127) {//需要舍入
int exp = x + 127;
return exp << 23;
}else{//比float最大值还大，无法使用float表示，return 正无穷
return 0XFF << 23;
}
}
