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 cs240integersworksheet.pdf submission sheet .
 Reference:
Exercises
Please write your answers on the cs240integersworksheet.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? (10bit two’s complement)
 What is the maximum fingersandtoescomplement (20bit two’s complement) number?

[4 points] Perform the following conversions:
 Show the 8bit two’s complement representation of 107_{10} and 107_{10}.
 Show the decimal notation of the signed integers whose 16bit
two’scomplement representations are given in hexadecimal
notation as
0x5F8C
and0xCAFE
.

[6 points] Perform the following calculations on the 8bit 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 8bit 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 32bit two’scomplement 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 32bit two’scomplement 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 32bit two’scomplement 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 32bit two’scomplement signed integer.