datalab小记
断断续续写了快一个月，终于是像区一样蠕动完了datalab。不管怎样，还是值得庆祝的。
啪唧啪唧啪唧。
回到正题，下面记录一下我的思路。
1.bitXor
大致要求就是让你用非(~)和与(&)完成异或(^)。 因为学了EDA，所以知道 x^y = ~x&y | x&~y,而或运算可以通过德摩根律化成与和非的运算。 不记得这个公式的话，也可以通过画真值表，用卡诺图化简得到。
int bitXor(int x, int y) { return ~(~(~x&y) & ~(x&~y));}2.tmin
固定返回补码能表示的最小数，即 0x1000 0000。
本题能使用的数值范围（似乎是0-255)有限，不然可以直接返回一个（那就没啥意义了）。
int tmin(void) { return 1<<31;}3.isTmax
判断一个数x是否是最大值，即 0x7FFF FFFF。
该数值有一个关系：~Tmax == Tmax + 1。
但不给用==，所以用其他的符号表示出来: **x == y <=> !(x ^ y) **
int isTmax(int x) { return !(~x ^ (x+1)) & !!(x+1);}4. allOddBits
判断奇数位是否都是1，是则返回1；否则返回0。
对于这种只关心特定数位的，需要用到掩码，即对特定的数值进行位运算。
比如：
&0 屏蔽对应位置； &1 不变；
|0 强制置零； |1 不变；
^ 1 进行翻转； ^0 不变；
像本题，我们需要屏蔽偶数位，来判断奇数位是否全为1，即结果是否等于0xAAAA AAAA。
int allOddBits(int x) { // 因为数值范围的限制，掩码得凑出来。 int mask = (0xAA | 0xAA << 8 | 0xAA << 16| 0xAA <<24); // 判断掩码运算后，结果是否等于0xAAAA AAAA return !((x & mask) ^ mask);}5.negate
就是对一个数取负数，x => -x。
计算机用补码表示数值，这里其实就是把补码变成反码，取反加一即可。
int negate(int x) { return (~x)+1;}6.isAsciiDigit
判断该数字是否属于ASCII码，即 0x30 <= x <= 0x39，是则返回1；否则返回0。
可以先减去一个0x30，y = x + (~0x30 + 1) 把目标范围偏移到 0x0 <= y <= 0x9；
下面就是划分范围进行判断了：
对负数，通过符号位直接返回0；
对正数，可以用 0x9 - y，来判断是否变成了负数，是则说明y大于0x9，不在范围内；反之则在。
int isAsciiDigit(int x) { int y = x +(~0x30 + 1); return !(y >> 31) & !((9+(~y+1)) >> 31);}7.conditional
即实现C语言中的三目运算符(x ? y : z)，在x为非零的时候返回y，在x为零的时候返回z。
选择结构，会想到或运算。同时，我们需要在选择y的时候把z变为0x0000 0000，避免造成干扰；选择z时同理。
而一个不变，一个全部置零，想到的&的掩码运算。想得到这样的结果，这个掩码需要为0x0000 0000 或者0xFFFF FFFF。
掩码需要由x控制。则由x构建出掩码。
int conditional(int x, int y, int z) { int mask = (~x+1 | x) >> 31; // 掩码，x!=0的时候为0xFFFF FFFF，x==0时为0x0000 0000 return (y & mask)|(z & ~mask);}isLessOrEqual
判断 x <= y。
用符号位，负数一定小于正数。同号再进行处理。
int isLessOrEqual(int x, int y) { // 分别得到x，y的符号位 int sign_x = (x >> 31) & 1; int sign_y = (y >> 31) & 1;
//异号情况，x为负，y为正的时候返回1；否则为0 int diff_case = sign_x & !sign_y;
//先判断是同号，然后区分等于和小于的情况。 int diff_sign = ((x + (~y+1)) >> 31) & 1; //判断差的符号位，x<y为1;x>=y为0 int same_case = !(sign_x ^ sign_y) & (!(x + (~y+1)) | diff_sign); return diff_case | same_case;}logicalNeg
实现逻辑非，即0为1，非0为0。
其实这题不是我自己想出来的（。
x为非零的情况下，(x | (~x + 1)一定会是0x1；x为0的情况下，(x | (~x + 1)一定为0x0。
int logicalNeg(int x) { return ((x | (~x + 1)) >> 31) + 1;}howManyBits
判断一个数用多少二进制位可以表示。
观察样例的时候发现正数和负数所用的位数是不同的，负数因为符号位的原因，会少一个。
于是把负数变成正数，统一去找最高位的1。
为了查找最高位的1，用二分法。
int howManyBits(int x) { // 处理x，统一为正数 int mask = x>>31; x = (~x & mask) | (x & ~mask); int b16 = !!(x>>16) << 4; x >>= b16; int b8 = !!(x>>8) << 3; x >>= b8; int b4 = !!(x>>4) << 2; x >>= b4; int b2 = !!(x>>2) << 1; x >>= b2; int b1 = !!(x>>1); x >>= b1; int b0 = x; return b16+b8+b4+b2+b1+b0+1;}floatScale2
给出一个unsigned作为一个浮点数的表示，要我们返回乘2的结果。
回忆IEEE的单精度浮点数表示，最高位是符号位，后8位是exp，最后23位是frac。
乘2，要对exp进行操作。还要针对exp和frac（M）的情况分类讨论。
unsigned floatScale2(unsigned uf) { // 得到阶码 unsigned exp = uf << 1; exp >>= 24; // 得到frac unsigned frac = uf << 9; frac >>= 9; // 得到符号位s unsigned s = uf >> 31;
// 处理NaN和inf if (exp == 255) return uf; // 处理0 if ((uf & 0x7FFFFFFF) == 0) return uf; // 处理非规格化 if (exp == 0) { frac <<= 1; if (frac & 0x800000) { exp = 1; frac &= 0x7FFFFF; } else { exp = 0; } return (s << 31) | (exp << 23) | frac; } // 规格化 exp += 1; if (exp == 255) { frac = 0; } return (s << 31) | (exp << 23) | frac;}floatFloat2Int
把用unsigned表示的浮点数强转为整型，还要注意
int floatFloat2Int(unsigned uf) { // 得到阶码 unsigned exp = uf << 1; exp >>= 24; unsigned e = exp - 127; //得到指数 // 得到frac unsigned frac = uf << 9; frac >>= 9; // 得到符号位s unsigned s = uf >> 31;
// 非规格化数的处理 if (exp < 127) return 0; else if (e >= 31) { // 这里是对超过int范围的情况直接返回最大值。 return 0x80000000u; } else { // 这里则是规格化数的转换 frac |= 0x800000; // 加上隐含的1 if (e <= 23) frac >>= (23-e); else frac <<= (e-23);
if (s) //符号处理 return -frac; return frac; }}floatPower2
返回用unsigned表示的2的x次方(2^x)。
unsigned floatPower2(int x) { unsigned exp,frac; // 溢出的处理 if (x > 127) return 0x7F800000; else if (x >= -126) { // 规格化数 exp = x+127; frac = 0; } else if (x > -149) { // 非规格化数 frac = 1 << (x+149); exp = 0; } else { // 下溢出归零 return 0; }
return exp<<23 | frac;}不得不说，这玩意确实难。听说datalab算这里面最无聊的那个，希望后面的别再这样折磨我了（悲）。
虽然挺多都不是自己独立写出来的，但还算有些收获。期待bomblab。
如果这篇文章对你有帮助，欢迎分享给更多人！