Integer Arithmancy
- Assign: Tuesday, 10 September
- Due: In class or under the door of Andy's office by 11:59pm on Tuesday, 17 September
- Policy: Individual graded synthesis assignment
- Submit: A neat paper copy of the cs240-integers-worksheet.pdf submission sheet .
- Reference:
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.
-
[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.
- 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?
- With both ten fingers and ten toes?
- 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)
- What is the maximum fingers-and-toes-complement (20-bit two’s complement) number?
-
[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
and0xCAFE
.
-
[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 ---------- ---------- ----------
-
[3 points] Repeat all parts of problem 3 assuming the 8-bit values represent signed integers in two’s complement representation.
-
[4 points] CSAPP3e Homework Problem 2.77.
(Summary:) Implement the C expression
x*k
to multiply the Cint
x
by various constants,k
, as listed. You may use only the C operators<<
,-
, and+
, the variablex
, and any literal numbers. Think about powers of 2. Each is possible with a small expression using only a few operators.x * 17
x * -7
- [Independent]
x * 60
- [Independent]
x * -112
-
[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 forx
andy
.Declarations:
int x = ...; // any value int y = ...; // any value unsigned ux = (unsigned)x; unsigned uy = (unsigned)y;
Expressions:
(x < y) == (-x > -y)
((x + y) << 4) + y - x == 17 * y + 15 * x
- [Independent]
~x + ~y + 1 == ~(x + y)
(ux - uy) == -(unsigned)(y - x)
- [Independent]
((x >> 2) << 2) <= x
-
[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 causesabsolute_value
to return a surprising result that is not the true absolute value ofx
.- Give the problematic argument value in decimal notation.
- Give the 32-bit two’s-complement representation of the problematic argument value in binary notation.
- Give the return value (in decimal notation) that
absolute_value
produces when called on the problematic argument. - Give the 32-bit two’s-complement representation of the return
value that
absolute_value
produces when called on the problematic argument. - Indicate which line of C code in
absolute_value
produces the surprising result and briefly describe how it happens with this value. - (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 beint
, which we assume to be a 32-bit two’s-complement signed integer.