注：这是我的第一篇博客，试图在通往程序猿的路上踏出坚实的一步。 ——小小菜下士
实验来自： 【读厚 CSAPP】I Data Lab
（一）任务目标： 主要是通过这次的作业来熟悉整型及浮点数的位表达形式，简单来说，就是解开一些人工谜题。共6个谜题，我选择其中的若干个进行练习，选择的谜题如下： 一：比特操作谜题： 1.isAsciiDigit(x) ：x 是 ASCII 码吗 难度3 15 2.conditional(x, y, z) ：类似于 C 语言中的 x? y:z 难度3 16 3.logicalNeg(x) ：计算 !x 而不用 ! 运算符 难度4 12 二：整数运算谜题： 1.negate(x) ：不用负号得到 -x 难度3 24 2.isLessOrEqual(x,y) ：x <= y? 难度3 24 3.howManyBits(x) ： 计算表达 x 所需的最少位数 难度4 90
任务指引还是比较清晰的，主要有以下一些说明：
整型的范围是 0 到 255(0xFF)，不允许用更大 只能包含参数和局部变量 一元操作符 ! ~ 二元操作符 & | + << >>不允许的操作有：
使用任何条件控制语句 定义和使用宏 定义其他的函数 调用函数 使用其他的操作符 使用类型转换 使用除 int 之外的类型（针对整型） 使用除 int, unsigned 之外的类型（针对浮点数）可以认为机器：
使用 2’s complent，32位 执行算术右移 移动超过字长的位数会出问题（二）具体实验及说明分析 一：比特操作谜题： 1.isAsciiDigit(x)
short isAsciiDigit(x){ short y; y=!(x>>7)//右移7位判断x的第八位是否为1； return y; } // bits谜题1.isAsciiDigit(x)：x 是 ASCII 码吗? 难度3 int main() { short x,y; scanf("%hd",&x); y=isAsciiDigit(x); if(y==1) printf("x is a Ascii dight!\n"); else printf("x is not a Ascii dight!\n"); return 0; }由于Ascii 对应的十进制数值范围为0—127，二进制表示为0000 0000到0111 1111，所以只要判断第八位是否为1就能知道输入的short 型标量是否为Ascii值，右移7位即可（x>>7）。
2.conditional(x, y, z) 题目要求：same as x ? y : z 例如：conditional(2,4,5) = 4 允许操作：! ~ & ^ | + << >> 操作数限制：16
int conditional(int x, int y, int z){ int exp=0;//exp判断变量 exp=~!x+1;//若x为0，！x为1，~！x+1为0xffffffff; //若x不为1，！x为0，~！x+1为0x0 return (y&~exp)|(z&exp); } int main() { int x=0,y=0,z=0,k=0; scanf("%d,%d,%d",&x,&y,&z); k=conditional(x, y, z); printf("%d",k); return 0; }由于不能使用条件语句，而函数返回的值与y和z有关，所以要构造一个结构为（y&op1）|(z&op2)的表达式，op1与op2由x决定，当x为0时，op1=0x0.op2=0xffff ffff;当x不为0时，op1=0xffff fff,op2=ox0;可想到op1与op的关系，op1=~op2;则有标志标量exp= ~!x+1符合条件。 由代码结果看出，当x为0时，输出第二个数z;当x不为0时，输出第一个数y。 这与x ? y : z功能一致。
3.logicalNeg(x)
int logicalNeg(int x){ int value=~((x^(~x+1))|(x&(~x+1))); return 1&(value>>31); } int main() { int x,k; scanf("%d",&x); k=logicalNeg(x); printf("%d\n",k); return 0; }这个很难，关键是找到表示出1或0的表达式。假如某个非0数x二进制表示为 …1…0(这个1表示最后一个低位不为0的1，1后全为0）x与其补码异或后即x^(~x+1)会有如下形式
1.x: ......(前k位)10... 2.~x+1: .取反..(前k位)“1”0... 3.x^(~x+1): 1..1(前k位)“0”0..0 4.对第三行取反：0000(前k位)1...11 5.对第四行右移31位，得到01）一般情况：此时可以试验下，取…(前30位随意）10（后两位），~x+1=…(前30位随意取反后）10（这里求补码的一个等价方法就是：从右往左数，数到第一个 1 ，这个1前面的取反，其余不变），x^ ( ~x+1)=1111…(前30位为1）00（后两位为0），然后再取反得到0000…(前30个位为0）11（后两位为1），右移31位后得到0。那是不是这样就可以了呢？ 2）特例：想到了补码当中有个特例，那就是最高位为1其余位均为0的二进制数，比如int型的100…(31个0）,它的补码是其本身，这样一来异或之后的前k位均为0，在取反后前k位均为1，右移31位后会得到1，这样与其要求应该得到的！x=0不符合，所以这个特例得处理一下； 为了专门解决这个特例，需要 |（或） 上一个表达式x&(~x+1),情况如下
1.x: 10000...（31个0） 2.~x+1: 10000...（31个0） 3.x&~x+1: 10000...（31个0）整个运算情况如下：
1.x: 10000...(31个0） 2.~x+1: 10000...(31个0） 3.x^(~x+1)：00..00(32个0) 4.x&(~x+1): 1000..(31个0) 5.x^(~x+1) | x&(~x+1) ：100..(31个0) 6.~(x^(~x+1) | x&(~x+1)):0000(31个0)1 7.右移31位：0（奈斯！）,上图表明可以解决100…这个情况，hahahahaha,只剩下x=0的情况：x=0
1.x: 00...（32个0） 2.~x+1: 00...（32个0） 3.x^(~x+1)：00..(32个0) 4.x&(~x+1): 00..(32个0) 5.x^(~x+1) | x&(~x+1) ：00..(32个0) 6.~(x^(~x+1) | x&(~x+1)):111..(32个1) 7.右移31位：111..(32个1) 8.1&(111..(32个1))=1 (奈斯*2)1&（）表示取最低位，也就是符号位。上图中1&“结果值”x=0也是符合的！！! 运行下看看 太好了是对的！ 二：整数运算谜题：
（int） negate(x) 题目要求：return -x 例如：negate(1) = -1. 允许操作：! ~ & ^ | + << >> 操作数限制：5 int negate(int x){ x=~x+1; return x; } int main() { int x=0,k=0; scanf("%d",&x); k=negate(x); printf("%d\n",k); return 0; }有个公式-x=~x+1,按照这个公式写代码就可以了。
2.isLessOrEqual(x,y)
int isLessOrEqual(int x, int y){ int value ; value=((x+(~y+1))>>31)|~(x^y); // x-y即表示为x+(~y+1),右移31位 //(x^y)判断两个数是否相等； //如果相等x^y=0,取反后为1； //最后的结果为1表明x<=y;为0表明x>y; return 1&value; } int main() { int x,y,k; scanf("%d,%d",&x,&y); k=isLessOrEqual(x,y); printf("%d\n",k); return 0; }程序目的是判断x<=y是否成立，若x<=y,则返回1，否则返回0。 1：x=y容易判断，若x=y,则有x^y=0，即~（x ^y）=1; 2：x<y或者x>y,则用减法判断，由于不能使用“-”号，采用~y+1的形式表示-y,则x-y表示为x+( ~y+1)；判断此式的正负性只要判断符号位就行，若符号位为1，则为负数，若为0，则为正数；采用右移31的方式取符号位， 即(x+( ~y+1))>>31)，结果为0xffffffff,即-1则表明x<=y,与1做&运算得到1；结果为0x0,则表明x>y,与1做&运算得到0； 3.综合1与2可知表达式为value=((x+( ~ y+1))>>31)|~(x^y);return 1& value; 下面测试下： 是的都对了！
3.howManyBits(x) ： 题目要求：return the minimum number of bits required to represent x in two’s complement 例如： howManyBits(12) = 5 howManyBits(298) = 10 howManyBits(-5) = 4 howManyBits(0) = 1 howManyBits(-1) = 1 howManyBits(0x80000000) = 32 允许操作：! ~ & ^ | + << >> 下面解释整个代码： 1.temp的作用：x为正数temp就是x，x为负数temp就是按位取反，x=0，temp=0; isZero的作用：用来判断x是否为0，如果x=0，则 isZero=1;如果x!=0，则 isZero=0; notZeroMask的作用：非0标志，x!=0则notZeroMask = 0xffffffff，即-1； 2. int bit_16,bit_8,bit_4,bit_2,bit_1：当x有足够位数时值分别为16，8，4，2，1 以下用bit_16解释：如果高16位有值，需要的位数至少为16（极端情况就是高16位为0…（15个0）1）；如果有值，则需要右移16位来确定x的高16位是从哪一位开始有值，temp=temp>>bit_16表示右移16位；如果高16位没有值，则意味着全0，同样右移16位来寻找最高有效位。 之后右移8位右移4位右移1位与上面类似进行; 3.temp=bit_16+bit_8+bit_4+bit_2+bit_1+2:此处有点难以理解，需要一个符号位，当使用bit_1右移一位时，有两种情况，10和11，右移一位后还有一位1，此时需要加上1；另外需要一个位表示符号位，因此再加1，所以总共+2。
int howManyBits(int x) { int temp=x^(x>>31);//x为正数temp就是x，x为负数temp就是按位取反，x=0，temp=0; int isZero=!temp;//如果x=0，则 isZero=1;如果x!=0，则 isZero=0; int notZeroMask=(!(!temp)<<31)>>31;//notZeroMask is 0xffffffff int bit_16,bit_8,bit_4,bit_2,bit_1; bit_16=!(!(temp>>16))<<4; //see if the high 16bits have value,if have,then we need at least 16 bits //if the highest 16 bits have value,then rightshift 16 to see the exact place of //if not means they are all zero,right shift nothing and we should only consider the low 16 bits temp=temp>>bit_16; bit_8=!(!(temp>>8))<<3; temp=temp>>bit_8; bit_4=!(!(temp>>4))<<2; temp=temp>>bit_4; bit_2=!(!(temp>>2))<<1; temp=temp>>bit_2; bit_1=!(!(temp>>1)); temp=bit_16+bit_8+bit_4+bit_2+bit_1+2;//至少还需要1位，10与11是一样的（at least we //need one bit for 1 to tmax, //and we need another bit for sign return isZero|(temp¬ZeroMask); } int main() { int k,x; scanf("%d",&x); k=howManyBits(x); printf("%d\n",k); return 0; }ok啦，差不多就是这样。感谢你能阅读到文末，看我写的这么繁琐的东西，good luck!
