CSAPP Data Lab V.2016.05.04。 要求如下

/*
 * Instructions to Students:
 *
 * STEP 1: Read the following instructions carefully.
 */

You will provide your solution to the Data Lab by
editing the collection of functions in this source file.

INTEGER CODING RULES:

  Replace the "return" statement in each function with one
  or more lines of C code that implements the function. Your code 
  must conform to the following style:

  int Funct(arg1, arg2, ...) {
      /* brief description of how your implementation works */
      int var1 = Expr1;
      ...
      int varM = ExprM;

      varJ = ExprJ;
      ...
      varN = ExprN;
      return ExprR;
  }

  Each "Expr" is an expression using ONLY the following:
  1. Integer constants 0 through 255 (0xFF), inclusive. You are
      not allowed to use big constants such as 0xffffffff.
  2. Function arguments and local variables (no global variables).
  3. Unary integer operations ! ~
  4. Binary integer operations & ^ | + << >>

  Some of the problems restrict the set of allowed operators even further.
  Each "Expr" may consist of multiple operators. You are not restricted to
  one operator per line.

  You are expressly forbidden to:
  1. Use any control constructs such as if, do, while, for, switch, etc.
  2. Define or use any macros.
  3. Define any additional functions in this file.
  4. Call any functions.
  5. Use any other operations, such as &&, ||, -, or ?:
  6. Use any form of casting.
  7. Use any data type other than int.  This implies that you
     cannot use arrays, structs, or unions.


  You may assume that your machine:
  1. Uses 2s complement, 32-bit representations of integers.
  2. Performs right shifts arithmetically.
  3. Has unpredictable behavior when shifting an integer by more
     than the word size.

EXAMPLES OF ACCEPTABLE CODING STYLE:
  /*
   * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31
   */
  int pow2plus1(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     return (1 << x) + 1;
  }

  /*
   * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31
   */
  int pow2plus4(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     int result = (1 << x);
     result += 4;
     return result;
  }

FLOATING POINT CODING RULES

For the problems that require you to implent floating-point operations,
the coding rules are less strict.  You are allowed to use looping and
conditional control.  You are allowed to use both ints and unsigneds.
You can use arbitrary integer and unsigned constants.

You are expressly forbidden to:
  1. Define or use any macros.
  2. Define any additional functions in this file.
  3. Call any functions.
  4. Use any form of casting.
  5. Use any data type other than int or unsigned.  This means that you
     cannot use arrays, structs, or unions.
  6. Use any floating point data types, operations, or constants.

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);
}

两次取反即可。~(x&y) = (~x) | (~y)

getByte

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

把要取的字节移到最低位,然后取出即可。注意是字节,所以要*8,即先n << 3

logicalShift

/* 
 * 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) {
  int mask;

  mask = ~(((1 << 31) >> n) << 1); // mask 0{n}1{32-n}

  x = (x >> n) & mask;

  return x;
}

由于xsigned int,因此右移时采用算数右移,故右移后要剔除在原最高位之前添加的符号位。用掩码0{n}1{32-n}即可。

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) {
  int tmp, mask1, mask2, mask3, mask4, mask5, v;

  tmp = 0x55 | (0x55 << 8);
  mask1 = tmp | (tmp << 16); // 0x55555555

  tmp = 0x33 | (0x33 << 8);
  mask2 = tmp | (tmp << 16); // 0x33333333

  tmp = 0x0F | (0x0F << 8);
  mask3 = tmp | (tmp << 16); // 0x0F0F0F0F

  mask4 = 0xFF | (0xFF << 16); // 0x00FF00FF

  tmp = 0xFF | (0xFF << 8);
  mask5 = tmp | (0 << 16); // 0x0000FFFF

  v = (x & mask1) + ((x >> 1) & mask1);
  v = (v & mask2) + ((v >> 2) & mask2);
  v = (v & mask3) + ((v >> 4) & mask3);
  v = (v & mask4) + ((v >> 8) & mask4);
  v = (v & mask5) + ((v >> 16) & mask5);

  return v;
}

参考[stackoverflow]。采用分治法,计算1的个数就是把每一位都当成独立的数,并求和。

  1. 0x55 -> 0101 0101,右移1位:每1位视为一个数,相邻求和,结果用2位保存。
  2. 0x33 -> 0011 0011,右移2位:每2位视为一个数,相邻求和,结果用4位保存。
  3. 0x0F -> 0000 1111,右移4位:每4位视为一个数,相邻求和,结果用8位保存。
  4. 0x00FF -> 0000 0000 1111 1111,右移8位:每8位视为一个数,相邻求和,结果用16位保存。
  5. 0x0000FFFF -> 0000 0000 0000 0000 1111 1111 1111 1111,右移16位:每16位视为一个数,相邻求和,结果用32位保存。即为最终结果。

为什么要右移呢?以每4位视为一数为例,1001被视为两个数10,01,若要将二者求和,则需要分别将二者从原数中取出,然后相加。掩码0011可以直接取出01,若要取出10,则需要先将10右移到低位。

So if I have number 395 in binary 0000000110001011 (0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1)
After the first step I have:      0000000101000110 (0+0 0+0 0+0 0+1 1+0 0+0 1+0 1+1) = 00 00 00 01 01 00 01 10
In the second step I have:        0000000100010011 ( 00+00   00+01   01+00   01+10 ) = 0000 0001 0001 0011
In the fourth step I have:        0000000100000100 (   0000+0001       0001+0011   ) = 00000001 00000100
In the last step I have:          0000000000000101 (       00000001+00000100       )

bang

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

!x = 1 if x == 0 else 1。因此要把0与其它数区分开来,考虑到-0 = +0 = 0-x只有在x=0时符号位才不会改变。故只需利用x | (-x) = x | (~x + 1)的符号位即可。

tmin

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

最小值为0x8000 0000

fitsBits

/* 
 * fitsBits - return 1 if x can be represented as an 
 *  n-bit, two's complement integer.
 *   1 <= n <= 32
 *   Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
int fitsBits(int x, int n) {
  // (x << (32 - n)) >> (32 - n) equals x

  int c;

  c = 33 + ~n;

  return !(((x << c) >> c) ^ x); 
}

(x << (32 - n)) >> (32 - n) == x 则能够表示

divpwr2

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

  bias = (1 << n) + ~0;
  return (x + ((x >> 31) & bias)) >> n;
}

参见[CSAPP 3rd edition 2.3.7]。无论x正负,结果都是舍入到0。因此正数向下舍入,负数向上舍入。直接右移n位会导致不论正负数都是向下舍入。

证明如下:

首先是为正数时,与无符号数相同。

为负数时,直接右移会同样向下舍入(前提是补码与无符号数的乘法表示形式相同)

因此要加一个偏差值,然后再右移,使其向上舍入

negate

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

参考[关于2的补码]。取反加1即可

isPositive

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

  return !(s | (!x));
}

第一步,取符号,区分负数。第二步,取非,区分0。

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) {
  // x <= y => ! (x > y)
  // x > y => x - y > 0 => x + (~y + 1) > 0

  // return !(((y + (~x + 1)) >> 31) & 1); 
  // breaks down when overflow eg. -x = x when x is 0x80000000

  int sign_x, sign_y, r;

  sign_x = (x >> 31) & 1;
  sign_y = (y >> 31) & 1;

  /* 1) sign_y = sign_x: y >= x if the index of first '1'
   *    in y is larger than in x (reduce to sign(x + ~y) is 1).
   * 2) sign_y != sign_x: y >= x if sign_y = 0 and sign_x = 1
   * */

  r = (!(sign_x ^ sign_y)) & (((x + ~y) >> 31) & 1);
  return r | ((!sign_y) & sign_x);
}

本来想利用 x > y => x - y > 0 => x + (~y + 1) > 0这个性质,但发现计算机并非纯数学,加法与可能会溢出。截断之后就不好玩了。故采取其它办法。

符号位不同则很好判断。符号位相同则从最高位起,比较第一个不相同的位,为1者较大。即若y > xx + ~y最高位为1,比如x=0001y=0010~y=1101,相加后前面相同的位变为全1,第一个不同的位变为0

ilog2

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

  int tmp, mask1, mask2, mask3, mask4, mask5, v;

  // most significant bit
  x = x | (x >> 1);
  x = x | (x >> 2);
  x = x | (x >> 4);
  x = x | (x >> 8);
  x = x | (x >> 16);  // eg. 0010 1011 => 0011 1111
  // MSB is x & (~(x >> 1))

  // bitCount  
  tmp = 0x55 | (0x55 << 8);
  mask1 = tmp | (tmp << 16); // 0x55555555

  tmp = 0x33 | (0x33 << 8);
  mask2 = tmp | (tmp << 16); // 0x33333333

  tmp = 0x0F | (0x0F << 8);
  mask3 = tmp | (tmp << 16); // 0x0F0F0F0F

  mask4 = 0xFF | (0xFF << 16); // 0x00FF00FF

  tmp = 0xFF | (0xFF << 8);
  mask5 = tmp | (0 << 16); // 0x0000FFFF

  v = (x & mask1) + ((x >> 1) & mask1);
  v = (v & mask2) + ((v >> 2) & mask2);
  v = (v & mask3) + ((v >> 4) & mask3);
  v = (v & mask4) + ((v >> 8) & mask4);
  v = (v & mask5) + ((v >> 16) & mask5);

  return v + ~0; // x - 1
}

也就是求最高有效位右边有多少位。首先把最高有效位后面的位全改成1,然后求1的个数。

怎么把所有有效位都置为1呢?把最高有效位不停地移到右边呗。先右移1位,得到11,然后右移2位,得到1111,依此类推。

float_neg

/* 
 * 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) >> 24) == 0xFF && ((uf << 9) != 0))
    return uf;
  return (1 << 31) ^ uf;
}

首先剔除NaN,然后符号位取反

float_i2f

/* 
 * 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) {
  int sign, exp, frac, bitc, tailb;

  if (x == 0) return 0;
  else if (x == 0x80000000) return 0xCF000000;

  sign = (x >> 31) & 1;
  if (sign) x = -x;

  // count bits to the right of MSB
  bitc = 1;
  while ((x >> bitc) != 0)
    bitc++;
  bitc--;

  exp = bitc + 127;

  x = x << (31 - bitc); // clear all those zeros to the left of MSB
  frac = (x >> 8) & 0x7FFFFF;

  // round to even (nearest) 
  if (bitc > 23) {
    tailb = x & 0xFF; // byte to round

    if ((tailb > 128) || ((tailb == 128) && (frac & 1))) {
      frac += 1;
      if (frac >> 23) {
        exp += 1;
        frac = 0;
      } 
    }
  }

  return (sign << 31) | (exp << 23) | frac;
}

单精度浮点小数点后面只能有23位有效数字,其后的要[round to even (nearest)]。超过0.5或不足的向最近的舍入,等于0.5的向偶数舍入。

float_twice

/* 
 * 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) {
  if ((uf & 0x7F800000) == 0) { // denormalized
    uf = ((uf & 0x007FFFFF) << 1) | (0x80000000 & uf);
  } else if ((uf & 0x7F800000) != 0x7F800000) { // normalized
    uf = uf + 0x00800000;
  } // NAN

  return uf;
}

指数位全为0的为非规格化数,指数为1 - Bias,底数为0.ff表示小数字段。因此加倍时直接左移。

规格化的数加倍时指数+1。

(完)

源码见[bits.c]