这是《深入理解计算机系统》的第一个实验(文件下载),从大一下的期中开始做,直到暑假才得以完成(答案)。本实验要求对计算机编码的了解和一定的编程技巧,有很高的趣味性。 ​

位操作

BitAnd

用德摩根律轻松解决。

/*
* bitAnd - x&y using only ~ and |
*   Example: bitAnd(6, 5) = 4
*   Legal ops: ~ |
*   Max ops: 8
*   Rating: 1
*/
int bitAnd(int x, int y) {
  return ~(~x|~y);
}

GetByte

一个字节等于8位,所以先将n乘上8,也就是是左移3位,然后再将x右移8*n位,把要获取的字节放在最右端,然后用0xFF把最右端的字节提取出来。

/* 
 * getByte - Extract byte n from word x
 *   Bytes numbered from 0 (LSB) to 3 (MSB)
 *   Examples: getByte(0x12345678,1) = 0x56
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int getByte(int x, int n) {
  return (x>>(n<<3))&0xFF;
}

LogicalShift

先将数x做符号右移,然后想办法将左端不该出现的1全部变为0。如果一个数右移n位,那么从左往右的n位要全部设为0,我就构造一个左往右的n位为0,剩下位置全为1的数,然后将x»n与这个数做“与”操作。具体的构造方法:先用0x1«31生成数0xA0000000(第一位都是1),然后将数0xA000000右移n-1位,这里不能用减号,所以用((0X1«31)»n)«1实现,得到一个左往右的n位为1,剩下位置全为0的数,然后取反即可。

/* 
 * logicalShift - shift x to the right by n, using a logical shift
 *   Can assume that 0 <= n <= 31
 *   Examples: logicalShift(0x87654321,4) = 0x08765432
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3 
 */
int logicalShift(int x, int n) {
  return (x>>n)&~(((0X1<<31)>>n)<<1);
}

BitCount

使用二分法累加,过程中需要构造一些特殊的二进制序列来实现这个过程

/*
 * bitCount - returns count of number of 1's in word
 *   Examples: bitCount(5) = 2, bitCount(7) = 3
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 40
 *   Rating: 4 
 */
int bitCount(int x) {
  /* Generate 0x55555555 */
  int mask = 0x55;
  mask += mask<<8;
  mask += mask<<16;
  x = ((x>>1)&mask) + (x&mask);
  /* Generate 0x33333333 */
  mask = 0x33;
  mask += mask<<8;
  mask += mask<<16;
  x = ((x>>2)&mask) + (x&mask);
  /* Generate 0x0F0F0F0F */
  mask = 0x0F;
  mask += mask<<8;
  mask += mask<<16;
  x = ((x>>4)&mask) + (x&mask);
  /* Generate 0xFFFFFFFF */
  mask = 0xFF;
  mask += mask<<16;
  x = ((x>>8)&mask) + (x&mask);
  x += x>>16;
  return x&0xFF;
}

Bang

由于这是“非”的操作,所以要先取反。设想一种折叠操作,将一个n长的数(二进制数的角度)分为两半,将两部分进行合取生成一个长为n/2的数。将一个数不断折叠,直到折叠到最右端的那一位,然后用0x1合取出最右端的那一位。

/* 
 * bang - Compute !x without using !
 *   Examples: bang(3) = 0, bang(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int bang(int x) {
  x = ~x;
  x = (x>>16)&x;
  x = (x>>8)&x;
  x = (x>>4)&x;
  x = (x>>2)&x;
  x = (x>>1)&x;
  return x&0x1;
}

补码运算

Tmin

这太简单了,把0x1左移31位就好。

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

Divpwr2

如果参数是正数,直接位移就好了,但如如果是负数的话要在位移之前给参数加上2^n-1。我们要好好利用一下符号位,把整数右移31位,如果是正数,得到0x0,如果是负数,得到0xffffffff,将结果与2^n-1做合,这样就可以根据符号来决定是否需要加上2^n-1了。

/* 
 * divpwr2 - Compute x/(2^n), for 0 &lt;= n &lt;= 30
 *  Round toward zero
 *   Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
 *   Legal ops: ! ~ &amp; ^ | + &lt;&lt; &gt;&gt;
 *   Max ops: 15
 *   Rating: 2
 */
int divpwr2(int x, int n) {
	int bias = (x>>31)&~(((0x1<<31)>>31)<<n);
  	return (x+bias)>>n;
}

Negate

这个也好简单,取反加1就好。

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

IsPositive

把数x右移31位后与0x1进行“与”运算,就可以获取数字的符号位,如果是负数那么符号位就是1,对符号位取反,如果数是正数或者0,结果就是1。接下来还要处理一下0的情况,用!!x就好,如果是零就返回0。两个表达式取合,就得到了结果。

/* 
 * isPositive - return 1 if x > 0, return 0 otherwise 
 *   Example: isPositive(-1) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 3
 */
int isPositive(int x) {
  return !((x>>31)&0x1)&!!x ;
}

IsLessOrEqual

一下三种情况,函数返回1: ​

  1. 两个数x,y相等: !(x^y);

  2. X符号为负,y符号为正: (sgnx&!sgny);

  3. X和y符号相同,x-y小于等于零: (!(sgnx^sgny)&sgnd);

对于第二种情况,之所以不用x-y来判断,是因为x-y有可能导致运算溢出。

/* 
 * 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 sgnx = (x>>31)&0x1;
  int sgny = (y>>31)&0x1;
  int d = x + (~y+0x1);
  int sgnd = (d>>31)&0x1;
  return !(x^y) | (sgnx&!sgny) | (!(sgnx^sgny)&sgnd);
}

 Ilog2

这个问题的本质就是确定编码中最左的一位的位置。这个过程需要用到之前的bitCount函数。首先,我们将最左那一位之后的所有位全部设为1,然后只要数出总共的1的个数。

/*
 * ilog2 - return floor(log base 2 of x), where x > 0
 *   Example: ilog2(16) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 90
 *   Rating: 4
 */
int ilog2(int x) {
  /* Pass the most significant to low bits */
  int mask = 0;
  x |= x>>1;
  x |= x>>2;
  x |= x>>4;
  x |= x>>8;
  x |= x>>16;
  /* Generate 0x55555555 */
  mask = 0x55;
  mask += mask<<8;
  mask += mask<<16;
  x = ((x>>1)&mask) + (x&mask);
  /* Generate 0x33333333 */
  mask = 0x33;
  mask += mask<<8;
  mask += mask<<16;
  x = ((x>>2)&mask) + (x&mask);
  /* Generate 0x0F0F0F0F */
  mask = 0x0F;
  mask += mask<<8;
  mask += mask<<16;
  x = ((x>>4)&mask) + (x&mask);
  /* Generate 0xFFFFFFFF */
  mask = 0xFF;
  mask += mask<<16;
  x = ((x>>8)&mask) + (x&mask);
  x += x>>16;
  return (x&0xFF)+(~0x1+0x1);
}

浮点操作

Float_neg

这里用了很有技巧性地判断方法,将uf左移1位后与0xFF000000比较大小。如果uf«1 > 0xFF000000,uf是NaN,那么返回NaN。否则数不是NaN,只要对符号位取反就好(加上0x80000000)。

/* 
 * float_neg - Return bit-level equivalent of expression -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 representations of
 *   single-precision floating point values.
 *   When argument is NaN, return argument.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 10
 *   Rating: 2
 */
unsigned float_neg(unsigned uf) {
	if (uf<<1 > 0xFF000000) 
		return uf;
	else
		return uf + 0x80000000;
}

Float_i2f

需要分类讨论:

  1. 0和tmin:我们的函数并不能处理这两种特殊情况,只能直接返回已知的编码;

  2. 其余情况:获得对数计算exponent,和除首位外的有效数字,得到fraction,这里很麻烦的是,如果数大于2^23,我们需要对它的fraction部分做约进,需要遵守round-to-even规则。

这是个很复杂的函数,但是最多只能使用30个运算符,只能使用一些特殊的技巧来减少运算符的使用了:

  1. 将条件判断中的逻辑运算符去掉,改用多个条件判断语句的嵌套;

  2. 如果可以。将运算改为赋值,取符号就是个很好的例子,原本可以使用x&0x80000000,但是后来我把取符号和去绝对值放在一起,直接赋值,减少了一个运算符的使用。

/* 
 * float_i2f - Return bit-level equivalent of expression (float) x
 *   Result is returned as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point values.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned float_i2f(int x) {
	// Variable declares
	int f, mask, abs_var, rounded_abs_var, temp, fraction, log2_var, dismissed_bits, last_bit, round_up;

	// If x == 0
	if (!x)
		return 0;
	// If x == tmin
	if (x == 0x80000000)
		return 0xcf000000;

	// If x != 0 && x != tmin
	// Get abs
	if (x > 0) {
		f = 0x3F800000;
		abs_var = x;
	} else {
		f = 0xBF800000;
		abs_var = -x;
	}
	if (abs_var >= 0x7FFFFFC0)
		return 0xcf000000;
	// Get exponent
	mask = 0x40000000;
	log2_var = 30;
	while (!(abs_var & mask)) {
		log2_var--;
		mask >>= 1;
	}
	f += log2_var << 23;
	// Get fraction
	dismissed_bits = log2_var - 23;
	if (dismissed_bits > 0) { 
		// Round
		mask = ~(0xFFFFFFFF << dismissed_bits);
		temp = abs_var & mask;
		rounded_abs_var = abs_var >>= dismissed_bits;
		last_bit = 0x1<<(dismissed_bits-1);
		round_up = 0;
		if (temp > last_bit)
			round_up = 1;
		else if (temp == last_bit)
			if (abs_var & 0x1)
				round_up = 1;
		rounded_abs_var += round_up;
		if (rounded_abs_var / abs_var > 1)
			f += 0x800000;
	} else 
		rounded_abs_var = abs_var <<= -dismissed_bits;
	return f | (rounded_abs_var & 0x7FFFFF);
}

Float_twice

需要分类讨论这个问题:

  1. Infinity和NaN:直接返回原来的数

  2. Denormal:将fraction左移一位,如果结果超出denormal的表示范围,那就把exponnet设为15

  3. Normal:将exponent加1,如果exponent等于31,结果是无穷大,就把fraction清零

/* 
 * 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) {
  unsigned fraction = uf & 0x7FFFFF;
  unsigned exponet = uf & 0x7F800000;
  // Infinity or NaN
  if (exponet == 0x7F800000) 
  	return uf;
  // Denormal
  else if (!exponet) {
  	fraction <<= 1;
  	fraction &= 0x7FFFFF;
  	// Bordery case
  	if (fraction & 0x400000) 
  	  exponet = 0x800000;
  }
  // Normal
  else {
  	// If result is infnity
  	if (exponet + 0x800000 == 0x7F800000)
  		fraction = 0;
  	exponet += 0x800000;
  }
  // Combine
  uf &= 0x80000000;
  uf |= exponet;
  uf |= fraction;
  return uf;
}