深入理解计算机系统实验：DataLab

bitXor

/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */

用~和&实现异或。与书中练习题2.13相似。

以下公式推导主要运用了狄摩根定律（DeMorgan）：
$$\begin{array}{rl}A\oplus B& =\bar{A}B+A\bar{B}\\ & =\overline{A+\bar{B}}+\overline{\bar{A}+B}\\ & =\overline{(A+\bar{B})(\bar{A}+B)}\\ & =\overline{AB}\cdot \overline{\bar{A}\bar{B}}\\ & =\sim (A\&B)\&\sim (\sim A\&\sim B)\end{array}$$

int bitXor(int x, int y) {
  return ~(x & y) & ~(~x & ~y);
}

tmin

/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */

返回最小二进制补码整数。Integer constants 0 through 255 (0xFF), inclusive.

int tmin(void) {
  return 1<<31;
}

isTmax

/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */

由于溢出规则Tmax + 1 = Tmin，并且有Tmax = ~Tmin。可利用这两个式子判断，~(x+1)^x的值若为0，则x为Tmax。

但是，对-1(补码11…11)来说，也满足上面的判别式，需要排除-1。

int isTmax(int x) {
  return !((~(x+1)^x)|(!(x+1));
}

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

判断x二进制奇数位是否全为1。

若x的二进制表示为1x1x...1x1x形式，则满足奇数位全为1。

以四位为例，1x1x & 1010 = 1010。拓展到32位，只要判断x & 0xAAAAAAAA == 0xAAAAAAAA。

问题是，如何构造出0xAAAAAAAA。

0xAA -> 0xAAAA: 0xAA | 0xAA<<8
0xAAAA -> 0xAAAAAAAA: 0xAAAA | 0xAAAA<<16

int allOddBits(int x) {
  int AA = 0xAA;
  int AAAA = AA | AA<<8;
  int A8 = AAAA | AAAA<<16;
  return !((x & A8) ^ A8);
}

negate

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

返回x的加法逆元

-x = ~x + 1
证明：
    x + ~x = -1  =>  x + (~x + 1) = 0  =>  -x = ~x + 1    

int negate(int x) {
  return ~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
 */

0x30 -> 0011 0000
0x31 -> 0011 0001
… …
0x38 -> 0011 1000
0x39 -> 0011 1001

判断高26位是否全为0：!(x>>6)
判断第4，5位: !((x>>4)^0b11) //0b表示二进制
判断低4位：(x&0xF)<10 -> (x&0xF)+(~10+1)<0 -> (((x&0xF)+(~0xA+1))>>31

int isAsciiDigit(int x) {
  return (!(x>>6)) & (!((x>>4)^0x3)) & (((x&0xF)+(~0xA+1))>>31);
}

conditional

/*  
 * conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */

输出取决于x的真假，考虑如何把x转换成可以影响输出的表达式。

00...00 & y = 0; 11...11 & y = y

我们期望当x当真时，exp1 & y = y; exp2 & z = 0，这样就有(exp1 & y ) | (exp2 & z) = y。x为假时同理。

int sign = !x;
当 x 为真，exp1: ~!sign + 1 = -1 -> 11..11
    	  exp2: sign -> 00..00
              
int sign = ((!!x)<<31)>>31;//注意：！！x != x
当 x 为真，sign -> 11..11   ~sign -> 00..00
当 x 为假，sign -> 00..00   ~sign -> 11..11

int conditional(int x, int y, int z) {
  int sign = ((!!x)<<31)>>31;
  return (sign & y) | (~sign & z);
  //return ((~!!x+1) & y) | ((~!x + 1) & z);
}

isLessOrEqual

/* 
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */

比大小，要是直接相减可能会溢出，影响判别

取符号位x>>31&0x1，x为有符号数，算术右移

考虑只有异号相减才会产生溢出，那异号时就直接比符号位

	x	y	return 
    -	+	  1     signx = 1   ->(signx ^ signy) & signx
    +   -	  0		signx = 0

int isLessOrEqual(int x, int y) {
  int signx = x >> 31 & 0x1;
  int signy = y >> 31 & 0x1;
  int con1 = !(signx ^ signy)  & !((y + (~x + 1))>>31);
  int con2 = (signx ^ signy) & signx;
  return con1 | con2;
}

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

当 x = 0, ~x + 1 = 0,(~x + 1) >> 31 = 00..00
当 x < 0, (~x + 1) >> 31 = 00..00
当 x > 0, (~x + 1) >> 31 = 11..11

区分0和负数:
   0: (x | (~x + 1)) >> 31 = 00..00
   负: (x | (~x + 1)) >> 31 = 11..11

int logicalNeg(int x) {
  return ((x | (~x + 1)) >> 31) + 1;
}

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

补码：1111 -> -1
     111  -> -1
     11   -> -1
     1    -> -1
相似地，补码：111101、11101、1101、101  -> -3
    
当 x > 0, howManyBits(x) = 找到最高的一位的1 + 一个符号位
当 x = 0, howManyBits(x) = 1
当 x < 0：howManyBits(x) = 找到最高的一位的0 + 一个符号位
    无论最高的一位0前面有几位1，都等价于只有一位1。以 11110111 为例，-> 10111，最少需要5位

int sign = x >> 31;
x = (~sign & x) | (sign & ~x); //x>0,x=x；x<0,x=~x  
把负数的补码表示中0都变为了1，接下来无论正负数都变成了寻找最高的一位1

0000 0100 0000 0000 | 0000 0000 0000 0000
若最高的一位1在高16位中，那低16位有意义但我们不关心具体，我们只关心最高一位1在高16位的什么位置。
bit_16 = (!(!!(x>>16) ^ 0x1)) << 4; //16
x >>= bit_16;

0000 0100 | 0000 0000
bit_8 = (!(!!(x>>8) ^ 0x1)) << 3; //8
x >>= bit_8;

0000 | 0100
bit_4 = (!(!!(x>>4) ^ 0x1)) << 2; //0
x >>= bit_4;

0000 01 | 00
bit_2 = (!(!!(x>>2) ^ 0x1)) << 1; //2
x >>= bit_2;

0 | 1
bit_1 = (!(!!(x>>1) ^ 0x1)); //0
x >>= bit_1;

bit_0 = x; //1

int res = bit_16 + bit_8 + bit_4 + bit_2 + bit_1 + bit_0 + 1; //28

int howManyBits(int x) {
  int isZero = !x;
  int mask = ((!!x)<<31)>>31;
  int sign = x >> 31;
  x = (~sign & x) | (sign & ~x);

  int bit_16,bit_8, bit_4, bit_2, bit_1, bit_0;
  bit_16 = (!(!!(x>>16) ^ 0x1)) << 4;
  x >>= bit_16;
  bit_8 = (!(!!(x>>8) ^ 0x1)) << 3;
  x >>= bit_8;
  bit_4 = (!(!!(x>>4) ^ 0x1)) << 2;
  x >>= bit_4;
  bit_2 = (!(!!(x>>2) ^ 0x1)) << 1;
  x >>= bit_2;
  bit_1 = (!(!!(x>>1) ^ 0x1));
  x >>= bit_1;
  bit_0 = x;
  int res = bit_16 + bit_8 + bit_4 + bit_2 + bit_1 + bit_0 + 1;

  return isZero | (mask & res);
}

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

取出s、exp和frac，根据三者的取值分类讨论。

特殊值：exp == 0xff，返回 uf 即可

非规格化：exp == 0x00，直接frac <<= 1即可。

​ 关于溢出：会溢出到阶码，非规格化数到规格化数是连续的。frac的MSB是1的时候，frac <<1 之后，正好导致Exp的LSB是1

规格化：E = exp - Bias，阶码加一等价于exp++

unsigned floatScale2(unsigned uf) {
  unsigned s = (uf >> 31) & 0x1;
  unsigned exp = (uf >> 23) & 0xff;
  unsigned frac = uf & 0x007fffff;

  //NaN and infinity
  if (exp == 0xff) {
    return uf;
  }

  //denormalize
  if (exp == 0) {
    frac <<= 1;
    return (s << 31) | frac;
  }

  //normalize
  exp++; //E = exp - Bias
  return (s<<31) | (exp << 23) | frac;
}

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

同样取出s、exp和frac，分类讨论。

特殊值（NaN and infinity）：exp == 0xff，返回 0x80000000u

非规格化：exp == 0，E = exp - 127 = -126导致V太小，接近0。返回0即可

规格化：计算E = exp - Bias 和 V 。注意不要把E定义成了unsigned类型，E可以取负

• E > 31：溢出，返回0x80000000u
• E < 0： 1.xxx / 2 => 0
• 23 <=E <= 31：frac的23位可以完全保留
• 0 <=E < 23：frac需要舍弃一些位数

int floatFloat2Int(unsigned uf) {
  unsigned s = (uf >> 31) & 0x1;
  unsigned exp = (uf >> 23) & 0xff;
  unsigned frac = uf & 0x007fffff;

  //NaN and infinity
  if (exp == 0xff) {
    return 1<<31;
  }

  //denormalize
  if (exp == 0) {
    //E = 1 - Bias = -126
    return 0;
  }
  
  //normalize
  int E = exp - 127;
  frac = frac | (1<<23); //1.frac
  if (E > 31) {
    return 1<<31;
  }else if (E < 0) {
    return 0;
  }
  if (E >= 23) {
    frac <<= (E - 23);
  } else {
    frac >>= (23 - E);
  }
  if (s==0)
    return frac;
  return ~frac + 1;
}

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

$$\begin{gathered} V=(-1{)}^S\times M\times 2^E \\ 本题中：V=2^x \end{gathered}$$

denormalize:  
	Min : 0000 0000 0000 0000 0000 0000 0000 0001
 	   E = 1 - Bias = -126   M = 2^(-23)   -149
   else : 0000 0000 0000 1000 0000 0000 0000 000
       E = -126  M = 2^(x - E) = 2^(x + 126)  shift = 23+(x+126)
        
normalize:
	Min : 0000 0000 1000 0000 0000 0000 0000 0000
       E = exp - Bias = -126  M = 1.0   -126
        : 0111 1111 0000 0000 0000 0000 0000 0000
       E = exp - Bias = 127   M = 1.0    127 
   else : 0000 0000 1000 0000 0000 0000 0000 0000
       E = exp - Bias  M = 1.0    x = E   exp = x + 127  shift = 23 

unsigned floatPower2(int x) {
  if (x < -149) { // too small
    return 0;
  }else if (x < -126) { // denormalize
    //E = 1 - Bias = -126;  M = 2^(x - E) = 2^(x + 126) 
    int shift = 23 + (x + 126); 
    return 1<<shift;
  }else if (x <=127 ) { // normalize
    //E = exp - Bias;  M = 1.0
    int exp = x + 127;
    return exp<<23;
  }else { // too large,NaN and INF
    return 0xff<<23;
  }
}

参考资料：

1. https://zhuanlan.zhihu.com/p/339047608
2. https://www.bilibili.com/video/BV183411k7VM