\documentstyle[11pt,prob,fullpage]{article}

\setlength{\parindent}{0em}
\setlength{\parskip}{1ex}

\newcommand{\hfile}[1]{{\it HOMEDIR}{\tt /#1}}
\newcommand{\afile}[1]{{\it ASSTDIR}{\tt /#1}}

\begin{document}

\begin{center}
{\Large CS 347, Spring 1998}\\[1ex]
{\Large Homework Assignment 2}\\[1ex]
{\large Assigned: Jan.~22\\Due: Thurs., Jan.~29, 3:00PM}
\end{center}

\section*{Policy}

You may work in a group of up to 3 people in solving the problems for
this assignment.  Turn in a single writeup per group, indicating all
group members, plus a single code file.  In the code file, identify
all of the group members.

\section*{Logistics}

Any clarifications and revisions to the assignment will be posted on
Web page {\tt assigns.html} in the class WWW directory.

In the following, {\it HOMEDIR} refers to the directory:
\begin{verbatim}
/afs/cs.cmu.edu/academic/class/15347-s98/public
\end{verbatim}
and {\it ASSTDIR} refers to the subdirectory \hfile{asst/h2}.

You should hand in a hard copy document for this assignment.  One
option is to simply write your answers on the assignment handout.  If
you submit a separate document, formatted text is preferred to hand
written.  In addition, you will be submitting your version of the file
{\tt numbers.c}, as described below.

\section*{Two's Complement Arithmetic}

The purpose of this part of the assignment is to become more familiar
with the bit representations of two's complement numbers and the
bit-level operations in C.

Suppose we want to express arithmetic operations and comparisons in C,
but we restrict ourselves to a limited set of C operators and
statement types.  In particular, our arithmetic expressions are
limited to:
\begin{enumerate}
\item Constant values {\tt 0L}, {\tt 1L}, and {\tt SIGN\_BIT} (a
compile time constant set to the bit position of the sign bit, which
will be $W-1$ where $W$ is the word size of your machine.)  {\bf Note:}
Your solutions must work for an arbitrary word size, including
machines for which {\tt int}'s and {\tt long int}'s have different
length.  You should be OK as long as you include the suffix ``L'' with
your constants.
\item Unary operations \verb@!@ (logical negation) and \verb@~@ (bitwise
{\sc Not}).
\item Binary operations \verb@+@ (addition), \verb@<<@ (left shift),
\verb@>>@ (right shift), \verb@&@ (bitwise {\sc And}),
\verb@^@ (bitwise {\sc Exclusive-Or}), and \verb@|@ (bitwise {\sc
Or}).
\end{enumerate}
Assume that the right shift operator \verb@>>@ implements an
{\it arithmetic} shift, where the new positions on the left are filled
with the most-significant bit of the original operand.

Note that this list omits many of the familiar C operations, such as
arithmetic negation, subtraction, comparisons, and logical
connectives.  {\bf In addition, you may not use conditionals, looping
constructs, or switch statements.}

\begin{problem}
Write expressions using the above restrictions for the following values:
\begin{choice}
\item The smallest representable long integer: {\em TMin}
\item {\tt -1L}
\item The largest representable long integer: {\em TMax}
\end{choice}
\end{problem}

\begin{problem}
Recall that in C, the relational and logical operations yield value 1
to denote {\sc True} and 0 to denote {\sc False}.  Unfortunately,
we've eliminated most of these operations.  Write expressions in our
restricted notation equivalent to the following expressions regarding long
integer variable {\tt x}.  {\bf Note that your expressions must yield
only 0L or 1L}.
\begin{choice}
\item {\tt x == 0L}
\item {\tt x < 0L}
\item {\tt x > 0L}
\end{choice}
\end{problem}

\begin{problem}
Write expressions in our restricted notation equivalent to the following arithmetic operations on long integer variable {\tt x}:
\begin{choice}
\item {\tt -x}
\item Absolute value: \verb@(x < 0L) ? -x : x @ [Note that this does not
compute the absolute value when {\tt x} equals {\em TMin}.  Your
solution should duplicate this incorrect behavior].
\end{choice}
\end{problem}

\begin{problem}
Write expressions in our restricted notation equivalent to the
following relational operations for long integer variables {\tt x} and {\tt y}:
\begin{choice}
\item {\tt x == y}
\item {\tt x > y}
\end{choice} 
\end{problem}

\begin{problem}
Demonstrate that your solutions to the above problems are correct.
That is, retrieve the file {\tt files.tar} from {\em ASSTDIR}.
Running the command {\tt tar xf file.tar} extracts three files: {\tt
Makefile}, {\tt numbers.c}, and {\tt numtest.c}.  Use the Makefile for
your compilations.  The file {\tt numbers.c} contains procedure
skeletons for each of the computations described above.  Insert your
solution expressions into these functions.  Compile your code using
the command {\tt make}.  and run the program {\tt numtest}.
Ist should print the message ``All tests passed.''

Submit your solution by naming your file {\tt XXX-numbers.c} where
{\tt XXX} is the Andrew ID of one of your team members.  Copy this
file into the directory {\tt {\em ASSTDIR}/handin}.  You should do
this before the due date and time of the assignment.  You have only
write and list permission for this directory.  Be careful not to
overwrite anyone else's file.

In your written solution, indicate the Andrew ID {\tt XXX} you used.
\end{problem}

\newpage
\section*{Floating Point Number Formats}

Suppose we want to devise a floating point format that fits in only 5
bits (!), but following the general design of the IEEE floating point format.
Here's the plan:
\begin{itemize}
\item There is no sign bit.  Only nonnegative values can be represented.
\item
The three-bit exponent field uses a biased representation, with a bias
of 3.
\item
When the exponent is 000, the mantissa is denormalized.
\item
Exponent value 111 is used to represent infinity and not-a-number.
\item
The two-bit significand field has an implied leading ``1.''\ for the normalized
case.
\end{itemize}


\begin{problem}

For the exponent, each three-bit pattern encodes an exponent weight
$2^E$.  Fill in the following table showing the numeric
weights for each bit pattern.  Express these as exact rational numbers,
e.g., 7, 7/16, or 7/4, rather than their decimal equivalents.  Note
that you are to express the total weight of the exponent field $2^E$
rather than the exponent $E$.  For cases that do not encode weights, write ``N.A.'' (for not applicable).
\begin{center}
\renewcommand{\arraystretch}{1.2}
\begin{tabular}{|c|c|c|}
\hline
Bit Pattern & Exp. Weight $2^E$  \\
\hline
000 &\\
\hline
001 &\\
\hline
010 &\\
\hline
011 &\\
\hline
100 &\\
\hline
101 &\\
\hline
110 &\\
\hline
111 &\\
\hline
\end{tabular}
\end{center}

\end{problem}

\begin{problem}
For the
mantissa, each two-bit pattern encodes a mantissa value $m$, where
the value will depend on whether or not the number is normalized.
Fill in the following table showing the two possible numeric values
for each bit pattern.  Express these as exact rational numbers, e.g.,
7, 7/16, or 7/4, rather than their decimal equivalents.
\begin{center}
\renewcommand{\arraystretch}{1.2}
\begin{tabular}{|c|c|c|}
\hline
Bit Pattern & Normalized & Denormalized \\
\hline
00 &&\\
\hline
01 &&\\
\hline
10 &&\\
\hline
11 &&\\
\hline
\end{tabular}
\end{center}
\end{problem}

\begin{problem}
Fill in the following table indicating the value represented
by each possible 5-bit pattern.  Express the entries as exact rational
numbers, or with the special values $\infty$ or NaN.
\begin{center}
\renewcommand{\arraystretch}{1.4}
\begin{tabular}{lc|c|c|c|c|}
\multicolumn{2}{c}{} & \multicolumn{4}{c}{Significand} \\
\multicolumn{2}{c}{} &
 \multicolumn{1}{c}{\makebox[.75in]{00}} & 
  \multicolumn{1}{c}{\makebox[.75in]{01}} & 
  \multicolumn{1}{c}{\makebox[.75in]{10}} & 
  \multicolumn{1}{c}{\makebox[.75in]{11}} \\
\cline{3-6}
 & 000 & & & & \\
\cline{3-6}
 &  001 & & & & \\
\cline{3-6}
 & 010 & & & & \\
\cline{3-6}
Exponent & 011 & & & & \\
\cline{3-6}
 & 100 & & & & \\
\cline{3-6}
 &  101 & & & & \\
\cline{3-6}
 & 110 & & & & \\
\cline{3-6}
 & 111 & & & & \\
\cline{3-6}
\end{tabular}
\end{center}
\end{problem}

\begin{problem}
For each of the following rational numbers, show what floating point
values these would be converted to using the three following rounding
rules:
\begin{description}
\item[RTZ] Round toward zero
\item[RTI] Round toward positive infinity
\item[RTE] Round to nearest even
\end{description}
Give your answer as rational numbers and/or special values, i.e., your
answers should match entries from the table of the previous problem.
\begin{center}
\renewcommand{\arraystretch}{1.3}
\begin{tabular}{|c|c|c|c|}
\hline
Value & \makebox[.75in]{RTZ} & \makebox[.75in]{RTI} & \makebox[.75in]{RTE} \\
\hline
1/3 &&&\\
\hline
11/16 &&&\\
\hline
9 &&&\\
\hline
11 &&&\\
\hline
15 &&&\\
\hline
\end{tabular}
\end{center}
\end{problem}

\end{document}
