【施工完成】CSAPP data lab

 1/* 
 2 * bitXor - x^y using only ~ and & 
 3 *   Example: bitXor(4, 5) = 1
 4 *   Legal ops: ~ &
 5 *   Max ops: 14
 6 *   Rating: 1
 7 */
 8/* 0 0 -> 0
 9   0 1 -> 1
10   1 0 - > 1
11   1 1 - > 0
12*/
13// ~(~a & ~b)&~(a&b)
14int bitXor(int x, int y) {
15  int ans = ~(~x & ~y)&(~(x&y));
16  // printf("%d\n",ans);
17  return ans;
18}
19/* 
20 * tmin - return minimum two's complement integer 
21 *   Legal ops: ! ~ & ^ | + << >>
22 *   Max ops: 4
23 *   Rating: 1
24 */
25/*
26  0X10000000
27*/
28int tmin(void) {

 1}
 2//2
 3/* 
 4 * isTmax - returns 1 if x is the maximum, two's complement number,
 5 *     and 0 otherwise 
 6 *   Legal ops: ! ~ & ^ | +
 7 *   Max ops: 10
 8 *   Rating: 1
 9 *   0x7FFFFFFF
10 */
11int isTmax(int x) {
12  /*
13  大体思路首先是根据，如果x是最大值0x7FFFFFFF,那么~x和x+1(自然溢出)应该相等。
14  不能用等号，但是我们可以用异或。x==y 等价于  !(x^y). 因此有了后半段!(x+1)^(~x)
15  但是满足这个条件的还有-1,也就是0xFFFFFFFF,因此我们需要排除掉-1.
16  还是用异或的性质，这回是0异或者任何数都等于其本身。
17  因此如果x为-1，那么前后两部分都为1，结果为0.
18  如果x为TMAX,那么前面为0，后面为1，结果为1.
19  如果x为其他任何数，前后结果都应为0. 结果为0。
20  */
21  return (!(x+1))^!((x+1)^(~x));                                                                                                                                   
22}
23/* 
24 * allOddBits - return 1 if all odd-numbered bits in word set to 1
25 *   where bits are numbered from 0 (least significant) to 31 (most significant)
26 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
27 *   Legal ops: ! ~ & ^ | + << >>
28 *   Max ops: 12
29 *   Rating: 2
30 */
31// 理解错误。误以为是要求当前长度x的所有奇数位上都是1.
32// 实际上要求和x的长度无关，而是要求[0,31]中，所有奇数位上都是1.
33int allOddBits(int x) {
34  int half_mask = (0xAA<<8) | 0xAA;
35  int mask = (half_mask<<16) + half_mask;
36  // printf("mask:X x:x x\n",mask,x,x&mask);
37  return  !((x&mask)^mask);  

 1}
 2/* 
 3 * negate - return -x 
 4 *   Example: negate(1) = -1.
 5 *   Legal ops: ! ~ & ^ | + << >>
 6 *   Max ops: 5
 7 *   Rating: 2
 8 */
 9int negate(int x) {
10  return ~x + 1;
11}
12//3
13/* 
14 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
15 *   Example: isAsciiDigit(0x35) = 1.
16 *            isAsciiDigit(0x3a) = 0.
17 *            isAsciiDigit(0x05) = 0.
18 *   Legal ops: ! ~ & ^ | + << >>
19 *   Max ops: 15
20 *   Rating: 3
21 */
22/* 把0-9的二进制写出来，发现0-7占满了3bit的二进制的8种组合。
23   因此考虑只判断8和9两种4bit的情况
24   构造mask,不在意的bit的位置放0，在意的bit位置放1.
25*/
26int isAsciiDigit(int x) {
27  int mask = 0x0E;
28  int ones = x&mask;
29  int ones_3 = ones >> 3;
30  int tens = x>>4;
31  // printf("x: x tens: x ones:x\n",x,tens,ones);
32  int ones_ok = (!(ones^0x8)) | (!ones_3);
33  int tens_ok = !(tens^0x3);
34  return ones_ok & tens_ok;

 1}
 2/* 
 3 * conditional - same as x ? y : z 
 4 *   Example: conditional(2,4,5) = 4
 5 *   Legal ops: ! ~ & ^ | + << >>
 6 *   Max ops: 16
 7 *   Rating: 3
 8 */
 9/*
10  关键思路是0xFFFFFFFF和0x00000000之间差了1.
11  而这两个数一个是全部位置都取的mask,一个是全部位置都不取的mask.
12*/
13int conditional(int x, int y, int z) {
14  return   z^(!x + ~0 )&(y^z);

 1}
 2/* 
 3 * isLessOrEqual - if x <= y  then return 1, else return 0 
 4 *   Example: isLessOrEqual(4,5) = 1.
 5 *   Legal ops: ! ~ & ^ | + << >>
 6 *   Max ops: 24
 7 *   Rating: 3
 8 */
 9/*
10  大体思路是，符号位相同和符号位不同分别考虑
11  符号位相同:  考虑差的符号位。
12  符号位不同: 当x<0,y>=0时结果为1.
13*/
14int isLessOrEqual(int x, int y) {
15  int minus = y + (~x+1);
16  int s_x = (x>>31)&1;
17  int s_y = (y>>31)&1;
18  int s_minus = (minus>>31) & 1;
19  return (s_x&(!s_y))| (!(s_x^s_y)&!s_minus); 
20}
21//4
22/* 
23 * logicalNeg - implement the ! operator, using all of 
24 *              the legal operators except !
25 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
26 *   Legal ops: ~ & ^ | + << >>
27 *   Max ops: 12
28 *   Rating: 4 
29 */
30/* 
31  0 == ~0+1
32  -2147483648 = ~-2147483648+1
33  满足 x == ~x+1
34  重点是x和~x+1的符号位相同，如果都是0那么x=0,如果都是1那么x=-214783648`
35*/
36int logicalNeg(int x) {
37  int s1 = (x>>31)&1;
38  int s2 = ((~x+1)>>31)&1;
39  // printf("s1: %d s2:%d  %d  %d\n",s1,s2,s1|s2,~(s1|s2));
40  //  1 + negate(0) -> 1
41  //  1 + neagate(1) -> 0
42  return 1+(1+~(s1|s2));
43}
44/* howManyBits - return the minimum number of bits required to represent x in
45 *             two's complement
46 *  Examples: howManyBits(12) = 5
47 *            howManyBits(298) = 10
48 *            howManyBits(-5) = 4
49 *            howManyBits(0)  = 1
50 *            howManyBits(-1) = 1 ??? should be 2?
51 *            howManyBits(0x80000000) = 32
52 *  Legal ops: ! ~ & ^ | + << >>
53 *  Max ops: 90
54 *  Rating: 4
55 */
56/*
57  思路似乎可以转化成判断一个数（可正可负）的最高位的1的位置。
58  判断最高位1用二分的办法。
59  构造一个单调的函数，假设最高位位置为a,那么f((a,32))=0,f([0,a])=1.
60  被 howManyBits(-1)==1 困扰了好久，实际上就是0x1，只有一位，改位就是符号位的情况。 
61*/
62int howManyBits(int x) {
63  int n = 0 ;
64  x^=(x<<1);
65  n +=  (!!( x & ((~0) << (n + 16)) )) << 4;   // 看高16位是否为0，是的话区间为[0,16),否的话为[16,32)
66  // printf("n:%d\n",n);
67  // printf("%d\n",!!(x & ((~0) << (n + 16))));
68  n +=  (!!( x & ((~0) << (n + 8)) )) << 3;
69  // printf("n:%d\n",n);
70  n +=  (!!( x & ((~0) << (n + 4)) )) << 2;
71  // printf("n:%d\n",n);
72  n +=  (!!( x & ((~0) << (n + 2)) )) << 1;
73  // printf("n:%d\n",n);
74  n +=  (!!( x & ((~0) << (n + 1)) ));
75  // printf("n:%d\n",n);

1  // int s = (x>>31)&1;
2  // int ret = n+1+((1^s)&(!!x));
3  // // printf("x:%d ret:%d\n",x,ret);

 1//float
 2/* 
 3 * floatScale2 - Return bit-level equivalent of expression 2*f for
 4 *   floating point argument f.
 5 *   Both the argument and result are passed as unsigned int's, but
 6 *   they are to be interpreted as the bit-level representation of
 7 *   single-precision floating point values.
 8 *   When argument is NaN, return argument
 9 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
10 *   Max ops: 30
11 *   Rating: 4
12 */
13unsigned floatScale2(unsigned uf)
14{
15  int exp_ = (uf & 0x7f800000) >> 23;
16  int s_ = uf & 0x80000000;
17  if (exp_ == 0)
18    return (uf << 1) | s_;
19  if (exp_ == 255)
20    return uf;
21  ++exp_;
22  if (exp_ == 255)
23    return 0x7f800000 | s_;
24  return (uf & 0x807fffff) | (exp_ << 23);
25}
26/* 
27 * floatFloat2Int - Return bit-level equivalent of expression (int) f
28 *   for floating point argument f.
29 *   Argument is passed as unsigned int, but
30 *   it is to be interpreted as the bit-level representation of a
31 *   single-precision floating point value.
32 *   Anything out of range (including NaN and infinity) should return
33 *   0x80000000u.
34 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
35 *   Max ops: 30
36 *   Rating: 4
37 */
38int floatFloat2Int(unsigned uf)
39{
40  int s_ = uf >> 31;
41  int exp_ = ((uf & 0x7f800000) >> 23) - 127;
42  int frac_ = (uf & 0x007fffff) | 0x00800000;
43  if (!(uf & 0x7fffffff))
44    return 0;

1  if (exp_ > 31)
2    return 0x80000000;
3  if (exp_ < 0)
4    return 0;

1  if (exp_ > 23)
2    frac_ <<= (exp_ - 23);
3  else
4    frac_ >>= (23 - exp_);

 1  if (!((frac_ >> 31) ^ s_))
 2    return frac_;
 3  else if (frac_ >> 31)
 4    return 0x80000000;
 5  else
 6    return ~frac_ + 1;
 7}
 8/* 
 9 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
10 *   (2.0 raised to the power x) for any 32-bit integer x.
11 *
12 *   The unsigned value that is returned should have the identical bit
13 *   representation as the single-precision floating-point number 2.0^x.
14 *   If the result is too small to be represented as a denorm, return
15 *   0. If too large, return +INF.
16 * 
17 *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while 
18 *   Max ops: 30 
19 *   Rating: 4
20 */
21unsigned floatPower2(int x)
22{
23  int exp = x + 127;
24  if (exp <= 0)
25    return 0;
26  if (exp >= 255)
27    return 0x7f800000;
28  return exp << 23;
29}