Practice Levels

  • Level A: 1-4
  • Level B: 5-7

Exercises

  1. Most people can count to 10 on their fingers; computer scientists can do better. Write answers to these expressions as simple arithmetic expressions or exact numbers in base ten.

    1. If you regard each finger as one bit, with finger extended as 1 and finger curled as 0, how high can you count in base 2 using ten fingers and starting at zero?
    2. With both ten fingers and ten toes?
    3. Now use just ten toes, with the left pinky toe as a sign bit for two’s (toes) complement numbers. What is the minimum expressible number? (10-bit two’s complement)
    4. What is the maximum fingers-and-toes-complement (20-bit two’s complement) number?
  2. Perform the following conversions:

    • Show the 8-bit two’s complement representation of -10710 and 10710.
    • Show the decimal (base 10) notation of the signed integers whose 16-bit two’s-complement representations are given in hexadecimal notation as 0x5F8C and 0xCAFE.
  3. Perform the following calculations on the 8-bit representation of unsigned integers. Show your work and do the calculations in binary. Write the 8-bit result value below the line. Indicate for each calculation whether or not overflow has occurred.

       00101101       11111111       00000000
     + 01101111     + 11111111     - 11111111
     ----------     ----------     ----------
    
  4. Repeat all parts of problem 3 assuming the 8-bit values represent signed integers in two’s complement representation.

  5. From CSAPP3e Homework Problem 2.77.

    Your goal is to accomplish the same result as the C expression x*k, to multiply the C int x by various constants, k, as listed. However, you may use only the C operators <<, -, and +, the variable x, and any literal numbers. (You may not use the multiplication operator, *.) Think about powers of 2. Each is possible with a small expression using only a few operators.

    1. x * 17
    2. x * -7
    3. x * 60
    4. x * -112
  6. (Omitted for now.)

  7. Consider the following C function, assuming the type int indicates a 32-bit two’s-complement signed integer.

    int absolute_value(int x) {
      if (x < 0) {
        return -x;
      } else {
        return x;
      }
    }

    There is one problematic value for the argument x that causes absolute_value to return a surprising result that is not the true absolute value of x.

    1. Give the problematic argument value in decimal notation.
    2. Give the 32-bit two’s-complement representation of the problematic argument value in binary notation.
    3. Give the return value (in decimal notation) that absolute_value produces when called on the problematic argument.
    4. Give the 32-bit two’s-complement representation of the return value that absolute_value produces when called on the problematic argument.
    5. Indicate which line of C code in absolute_value produces the surprising result and briefly describe how it happens with this value.
    6. (Challenge) Rewrite the function absolute_value to fix this problem. You may change all parts of the function definition that you wish except the argument type, which must be int, which we assume to be a 32-bit two’s-complement signed integer.