CS-APP Datalab

1

tar xvf datalab-handout.tar

1

! ~ & ^ | + << >>

1
2
3
4
5
6

# 编译并运行
make && ./btest
# 对某个函数进行单元测试
make && ./btest -f bitXnor
# 对某个函数进行单元测试，且指定测试用例，以 -1 指定第一个参数，依次类推
make && ./btest -f bitXnor -1 7 -2 0xf

1

./dlc bits.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

//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
2
3
4
5
6
7
8
9

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

/*
 * 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) {
  return !!(~x)&!((~x)^(x+1));
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

/* 
 * 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 mask = 0x55 + (0x55 << 8);
  mask = mask + (mask << 16);
  return !(~(mask | x));
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

/* 
 * 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 f3 = !((x >> 4) ^ 3);
  int f0t9 =!! (!(x & 8) + !(x & 6));
  return f3 & f0t9;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

/* 
 * 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 f = !!x;
  int mask = ~f + 1;
  return (y & mask) + (z & ~mask);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

/* 
 * 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 fx = x >> 31;
  int fy = y >> 31;
  int f = fx ^ fy;
  int z = x + ~y + 1;
  return !!((f & fx) | ((!f) & ((!z) | z >> 31)));
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

/* 
 * 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 + 1) | x) >> 31) + 1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/* 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 f = !!(x >> 31);
  f = ~f + 1;
  x = (x & ~f) + (~x & f);
  int b16 = (!!(x >> 16)) << 4;
  x = x >> b16;
  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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/* 
 * 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) {
  unsigned s = uf & 0x80000000;
  unsigned exp = uf & 0x7f800000;
  unsigned f = uf & 0x007fffff;
  if(!exp){
    return s | (uf << 1);
  }
  if(!(exp ^ 0x7f800000)){
    return uf;
  }
  exp = exp + 0x00800000;
  if(exp == 0x7f800000){
    return 0x7f800000 | s;
  }

  return s | (exp & 0x7f800000) | f;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/* 
 * 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) {
  unsigned s = uf & 0x80000000,
           e = uf & 0x7f800000,
           f = uf & 0x007fffff;
  int exp = (e >> 23) - 0x7f;
  unsigned res = f | 0x00800000;
  if(exp < 0) return 0;
  if(exp >= 31) return 0x80000000;
  if(exp < 23)exp = 23 - exp;
  else exp = exp - 23;
  res = res >> exp;
  if(s)return -res;
  else return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

/* 
 * 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) {
  int exp = 0x7f + x;
  if(exp < 0x00)return 0;
  if(exp >= 0xff)return 0x7f800000;
  if(exp == 0x00)return 1;
  return exp << 23;
}