CSAPP实验——datalab

官网

http://csapp.cs.cmu.edu/3e/labs.html

Students implement simple logical, two’s complement, and floating point functions, but using a highly restricted subset of C. For example, they might be asked to compute the absolute value of a number using only bit-level operations and straightline code. This lab helps students understand the bit-level representations of C data types and the bit-level behavior of the operations on data.

参考

Introduction to CSAPP（八）：Datalab

CSAPP:datalab

CSAPP 之 DataLab详解，没有比这更详细的了

《深入理解计算机系统》（CSAPP）实验一 —— Data Lab

bitXor

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

用~和&表示异或运算。根据异或运算公式Y = A'·B + A·B' = (A'·B)' · (A·B')' 即可。

tmin

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

返回补码的最小值，补码最小值就是符号位为1，其余全为0。直接位移可得。

isTmax

/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTmax(int x) {
   int i = x + 1; //Tmin,1000...
   x = x + i; //-1,1111...
   x = ~x; //0,0000...
   i = !i; //exclude x=0xffff...
   x = x + i; //exclude x=0xffff...
   return !x;
}

通过位运算计算是否是补码最大值。最大值为符号位为0，其余全1。最后两行是排除x=0xffff的情况，因为0xffff也有前三行的性质。

allOddBits

/*
 * 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 mask = 0xAA + (0xAA << 8) + (0xAA << 16) + (0xAA << 24);
	//mask & x  留下奇数位的1
	//mask ^ (mask & x) 奇数位为1，则异或后变0
    return !(mask ^ (mask & x));
}

mask变量的所有奇数位都为1，偶数位为0。经过与运算和异或运算后，只有在x为0的奇数位上，mask ^ (mask & x)值为1。若x的所有奇数位都为1，则最终结果mask ^ (mask & x)为全0，经过非运算后返回值为1。

negate

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

重要结论：x + ~x + 1 = 0。已知x补码，求-x的补码：将x补码各位取反（包括符号位）再加1。

isAsciiDigit

/* 
 * 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 lowerBound = 0x39 + ~x + 1;
   int upperBound = x + ~0x30 + 1;
   return !((lowerBound | upperBound) >> 31);
}

分别计算x-'0'和'9'-x，两结果的符号位皆为0即返回1。

conditional

/*
 * 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) {
   x = !!x; //逻辑运算变为0 or 1
   x = ~x + 1; //若x为True，则x补码全1；若x为False，则x补码全0
   return (x & y) | (~x & z);
}

使用位级运算实现三目运算符。根据 x 的布尔值转换为全0或全1来解决。

isLessOrEqual

/*
 * 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 subtraction = y + (~x + 1); //y-x
   int subtractionSign = (subtraction >> 31) & 1; //y-x的符号
   int xSign = (x >> 31) & 1; //x的符号
   int ySign = (y >> 31) & 1; //y的符号
   int bitXor = xSign ^ ySign; //x和y符号相同标志位，相同为0不同为1
   //返回1有两种情况：1、bitXor为0（符号相同），y-x 的符号为0（y-x>=0）；2、bitXor为1（符号不同）位与x的符号位为1（x<0）
   return ((!bitXor) & (!subtractionSign)) | (bitXor & xSign);
}

二者的差值可能过大而溢出，所以仅通过subtractionSign来判断是不行的。

logicalNeg

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

0和最小数的补码是本身，二者的补码一个全0，一个全1。如果是0，位或操作之后符号位为0，位移后为0，返回值1。如果非0，位或操作之后符号位为1，位移后为全1，即值为-1，返回值为0。

howManyBits

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

如果是正数，则需要找最高的为1的一位数是第几位，再加上符号位，结果为n+1；如果是负数，则需要知道其最高的一位是0的（例如4位的1101和三位的101补码表示的是一个值：-3，最少需要3位来表示），按位取反转换为正数做同样处理。

floatScale2

/* 
 * 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) {
   int exp = (uf & 0x7f800000) >> 23; //阶码
   int sign = uf & (1 << 31); //符号位
   if (exp == 0) return uf << 1 | sign; //uf无穷小和0的情况，将原数乘二再加上符号位就行了（并不会越界）
   if (exp == 255) return uf; //无穷大和NaN的情况，只需要返回参数
   exp++; //直接整体左移保持符号位不变即可实现乘2操作
   if (exp == 255) return 0x7f800000 | sign; //指数+1之后为指数为255则返回原符号无穷大
   return (exp << 23) | (uf & 0x807fffff); //指数+1之后的原符号数
}

复习了一下32位浮点数的表达方式。NaN：阶码全为1，尾数非0；无穷大：阶码全1，尾数全0；非规格化的值：阶码全0。

根据输入的数值，可以分为三种情况：

输入uf为无穷大和NaN，直接返回uf
uf为0或无穷小，返回2*uf | sign
若exp+1 == 255，返回无穷大，否则返回 exp+1。（exp为浮点数编码的整数部分，exp+1相当于uf*2。）

floatFloat2Int

/*
 * 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 sign = uf >> 31; //符号位
   int E = ((uf & 0x7f800000) >> 23) - 127; //阶码
   int frac = (uf & 0x007fffff) | (1 << 23); //算上默认的1
   if (!(uf & 0x7fffffff)) return 0; //原浮点值为0
   if (E < 0) return 0; //小数
   if (E >= 31) return 0x80000000u; // 超出int范围
   if (E < 23) frac >>= (23 - E); //舍去部分小数
   else frac <<= (E - 23); //不需要舍去小数
   if (sign) return -frac;
   else return frac;
}

非规格化，表示非常接近0的数，转换为int值后为0
规格化，数的分布从接近0到无穷越来越稀疏，当f不超过int型表示的范围时，转换为int；当超过int型表示的范围时返回0x80000000u
特殊，返回0x8000000u

在规格化的float转换为int型整数时，

如果E >= 31，小数点右移31位，此时隐含的1和frac占32位，另外还需要一个符号位，超出了int型范围
如果E < 0，小数点左移1位后为0.1frac，转换为int后为0
如果0 < E < 23, 小数点左移E位后需要舍弃frac中部分位，此时直接将frac右移23-E位，抹去小数部分
如果23 <= E < 31，此时小数点右移后frac全部移到小数点以左，将frac左移E-23位，在后面补零

floatPower2

/*
 * 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
 */
unsigned floatPower2(int x) {
   if (x >= -149 && x <= -127) return 1 << (149 + x); //for denormal number
   // 2.0^x = (1.0 * 2^1)^x = 1.0 * 2^x
   int exp = x + 127;
   if (exp <= 0) return 0;
   if (exp > 255) return 0x7f800000; //返回INF
   return exp << 23; //直接将阶码左移23位，尾数全0
}