信息的表示和处理 及 CS:APP 15213 datalab (2)

7. 条件判断，三目运算符， 可用字符 ! ~ & ^ | + << >>
思路：由于 X & 0xFFFFFFFF = X, X & 0x0 = 0, 将两个数和 0xFFFFFFFF, 0x0 做与操作，再相加

只需要找到什么时候为 0xFFFFFFFF 和 0x0, 注意这两者可通过 ~ 得到

/* * 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) { int flag = (!!x + ~0); return (z & flag) + (y & ~flag); }

8. 小于等于 可用字符 ! ~ & ^ | + << >>
思路：判断相等，同符号相减判断是否有进位，不同符号直接判断第一个数的符号是否为 正

/* * isLessOrEqual - if x <= y then return 1, else return 0 * Example: isLessOrEqual(4,5) = 1. * Legal ops: ! ~ & ^ | + << >> * Max ops: 24 * Rating: 3 */ int isLessOrEqual(int x, int y) { int equal = !(x ^ y); // x == y int same_sign = !((x ^ y) >> 31); // sign int x_reduce_y = ~y + 1 + x; return equal | (same_sign & (x_reduce_y >> 31)) | ((!same_sign) & (x >> 31) & 1); }

9. 非运算符 可用字符 ! ~ & ^ | + << >>
思路：核心就是抓住 符号位判断

考虑取反还是取负，取反所有数字的符号位都改变，取负只有 0 和 0x80000000 符号位不变，且这两个符号位相反，所以用取负的方式

将数与其负数直接做与操作，只有 0x80000000，符号为 1 不变，不能筛选出 0 的情况

考虑别的情况，将数取反做与操作，符号相反的数与操作后仍然为 0， 0x800000000 取反(符号为0)与其负数(符号为0)相与也还为 0，只有0取反后符号为1，与操作后仍为1

/* * 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) { return ((~x & ~(~x + 1)) >> 31) & 0x1; }

10. 计算一个最少的补码位可以表达的位数 可用字符 ! ~ & ^ | + << >>
思路：将相邻位做亦或操作，找到最高的位为 1 所在的位
~(bits16 << 3) + 1) + (((bits16 ^ 1) & 0x1) << 3, bits* 为上一个移位的结果，利用这个结果判断是增加位移的大小

/* 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) { // all assignment must be followed by a declaration. int bits16, bits8, bits4, bits2, bits1; int shift16, shift8, shift4, shift2, shift1; int shift_off = 16; // first shift offset x ^= x << 1; // find the highest 1-bit after XOR adjacent bits bits16 = !(x >> shift_off); shift16 = bits16 << 4; // binary search. // if result of prev offset != 0, shift_off should be increasing half prev // offset , else should be decreasing half. shift_off = shift_off + (~(bits16 << 3) + 1) + (((bits16 ^ 1) & 0x1) << 3); bits8 = (!(x >> shift_off)); shift8 = bits8 << 3; shift_off = shift_off + (~(bits8 << 2) + 1) + (((bits8 ^ 1) & 0x1) << 2); bits4 = (!(x >> shift_off)); shift4 = bits4 << 2; shift_off = shift_off + (~(bits4 << 1) + 1) + (((bits4 ^ 1) & 0x1) << 1); bits2 = (!(x >> shift_off)); shift2 = bits2 << 1; shift_off = shift_off + (~(bits2) + 1) + ((bits2 ^ 1) & 0x1); bits1 = (!(x >> shift_off)); shift1 = bits1; }

11. 计算浮点数 f 2, 返回浮点数的二进制位表示, 可用符号不受限制*
思路：由于尾数的值取决于 frac 和 exp，所以要对其分开处理

对于规格数，exp + 1, 但要考虑 +1 后不能为 255

对于非规格数

exp = 255, 直接返回参数

exp = 0, frac = 0 返回 0， 因为这就是个 0

exp = 0， frac != 0, frac 左移一位（尾数取值的问题），又要判断左移后是否溢出（0-22bit）

/* * float_twice - 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 argument * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while * Max ops: 30 * Rating: 4 */ unsigned float_twice(unsigned uf) { int exp = 0x7f800000 & uf; int frac = 0x007FFFFF & uf; int sign = 0x80000000 & uf; int bias = (exp >> 23) - 127; if (uf == 0x0) return 0; if (bias == 128) // NaN return NaN, inf can't *2 return uf; // frac depends on exp, so exp could not add 1 alone. if (exp == 0) { // (exp + frac) << 1 frac = (frac << 1) & 0x007FFFFF; if (uf & 0x00400000) exp = 0x00800000; } else { exp = (exp + 0x00800000) & 0x7F800000; if (exp == 0x7F800000) frac = 0; } uf = sign | exp | frac; return sign | exp | frac; }