pencil Practice number representation and computer arithmetic.

Exercises

Please write your answers on the cs240-integers-worksheet.pdf submission sheet to streamline the grading process.

Problems marked [Independent] must be completed without assistance from tutors or instructors.

  1. [3 points] 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. [4 points] Perform the following conversions:

    • Show the 8-bit two’s complement representation of -10710 and 10710.
    • Show the decimal notation of the signed integers whose 16-bit two’s-complement representations are given in hexadecimal notation as 0x5F8C and 0xCAFE.
  3. [6 points] Perform the following calculations on the 8-bit representation of unsigned integers. Show your work and do the calculuations in binary. Indicate for each calculation whether or not overflow has occurred.

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

  5. [4 points] CSAPP3e Homework Problem 2.77.

    (Summary:) Implement the C expression x*k to multiply the C int x by various constants, k, as listed. You may use only the C operators <<, -, and +, the variable x, and any literal numbers. Think about powers of 2. Each is possible with a small expression using only a few operators.

    1. x * 17
    2. x * -7
    3. [Independent] x * 60
    4. [Independent] x * -112
  6. [10 points] CSAPP3e Homework Problem 2.82.

    (Summary:) For each of the following expressions, based on the given declarations, indicate whether the expression always yields 1 (for all possible x, y, ux, uy, as established by these declarations). Indicate “yes” or “no” and why. When choosing “yes,” a brief description (no proof required) suffices to “describe the underlying mathematical principles.” When choosing “no,” provide counterexamples for x and y.

    Declarations:

     int x = ...; // any value
     int y = ...; // any value
     unsigned ux = (unsigned)x;
     unsigned uy = (unsigned)y;
    

    Expressions:

    1. (x < y) == (-x > -y)
    2. ((x + y) << 4) + y - x == 17 * y + 15 * x
    3. [Independent] ~x + ~y + 1 == ~(x + y)
    4. (ux - uy) == -(unsigned)(y - x)
    5. [Independent] ((x >> 2) << 2) <= x
  7. [10 points, Independent] 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.