CSAPP Datalab (New)

CMU updated their lab questions for CSAPP last year, and many solutions online are actually outdated. I’m trying to figure out these questions and I’ll post my solutions for the latest Data Lab with some explanations here. I hope this could be helpful if you have any problems with the lab questions.

1. bitXor

1
2
3
4
5
6
7
8
9
10
/* 
 * 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));
}

For this problem, we need to know that not(not a and not b) = a or b (i.e. ~(~x & ~y) = x | y) (De Morgan’s laws) and (x or y) and not(x and y) = x xor y.

2. TMin

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

TMin = 1000...0000 in binary, so shift 1 to the left (0000...0001 in binary) by 31 to get TMin.

3. isTmax

1
2
3
4
5
6
7
8
9
10
11
12
/*
 * 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) {
  // TMax = ~(TMin) (simply flip the bit-level representation of TMin (i.e. 100000...))
  int tmax = ~(1 << 31);
  return !(~(~x & ~tmax) & ~(x & tmax));
}

The first trick is to get the value of TMax by simply flipping the bit-level representation of TMin.

Then, you might notice that the return statement is pretty similar to the one in bitXor, only with an extra ! (logical negation). Actually, by doing the xor operation, we are checking the equality of two numbers. We could also say that the xor operation works just like !=, so by adding a ! to our xor implementation, we are literally just checking the equality like what == does.

4. allOddBits

1
2
3
4
5
6
7
8
9
10
11
12
/* 
 * 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 andResult = (x & 0xAAAAAAAA);
  return !(~(~0xAAAAAAAA & ~andResult) & ~(0xAAAAAAAA & andResult));
}

Read the prompt first. It could be helpful.

Then you may start to wonder what is special about 0xAAAAAAAA. Well, you can try to convert it to binary and it turns out to be 0xAAAAAAAA = 0b10101010101010101010101010101010, which is a number with all odd-numbered bits in the word set to 1, exactly the same thing asked in this problem.
What we are going to do is calculate x & 0xAAAAAAAA. This operation allows us to ignore all numbers on even-numbered bits. Since the numbers on even-numbered bits are not helpful for this problem and it only makes things more tricky so we should ignore them. By ignoring the even-numbered bits, we will get the same value as 0xAAAAAAAA if x has all of its odd-numbered bits set to 1.
Finally, check if the result has the same value as 0xAAAAAAAA using the equality check trick we did before.

5. negate

1
2
3
4
5
6
7
8
9
10
11
/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  // To negate a number in 2's complement, invert the bits and add 1
  return ~x + 1;
}

-a = ~a + 1

6. isAsciiDigit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* 
 * 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) {
  // Compare x with 0x30 (0x30 <= x)
  int y_x = x + (~0x30 + 1);
  int sign_yx = (y_x >> 31) & 1;
  int result1 = !sign_yx;
  // Compare x with 0x39 (x <= 0x39)
  int y_x_2 = 0x39 + (~x + 1);
  int sign_yx_2 = (y_x_2 >> 31) & 1;
  int result2 = !sign_yx_2;
  return result1 & result2;
}

We are doing comparison in this question. Check question 8 to see how we compare two numbers using only bit-level operations.

7. conditional

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
 * 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 mappedX = ((x | (~x + 1)) >> 31);
  int yResult = y & mappedX;
  int zResult = z & (~mappedX);
  return yResult + zResult;
}

The ternary operator x ? y : z will return y if x is true and z otherwise. In order to map an integer value to boolean, we first need to know that 0 will be converted to false while any other values will be converted to true, so we need to somehow create an algorithm to map x to a new domain.
The expression ((x | (~x + 1)) >> 31) will convert x to 0 if x = 0 and convert x to -1 (1111….1111 in binary) if x != 0.
Then, we can apply the mapped x value to y and z. Since we have 0000...0000 or 1111...1111 as our mapped value in bit level representation, we could simply apply an AND operation.

  • a AND 0 will empty the value and set all bits to 0.
  • a AND -1 will give out exactly the same value as the input.

By doing so, we can set either of y and z to zero while leaving one of them unchanged. Finally, we can get the result by adding them up.

8. isLessOrEqual

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 
 * 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 sign_x = (x >> 31) & 1;
  int sign_y = (y >> 31) & 1;
  int y_x = y + (~x + 1);
  int sign_yx = (y_x >> 31) & 1;
  int result = (sign_x & !sign_y) | ((!(sign_x^sign_y)) & !sign_yx);
  return result;
}

There are two cases that x <= y:

  • x is negative and y is positive
    We can determine this by checking the sign bits of x and y. If x is signed while y is not, return 1;
  • x and y have the same sign but y - x is positive.
    We can determine this by checking if the sign bits of x and y are the same and checking the sign bit of y - x. If both x and y have the same sign bit and sign bit of y - x is 0, return 1.

9. logicalNeg

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 | (~x + 1)) >> 31) + 1;
}

For a logical negation, we want it to return 1 when and only when x is 0. A special property of 0 in 2’s complement is that there’s no negative zero, so (x | -x) will give out 0 if x is zero, while giving out a number with 1 on its most significant bit when x is nonzero.
Then we shift the value of (x | -x) by 31 so that we can get -1 if x is nonzero or 0 if x is zero. (Remember that arithmetic shift copies the most significant bit while shifting, which means if we have a number with 1 on its MSB, it will keep copying 1 and give us 111....111 which is -1 in 2’s complement)

Finally, we add a 1 as bias to get the result.

10. howManyBits

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
29
30
31
32
33
34
35
/* 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) {
  // flip if negative => remove the duplicated sign bits
  int negativeFlag = (x >> 31) & 1;
  // conditional
  int mappedFlag = ((negativeFlag | (~negativeFlag + 1)) >> 31);
  int yResult = ~x & mappedFlag;
  int zResult = x & (~mappedFlag);
  int newX = yResult + zResult;
  // right align & fill with ones
  int full1s = newX | newX >> 16;
  full1s = full1s | full1s >> 8;
  full1s = full1s | full1s >> 4;
  full1s = full1s | full1s >> 2;
  full1s = full1s | full1s >> 1;
  // count ones
  int count = (full1s & 0x55555555) + ((full1s >> 1) & 0x55555555);
  count = (count & 0x33333333) + ((count >> 2) & 0x33333333);
  count = (count & 0x0F0F0F0F) + ((count >> 4) & 0x0F0F0F0F);
  count = (count & 0x00FF00FF) + ((count >> 8) & 0x00FF00FF);
  count = (count & 0x0000FFFF) + ((count >> 16) & 0x0000FFFF);
  // plus one (sign bit)
  return count + 1;
}

This question is one of the trickiest questions in this lab. It took me quite a long time to figure this out.
We can divide the whole process into three steps.

  • Flip the bits if x < 0
    In 2’s complement, if we have more bits available than what is required to represent a number, we copy the sign bit until all empty bits are filled with duplicated sign bits, which is called sign extension. By flipping the bits of a negative number, we can remove the leading ones in its bit level representation caused by sign extension.
  • Fill the lower bits with ones
    Now we have a new number with bit level representation like 0000 0000 1000 1010. We want to fill the lower bits with ones (i.e. turn it into 0000 0000 1111 1111) so that we can count the number of ones to get our result.
  • Count ones
    We can count ones by grouping and adding. Each step of those five, adds neighbouring bits together in groups of 1, then 2, then 4 etc. The method is based in divide and conquer.
    Check out this post on StackOverflow for detailed explanation on this algorithm: https://stackoverflow.com/questions/3815165/how-to-implement-bitcount-using-only-bitwise-operators

Don’t forget to add a one for sign bit for our final result.

I strongly recommend you to pick a small number (e.g. a 8-bit number) and do the whole process by hand to understand how the algorithm works.

11. floatScale2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* 
 * 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) {
  //0
  if(uf == 0 || uf == (1 << 31))
    return uf;
  //Special value
  if(((uf >> 23) & 0xff) == 0xff)
    return uf;
  //Denormalized
  if(((uf >> 23) & 0xff) == 0x00) 
    return ((uf & 0x007FFFFF) << 1) | ((1 << 31) & uf);
  // Normalized
  return uf + (1<<23);
}

According to the IEEE Standard for floating point number, a single-precision floating point number is stored and formatted like this.

Screen-Shot-2019-02-17-at-3.44.24-PM

And there’re generally three ways to interpret a floating point

  • Normalized
  • Denormalized
  • Special value

For this question, we first need to determine whether this number is a normalized, denormalized or special value representation by checking the exp field. We can get the value of exp field using ((uf >> 23) & 0xff) (i.e. shift to right by 23 and get rid of the sign bit).
If the number is a 0 or special value representation, return uf without any modification.
If the number is a denormalized representation, shift the frac field to left by 1 without changing the exp field. To get the frac field, we use (uf & 0x007FFFFF) to empty all bits but the frac field. Don’t forget to put the sign bit back.
If the number is a normalized representation, add 1 to the exp field.

12. floatFloat2Int

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/* 
 * 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 sign = (uf >> 31) & 0x1;
  int e = (uf >> 23) & 0xFF;
  int frac = uf & 0x7FFFFF;
  
  int exponent = e - 127;
  // add the implicit one
  int newFrac = 0x1000000 + frac;
  int shifted;
  // if e equals zero -> denorm -> will be rounded to 0 while casting to integer
  // if exponent is negative -> will be rounded to 0 while casting to integer
  if(exponent < 0 || e == 0) {
    return 0;
  }
  // if exponent is greater than or equal to 31 -> overflow
  // if e == 0xFF -> special value
  if(exponent >= 31 || e == 0xFF) {
    return 0x80000000;
  }
  // if exponent is greater than 24, shift to left by (exponent - 24)
  if(exponent > 24) {
    shifted = newFrac << (exponent - 24);
  }
  // if exponent is less than or equal to 24, shift to right by (24 - exponent)
  else if(exponent <= 24) {
    shifted = newFrac >> (24 - exponent);
  }
  // negate if signed
  if(sign)
    shifted = -shifted;
  return shifted;
}

In order to cast a floating point number into integer, we first need to extract the three fields of a floating point representation.
Screen-Shot-2019-02-17-at-3.44.24-PM

  • 1 sign bit s
  • 8 bits for exp field
  • 23 bits for frac field

Then we subtract the bias to get the real exponent and add the implicit 1 to frac field in order to get the real mantissa M. Although there is a denormalized representation for representing small numbers, but since we are casting to integer and all those small numbers will be rounded to 0, we don’t need to care about the denormalized representation in this case.

Check the exponent. If the exponent is less less than zero (negative exponent) or the exp field is zero (denorm), return 0 because the result will be rounded to zero anyway.

If the exponent is greater than or equal to 31 (overflow while casting to integer) or the exp field is equal to 0xFF (special values), return 0x80000000 according to the instruction in the prompt.

If the exponent is greater than 24, left shift by exponent - 24.

If the exponent is less than or equal to 24, right shift by 24 - exponent.

Finally, we check the sign bit an negate our result if the original number is nagetive.

13. floatPower2

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
29
30
31
32
33
34
35
/* 
 * 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 < -150) {
    return 0;
  }
  if(x >= -150 && x <= -127) {
    //denorm
    int shiftAmount = (-x - 127);
    int frac = 1 << shiftAmount;
    return frac;
  }
  if(x >= -126 && x <= 127) {
    //norm
    int e = (x + 127) << 23;
    return e;
  }
  if(x >= 128) {
    //inf
    int e = 0xFF << 23;
    return e;
  }
  return 0;
}

For this question, we should consider 4 conditions:

  • Too small to be represented as denormalized
  • Denormalized
  • Normalized
  • Too big

Since we know that we have 1 bit for sign, 8 bits for exp field and 23 bits for frac field in a single precision number, we can figure out the range of those four conditions.

In normalized representation, the maximum value for exp field is 254 (since we cannot have all ones), so the maximum exponent should be 254 - Bias = 254 - 127 = 127. The minimum value for exp field is 1 (we cannot have all zeros as well), so the minimum exponent value should be 1 - Bias = 1 - 127 = -126.

In denormalized representation, the exp field is always 0 (giving out an exponent of -126) and the powers of two are represented by the frac field. The minimum value in our case is 2^-150 while the maximum value is 2^-127.

Hence, everything with an exponent less than -150 should be regarded as 0, and everything with an exponent greater than 127 should be +INF.

After knowing the range of each representation, we can set up a conditional statement and compose the result.

As we mentioned before, the powers of 2 in denormalized representation are calculated by manipulating the bits in frac field. Therefore, we can simply shift the 1 in frac field by correct amount to get the result.

For normalized representation, we change the value of exp field to get a power of 2, but don’t forget to shift the whole exp field to the correct position (shift to left by 23). Leave the frac field empty so that it will be interpreted as 1.0.