CSAPP-实验1 Datalab 学习记录

本文主要作为【不周山之读厚 CSAPP】I Data Lab的扩充，小土刀于2016年4月写成，当时总共需要13个函数，而现在需要完成62个函数。
没有阅读过【不周山之读厚 CSAPP】I Data Lab的同学，需要先去阅读。

题目的要求都是一样的，有用的提示小土刀也提示的差不多了。
现在多了两个帮助函数ishow 和 ifshow,另外btest功能增强了,更多功能请阅读datalab-handout目录下的README

• ishow 展示输入的整型数据的详细信息
  使用示例：

    unix> ./ishow 0x27
    Hex = 0x00000027,   Signed = 39,    Unsigned = 39

    unix> ./ishow 27
    Hex = 0x0000001b,   Signed = 27,    Unsigned = 27

• fshow 展示输入的浮点型数据的详细信息
  使用示例:

  unix> ./fshow 0x15213243
    Floating point value 3.255334057e-26
    Bit Representation 0x15213243, sign = 0, exponent = 0x2a, fraction = 0x213243
    Normalized.  +1.2593463659 X 2^(-85)

    linux> ./fshow 15213243
    Floating point value 2.131829405e-38
    Bit Representation 0x00e822bb, sign = 0, exponent = 0x01, fraction = 0x6822bb
    Normalized.  +1.8135598898 X 2^(-126)

废话不多说，我们进入正题

进入正题

1. absVal

/*
 * absVal - absolute value of x
 *   Example: absVal(-1) = 1.
 *   You may assume -TMax <= x <= TMax
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 10
 *   Rating: 4
 */
int absVal(int x) {
  int negate = !!(x & (1 << 31));
  return (x^(~0 + !negate))+negate;
}

解题思路：

当 x < 0 时 absVal(x) = -x
当 x >= 0 时 absVal(x) = x
由小土刀对negate分析，可知
-x = ~x + 1
~x = x ^ (~0)
x = x ^ 0

2.addOK

/*
 * addOK - Determine if can compute x+y without overflow
 *   Example: addOK(0x80000000,0x80000000) = 0,
 *            addOK(0x80000000,0x70000000) = 1,
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */
int addOK(int x, int y) {
  int res = x + y;
  int flagx = !(x & (1 << 31));
  int flagy = !(y & (1 << 31));
  int flagr = !(res & (1 << 31));
  return !((flagx & flagy & !flagr) | (!flagx & !flagy & flagr));
}

解题思路：

当 x > 0 且 y > 0 但 x+y < 0时，发生正溢出
当x<0 且 y < 0 但 x+y >= 0 时，发生负溢出

3.allEvenBits

/*
 * allEvenBits - return 1 if all even-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allEvenBits(0xFFFFFFFE) = 0, allEvenBits(0x55555555) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allEvenBits(int x) {
  int a = 0x55;
  int b = (a << 8) + a; //0x55 55
  int c = (b << 8) + a; //0x55 55 55
  int d = (c << 8) + a; //0x55 55 55 55
  return !((x & d)^d);
}

4.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;
  int b = (a << 8) + a; //0xAA AA
  int c = (b << 8) + a; //0xAA AA AA
  int d = (c << 8) + a; //0xAA AA AA AA
  return !((x & d)^d);
}

5.anyEvenBit

/*
 * anyEvenBit - return 1 if any even-numbered bit in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples anyEvenBit(0xA) = 0, anyEvenBit(0xE) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int anyEvenBit(int x) {
  int a = 0x55;
  int b = (a << 8) + a; //0x55 55
  int c = (b << 8) + a; //0x55 55 55
  int d = (c << 8) + a; //0x55 55 55 55
  return !!(x & d);
}

6.anyOddBit

/*
 * anyOddBit - return 1 if any odd-numbered bit in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples anyOddBit(0x5) = 0, anyOddBit(0x7) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int anyOddBit(int x) {
  int a = 0xAA;
  int b = (a << 8) + a; //0xAA AA
  int c = (b << 8) + a; //0xAA AA AA
  int d = (c << 8) + a; //0xAA AA AA AA
  return !!(x & d);
}

7.bang

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

解题思路：

依次折半的将所有位数合并。
step1，将高16位与低16位进行或运算，将高16位中的1藏在低16位中。
step2，将低16位中的高8位与低8位进行或运算，将低16位中的高8位中的1藏于低8位中。
step3，将低8位中的高4位与低4位进行或运算，将低8位中的高4位中的1藏于低4位中。
step4，将低4位中的高2位与低2位进行或运算，将低4位中的高2位中的1藏于低2位中。
step5，将低2位中的高位与低位进行或运算，将低2位中的高位中的1藏于低位中，并与1进行与运算。
如此，step5中e的结果必为0（当且仅当x为0时）或1，将其与1异或便是结果。

改进
参考网上大笨象同学的解法

在补码表示里只有0和它的相反数同时非负，即0 与（~0 + 1）的符号为均为 0；其他任何数|上自己的相反数，符号位都为1；

int bang(int x) {
  int a = ~x + 1;
  int b = ((a | x) >> 31) + 1 ;
  return b;
}

8.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) {
  int a = ~x | ~y;
  return ~a;
}

9.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) {
  //数据结构习题解析第三版 邓俊辉 第一章 12题(b) Page 9
  /*
   * Warning: 42 operators exceeds max of 40
   *
  int mask0 = (0x55) | (0x55 << 8) | (0x55 << 16) | (0x55 << 24);  //0x55555555
  int mask1 = (0x33) | (0x33 << 8) | (0x33 << 16) | (0x33 << 24);  //0x33333333
  int mask2 = (0x0F) | (0x0F << 8) | (0x0F << 16) | (0x0F << 24);  //0x0F0F0F0F
  int mask3 = (0xFF) |               (0xFF << 16);                 //0x00FF00FF
  int mask4 = (0xFF) | (0xFF << 8);                                //0x0000FFFF
  */

  int a = (0x55) | (0x55 << 8);
  int mask0 = a | (a << 16);
  int b = (0x33) | (0x33 << 8);
  int mask1 = b | (b << 16);
  int c = (0x0F) | (0x0F << 8);
  int mask2 = c | (c << 16);
  int mask3 = (0xFF) | (0xFF << 16);
  int mask4 = (0xFF) | (0xFF << 8);

  //unsigned int n = (unsigned int)x;
  int n = x;
  n = (n & mask0) + (n >> 0x01  & mask0);
  n = (n & mask1) + (n >> 0x02  & mask1);
  n = (n & mask2) + (n >> 0x04  & mask2);
  n = (n & mask3) + (n >> 0x08  & mask3);
  n = (n & mask4) + (n >> 0x10  & mask4);

  return n;
}

BitCount.png

10.

/*
 * bitMask - Generate a mask consisting of all 1's
 *   lowbit and highbit
 *   Examples: bitMask(5,3) = 0x38
 *   Assume 0 <= lowbit <= 31, and 0 <= highbit <= 31
 *   If lowbit > highbit, then mask should be all 0's
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int bitMask(int highbit, int lowbit) {
  int a = ~0;
  //notice: the result of x << 32 is x
  //        should exec x << 31 then x << 1
  int b = a << highbit;
  int x = (a << lowbit) & (~(b << 1));
  return x;
}

注意事项：
当对int x执行<<32时， 什么事情也没有发生，x并不是0，仍旧是自身。

11.bitMatch

/*
 * bitMatch - Create mask indicating which bits in x match those in y
 *            using only ~ and &
 *   Example: bitMatch(0x7, 0xE) = 0x6
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitMatch(int x, int y) {
  int match0 = ~x & ~y;
  int match1 = x & y;
  int res = ~(~match0 & ~match1);
  return res;
}

12.bitNor

/*
 * bitNor - ~(x|y) using only ~ and &
 *   Example: bitNor(0x6, 0x5) = 0xFFFFFFF8
 *   Legal ops: ~ &
 *   Max ops: 8
 *   Rating: 1
 */
int bitNor(int x, int y) {
  //int res = ~(~(~x & ~y));
  int res = ~x & ~y;
  return res;
}

13.bitOr

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

14.bitParity

/*
 * bitParity - returns 1 if x contains an odd number of 0's
 *   Examples: bitParity(5) = 0, bitParity(7) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 4
 */
int bitParity(int x) {
  int a = x ^ (x >> 16);
  int b = a ^ (a >> 8);
  int c = b ^ (b >> 4) ;
  int d = c ^ (c >> 2);
  int e = (d ^ (d >> 1)) & 0x01;
  return e;
}

解题思路类似第7题

15.bitReverse

/*
 * bitReverse - Reverse bits in a 32-bit word
 *   Examples: bitReverse(0x80000002) = 0x40000001
 *             bitReverse(0x89ABCDEF) = 0xF7D3D591
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 45
 *   Rating: 4
 */
int bitReverse(int x) {
  /*
   *  Warning: 50 operators exceeds max of 45
   *
  int mask0 = 0xFF | 0xFF << 8;                             //0x0000FFFF
  int mask1 = 0xFF              | 0xFF << 16;               //0x00FF00FF
  int mask2 = 0x0F | 0x0F << 8  | 0x0F << 16 | 0x0F << 24;  //0x0F0F0F0F
  int mask3 = 0x33 | 0x33 << 8  | 0x33 << 16 | 0x33 << 24;  //0x33333333
  int mask4 = 0x55 | 0x55 << 8  | 0x55 << 16 | 0x55 << 24;  //0x55555555
  */

  int mask0 = (0xFF) | (0xFF << 8);
  int mask1 = (0xFF) | (0xFF << 16);
  int a = (0x0F) | (0x0F << 8);
  int mask2 = a | (a << 16);
  int b = (0x33) | (0x33 << 8);
  int mask3 = b | (b << 16);
  int c = (0x55) | (0x55 << 8);
  int mask4 = c | (c << 16);

  int n = (x >> 16 & mask0) | (x << 16);
  n = (n >> 8  & mask1) | (n << 8 & ~mask1);
  n = (n >> 4  & mask2) | (n << 4 & ~mask2);
  n = (n >> 2  & mask3) | (n << 2 & ~mask3);
  n = (n >> 1  & mask4) | (n << 1 & ~mask4);
  return n;
}

解题思路：
可借鉴第7题、第9题、 第14题

折半的交换左右两部分
例如 12345678
第一次交换后： 5678 | 1234
第二次交换后： 78 | 56 || 34 | 12
第三次交换后： 8|7|| 6|5 ||| 4|3 || 2|1

16.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 a = x & ~y;
  int b = ~x & y;
  int c = ~(~a & ~b);
  return c;
}

17.byteSwap

/* 
 * byteSwap - swaps the nth byte and the mth byte
 *  Examples: byteSwap(0x12345678, 1, 3) = 0x56341278
 *            byteSwap(0xDEADBEEF, 0, 2) = 0xDEEFBEAD
 *  You may assume that 0 <= n <= 3, 0 <= m <= 3
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 25
 *  Rating: 2
 */
int byteSwap(int x, int n, int m) {
  int n8 = n << 3;
  int m8 = m << 3;
  int a = ((x >> n8) & 0xFF) << m8;
  int b = ((x >> m8) & 0xFF) << n8;
  int c = (x & ~(0xFF << m8) & ~(0xFF << n8));
  return (a | b | c);
}

解题思路：

将需要交换的2个byte分别扣（与运算）出来，再错位放入（或运算)

18.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 flag = !!x;
  int a = y ^ z;
  int b = a ^ ( y & (~0 + flag)) ^ ( z & (~0 + !flag));
  return b;
}

19.copyLSB

/* 
 * copyLSB - set all bits of result to least significant bit of x
 *   Example: copyLSB(5) = 0xFFFFFFFF, copyLSB(6) = 0x00000000
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int copyLSB(int x) {
  int n = x & 0x01;
  n = ~n + 1;
  return n;
}

20.distinctNegation

/*
 * distinctNegation - returns 1 if x != -x.
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 5
 *   Rating: 2
 */
int distinctNegation(int x) {
  return !!(x+x);
}

解题思路：

只有 0 与 Tmin 的相反数等于自身,另外有如下特性
0 + 0 = 0
Tmin + Tmin = 0

21.dividePower2

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

解题思路：

明白整数乘法总是舍入到零（CSAPP 中文第二版 P64)
因此有如下除法公式：
x/pwr2k = (x < 0 ? ( x + (1 << k) -1) : x) >> k; （CSAPP 中文第二版 P66)

22.evenBits

/* 
 * evenBits - return word with all even-numbered bits set to 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 1
 */
int evenBits(void) {
  int mask = 0x55 | 0x55 << 8 | 0x55 << 16 | 0x55 << 24;
  return mask;
}

23.ezThreeFourths

/*
 * ezThreeFourths - multiplies by 3/4 rounding toward 0,
 *   Should exactly duplicate effect of C expression (x*3/4),
 *   including overflow behavior.
 *   Examples: ezThreeFourths(11) = 8
 *             ezThreeFourths(-9) = -6
 *             ezThreeFourths(1073741824) = -268435456 (overflow)
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 3
 */
int ezThreeFourths(int x) {
  int a = (x << 1) + x;  //a = x * 3;
  int flag = !!(a & (0x1 << 31));
  int b = a + (0x3 & (flag | flag << 1));
  return b >> 2;
}

解题思路：

先计算a = x * 3,再对a/4 向零取整，当x*3 溢出时，也符号期望值。
如果先计算x/4 会损失精度

24.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) {
  int positive = !(x & (1 << 31));
  int mask = ~0 << (n + ~0);
  int a = !((x^(~0 + positive)) & mask);
  return a;
}

解题思路：

这道题目对我很难。我思考了并修改了很久，才得出正确的结果
当有1个bit时， 能表示的数 只有 {-1 ， 0}；
当有2个bit时，能表示的数有 {-2， -1， 0， 1}；
当有3个bit时，能表示的数有{-4，-3，-2，-1，0，1，2，3}；
刚开始我的思路是：既然Tmin = -Tmax - 1;那求出Tmin，然后加上x的绝对值小于0，就说明可以放下x。但是 ，当x = Tmin32时，无法求得x的绝对值。
最后通过观察，发现能表示的数从n-1位左边所有的数必为全1或全0（正负两种情况）。

优化
参考网上大笨象同学的解法

想法：有两个规律假设n=4只有当0x11111...[1xxx]或0x00000...[0xxx]我们才能用n个二进制位来表式x，想法出来了我就将x往右移n-1位~((~n)+1)，判断剩下的数字是不是全1或者全0不就好了啊？是的就是这样辣。

int fitsBits(int x, int n)
{
   int tmp = ~((~n)+1);
   int tmpx = x >> tmp;
   int ans =   ( !tmpx | !(tmpx+1)  );
   return ans;
}

25.fitsShort

/* 
 * fitsShort - return 1 if x can be represented as a 
 *   16-bit, two's complement integer.
 *   Examples: fitsShort(33000) = 0, fitsShort(-32768) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 1
 */
int fitsShort(int x) {
  int a = x >> 15;
  int res = !a | !(a + 1);
  return res;
}

解题思路：

我采用的是和24题一样的解法。将16替换为n。使用了10个操作符，超出了限制。
以上为大笨象同学的解法。

浮点数

浮点数采用和整数完全不同的表示法。
可以参考https://wdxtub.com/2016/04/16/thin-csapp-1/

image
浮点数的实际表示.png

26.floatAbsVal

/* 
 * floatAbsVal - Return bit-level equivalent of absolute value of 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 floatAbsVal(unsigned uf) {
  unsigned a = uf & ~(1 << 31);
  unsigned B = (0x7F << 24) | (0x80 << 16);
  if (((a & B) == B) && (a ^ B))
      return uf;
  return a;
}

解题思路：

主要难点在于理解NaN即可

（未完待续...）