CSAPP Lab -- Data Lab

Integer

bitXor

//1
/* 
 * 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 ~(~(x & ~y) & ~(~x & y));
}

抛开现有的公式，直接分析异或操作的特性。仅有1和0的组合会得到1，其余都是0。

如果我数字$x$取反，那么会将原本为0的位置1，而原本为1的位置0。那么此时与$y$进行与操作，得到的结果中的所有的1都是满足“$y$中为1的位，以及$x$中原本为0的位”。

同理，再对$y$取反和$x$进行与操作。将两部分的结果相组合（或操作）即为异或的结果。

由于仅能用与非操作，因此对或进行转换即可。（暂不考虑化简）

tmin

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

二进制补码的最小值。参照CSAPP书上的理解是最合适的，符号位表示一个负权，其余的位均为正权。所以最小值必然为符号位为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 a = x ^ ~(x + 1);
    int b = !!(x + 1);
    return !a & b;
}

判断最大值，容易联想到对Tmax + 1得到Tmin。而Tmin取反即为Tmax。简单分析便可知，仅有+1后正数溢出到负数，或者负数转化为正数时，才能满足~(x + 1) == x。也就是说出了Tmax，还有-1也满足上述条件（-1 + 1 = 0; ~0 = -1）。为了排除这种情况，可以使用!运算，保证非零值均为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
 */
int allOddBits(int x) {
    int a = 0xAA;
    a = (a << 8) | a;
    a = (a << 16) | a;

    return !((x & a) ^ a);
}

其实，这题很容易联想到的方法，就是利用右移，判断x的每8位是否满足0xAA。但是很不幸，该方法的操作数较多，难以通过测试。

因此我们可以反过来考虑，利用左移主动构造一个0xAAAAAAAA，再去与x判断是否满足。

negate

/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
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
 */
int isAsciiDigit(int x) {
    int top = ~(1 << 31) + ~0x39 + 1;
    int bottom = ~0x30 + 1;

  return !(((x + bottom) >> 31) + ((x + top) >> 31));
}

可以考虑利用溢出来判断数值的大小。

分别判断大于0x39的数会发生上溢，小于0x30的数会得到负数。也即满足区间的数，前者判断会得到一个正数（不会发生上溢），后者判断会得到一个正数（负 + 正 = 正）。

也就是说只要最后的两个判断结果均为正数，那么x必然属于这个区间。

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

x分为0和非零两种情况，通过!运算符，可以使得x仅有0，1两种值。但是1这个数在仅有位运算的前提下，是很难不改变y和z的值的。而全0和全1两个值则会很好处理位运算，同时联想到全1的值即为-1。因此考虑将其减一（也即变量t）。

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 cs = (x ^ y) >> 31;
  return !!((cs & (x >> 31)) | (!cs & !((~x + 1 + y) >> 31)));
}

比较大小，最容易想到的方式就是将二者相减然后判断是否大于0。但是如果x与y异号，则可能出现负数减去正数溢出到正数的情况。因此需要分开考虑同号和异号两种情况。

对x和y进行异或：

• cs为0，则代表x与y同号。所以可以采取二者相减的方式判断大小。

  • y - x的符号位为0，则y >= x，因此$cs = 0, sign(y - x) = 0 \rightarrow x \leqslant y$
  • y - x的符号位为1，则y < x，因此$cs = 0, sign(y - x) = 1 \rightarrow x > y$

• cs为1，则代表x与y异号。此时仅判断x或y的符号即可

  • x的符号位为0，则x >= 0 > y，因此$cs = 1, sign(x) = 0 \rightarrow x > y$

  • x的符号位为1，则x < 0 <= y，因此$cs = 1, sign(x) = 1 \rightarrow x \leqslant y$

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，也即补码是不存在负0和正0的概念的。然后可以确定的是x与(~x + 1)必定异号，因为二者相加为0。

因此可以利用这个性质，仅x为0时，x | (~x + 1)的符号位为0；其余情况均为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
 */
int howManyBits(int x) {
    int sign = x >> 31;  // x为正则sign == 0x00000000；x为负则sign = 0xffffffff
    // 如果x为正则不变
    // 如果x为负，则取反，消除符号位
    x = (sign&~x)|(~sign&x);

    int b16 = !!(x >> 16) << 4;  //高16位如果有1，则说明需要16位以上
    x = x >> b16;  // 高16位有1，则位移16位；没有1则移0位；操作完成之后关注低16位
    int b8 = !!(x >> 8) << 3;
    x = x >> b8;
    int b4 = !!(x >> 4) << 2;
    x = x >> b4;
    int b2 = !!(x >> 2) << 1;
    x = x >> b2;
    int b1 = !!(x >> 1);
    x = x >> b1;
  return b16 + b8 + b4 + b2 + b1 + x + 1;  // + 1表示加上符号位，以及处理0的时候需要1位表示
}

采用二分法统计，因为对于正数，仅需考虑除符号位最高位1所处的位置，然后补上一个符号位即可。对于负数则是考虑除符号位最高位的1后的0，如1101和101表示同一个数，因此该情况仅需3位。所以在计算时，考虑均去除符号位后，最后再补上符号位

Float

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 == 255) return uf;
    if (exp == 0) return (uf << 1) | sign;  // 阶码是0，则小数部分乘2

    exp++;  // 阶码 + 1表示乘2
    if (exp == 255)  return 0x7f800000 | sign;  // 返回无穷大，表示溢出

  return (exp << 23) | (uf & 0x807fffff);
}

浮点数乘2，取出阶码，将阶码+1即可，如果上溢出则返回无穷大，下溢出则返回0，NaN则返回原数。

此外，还有一个需要注意的就是，从浮点数开始放开了常数范围、运算符以及条件语句if的限制。

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 exp = ((uf & 0x7f800000) >> 23) - 127;  // 减去bias
    int sign = uf >> 31;
    int frac = (uf & 0x007fffff) | 0x00800000;  // 补上丢去的高位1

    // 当exp == 31的时候，意味着移位改变了符号位，那么必然是存在溢出
    if (exp >= 31) return 0x80000000u;  
    if (exp < 0) return 0;

    if (exp > 23) frac = frac << (exp - 23);  // 画图可以看出来
    else frac = frac >> (23 - exp);

    if (sign == 0) return frac;  // frac符号位必然是0，原本符号也是0，那可以直接返回
    else return ~frac + 1;  // 如果该数原本为负，取反加一即可
}

将浮点数转为整数。考虑到阶码的偏置值，将其减去127。因为整数最多32位，因此阶码大于31，则为超出了表示范围，用0x80000000替代。同样如果阶码小于0，则说明数的取值在-1 < x < 1之间，整数也无法表示，用0替代。其余的情况再进一步处理。

「此处的操作不考虑符号位」

对于小数.1011：左移1位，相当于1011右移3位（0001）；左移2位相当于1011右移2位（0010）；左移5位相当于1011左移1位（10110）。综上可以看出，对于23位表示的frac，左移大于23位时，相当于frac直接左移exp - 23；小于23位时，相当于frac直接右移23 - exp。移动后的二进制码直接当做整数。

另外这里需要额外考虑一个异常情况，即移动后产生了溢出，即移动后的frac最高位为1且frac原本为正数，表明数字由正数溢出到了负数。

而对于负数，因为小数部分用的是原码表示，可以理解成所有的操作都是假定该数是一个正数进行计算的，但是由于实际上是一个负数，已经使用~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
 */
unsigned floatPower2(int x) {
    if (x < -126) return 0;
    if (x > 127) return 0x7f800000;

    return (x + 127) << 23;
}

2的x次幂，单独考虑超范围的情况。未超出表示范围时，将x置为阶码即可（记得加上偏置值）。