课程首页

目录

信息的表示和处理浮点数注意 lab1

信息的表示和处理

浮点数

在规格化数中，需要加入bias偏置项，需要注意的是，e全0（非规格化数）与e为0x01表示的指数值相同，由于尾数自动从0.变成了1.0，从而实现了平稳过渡。从lab1中的实验可以进行验证。

注意

由于浮点数由指数和尾数两部分固定长度组成，随着数字变大，表示的精度会变小。如下图

有符号数右移时，符号位如果是1，则会进行补1。

负数的一种计算方式是-x = (~x) + 1，因此有-INT_MIN = INT_MIN。

补补得原。

负数的补码, -3 = 1111 1101 = 111 1101 = 1101，这个性质后面会用到。

以-3 = 1111 1101为例，负数的补码也可以看成-2⁸+2⁷+2⁶+2⁵+2⁴+2³+2²+2⁰。

lab1

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

本来a^b = (a&b) | ((~a)&(~b))和a|b = ~((~a)&(~b)可以得到。

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

int32位的最小值为 0x80000000

int isTmax(int x) { //a == b -> !(a^b) return !((~0) ^ (x ^ (x + 1))) & !!(x+1); }

如果是可以验证发现，只有x = 0X7FFFFFFF或者x=-1时!((~0) ^ (x ^ (x + 1))) = 1，再通过!!(x+1)拒绝x = -1的情况。

/* * 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 flag = 0xAA; flag = (flag << 8) + flag; flag = (flag << 16) + flag; return !(flag ^ (x & flag)); }

首先使用&运算只保留奇数位置上的数。再判断是否和奇数位全1的数字是否相等。

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

(~x) + 1本身就是取反的一种实现，比如在-INT_MIN == INT_MIN会返回true。

/* * 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 ans1 = !((x + (~0x30) + 1) >> 31); int ans2 = ((x + (~0x3A) + 1) >> 31); return ans1 & ans2; }

通过x-0x30 和x-0x3A的符号进行判断，关于数字溢出，可以通过区间判断得出溢出时也会返回正确结果。

/* * 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 mask = (!x) + (~1) + 1; return (mask & y) | (~mask & z); }

巧妙的使用mask，当x为真时,mask 为全1，当x为假时mask为全0。

/* * 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 signx = (x >> 31) & 1; int signy = (y >> 31) & 1; int isSameSign = !(signx ^ signy); int sub = (y + (~x) + 1) >> 31; return (isSameSign & (!sub)) | ((!isSameSign) & signx); }

简单做差判符号会有不同号溢出问题，因此添加一个同号和非同号的判断。

/* * 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) + 1; }

技巧性比较强，参考http://zhouni.net/questions/a19511558888145.html。

/* 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 b16,b8,b4,b2,b1,b0; int sign=x>>31; x = (sign&~x)|(~sign&x);//如果x为正则不变，否则按位取反（这样好找最高位为1的，原来是最高位为0的，这样也将符号位去掉了） // 不断缩小范围 b16 = !!(x>>16)<<4;//高十六位是否有1 x = x>>b16;//如果有（至少需要16位），则将原数右移16位 b8 = !!(x>>8)<<3;//剩余位高8位是否有1 x = x>>b8;//如果有（至少需要16+8=24位），则右移8位 b4 = !!(x>>4)<<2;//同理 x = x>>b4; b2 = !!(x>>2)<<1; x = x>>b2; b1 = !!(x>>1); x = x>>b1; b0 = x; return b16+b8+b4+b2+b1+b0+1;//+1表示加上符号位 }

此题需要对负数补码的性质有一个清晰的理解。参考CSAPP 之 DataLab详解，没有比这更详细的了

//float /* * 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 argument * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while * Max ops: 30 * Rating: 4 */ unsigned floatScale2(unsigned uf) { if ((uf & 0x7F800000) == 0x7F800000) return uf; if (uf & 0x7F800000) { //e != 0 uf = uf + 0x00800000; } else { return ((uf & 0x007FFFFF) << 1) | (uf & 0x80000000); } return uf; }

对阶符全0进行特判，在判断阶符是否全为0，如果全为0，只需要右移尾数，不全为0，则使阶符号+1。

/* * 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) { int e = uf & 0x7F800000; int frac = uf & 0x007FFFFF; int n = (e >> 23) - 127; if (n < 0) return 0; if (n >= 31) return 0x80000000u; frac = frac + 0x00800000; //1.xxx if (n <= 23) frac = (frac >> (23 - n)); else frac = (frac << (n - 23)); if (uf & 0x80000000) return -frac; else return frac; } /*

根据题意，先对阶数进行下溢和上溢特判，之后得到完整的尾数ans = frac + 0x00800000，再根据阶数判断完整的尾数是左移，还是右移处理。

/* * 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 */ #include<stdio.h> unsigned floatPower2(int x) { if (x > 127) return 0x7F800000; if (x >= 0) return (x << 23) + 0x3F800000; //x < 0 if (x < -(23 + 126)) return 0x0; if (x <= -126) return 1 << ((-x) - 126); else return ((-x) + 127) << 23; }

这题难度不大，坑就坑在这题样例非常多，默认10秒机子性能不好的话会超时。太坑了