Due Sunday, September 7, 2014 @ 11:59pm
Goals
This assignment covers a range of topics related to number representation. It is also intended to get you familiar with basic C bitwise operators.
Submission
Submit your solution by creating a directory named hw1 that contains a file named hw1.txt.
Please use the provided format in hw1.txt. File names are casesensitive and the submission program will not
accept your submission if your file names differ at all from those
specified. From within that directory, type submit hw1
. Partners are not allowed on this assignment.
Exercises
Problem 1: Number representation  5pts
Put your answers to the following questions in hw1.txt
Assume we are dealing with 8 bit numbers for this problem. Fill in the following table according to the representation given by the column header. If you are given binary or hexadecimal, give the decimal value interpreted under the given representation. If you are given a decimal value, convert it to binary under the given representation and write your answer in hexadecimal. Put "n/a" if the value cannot be converted.
unsigned  sign & magnitude  one's complement  two's complement  
0b11110000 

0b00001111  
0x0F
 
0xA1
 
0xFF
 
0xBE
 
64
 
35
 
128
 
128

Problem 2: C bitwise operators  5pts
Put your answers to the following questions in hw1.txt
Note: If you are unfamiliar with or need to review the truth tables for the standard 2input logic gates, just Google or Wikipedia 'logic gates.' Same goes for 'bitshifting.'
C provides bitwise commands for AND(&), OR(), XOR(^),
and NOT(~)
.
 Let
x
be a singlebit input. Fill in the following blanks with either0, 1, x,
orx̅
(NOT x
):x & 0 = ___
x  0 = ___
x ^ 0 = ___
x & 1 = ___
x  1 = ___
x ^ 1 = ___
 Based on your responses, look at the columns (grouped by operation)
above. Which operation would be useful for:
 turning bits OFF?
 turning bits ON?
 flipping bits?
 Now let's also consider logical bitshifting operators for
LEFT SHIFTING(<<)
andRIGHT SHIFTING(>>)
which are also provided in C (you may have seen them in 61B in Java as well). Note that logical left shifting works on both unsigned and signed types, whereas logical right shifting only makes sense for unsigned types. Fill in the blank with the result in terms of an 8bit binary number:
((0b01010101 << 3) & 0xAE)  2 = ___
 Fill in the blank with the simplest numerical expression in terms of
x
, simple arithmetic operators (+, , *, /
, and%
), and numerical constants :
x << 4 = ___
 Fill in the blank with the simplest numerical expression in terms of
x
, simple arithmetic operators (+, , *, /
, and%
), and numerical constants :
x >> 1 = ___
 Write a simple expression for turning the
n
th bit ON for a numberx
, in terms ofn, x,
bits, and bitwise operators. You may assumex
has at leastn+1
bits, and that the bits are indexed from zero.
 Fill in the blank with the result in terms of an 8bit binary number:
Problem 3: Picking representations  6pts
Put your answers to the following questions in hw1.txt
Assume we are working with 8bit numbers for the entirety of this question.
 For each part below, you will be given a choice of two number representations to choose between. It's your job to pick the better number representation for the given criteria, or denote that both representations are equally good. Explain your answer in one sentence or less.:
 You would like multiple ways to represent 0:
ONE'S COMPLEMENT
orTWO'S COMPLEMENT
orBOTH
 You would like to maximize the range (distance between most negative represented number, and most positive represented number):
UNSIGNED
orSIGN AND MAGNITUDE
orBOTH
 You would like to represent an equal number of positive and negative numbers:
SIGN AND MAGNITUDE
orTWO'S COMPLEMENT
orBOTH
 You would like to maximize the range (distance between most negative represented number, and most positive represented number):
UNSIGNED
orTWO'S COMPLEMENT
orBOTH
 You would like multiple ways to represent 0:

Describe how you could compare numbers represented in two's complement, in at most 3 simple steps, if you only have unsigned comparators (<,≤,≥,>,=,≠) and basic logic (if, and, or, else). You can use as many of these components as you need. Please keep each step to two sentences maximum, but be sure to describe each step in enough detail.
Problem 4: Ternary  4pts
Put your answers to the following questions in hw1.txt
Consider the ternary system: base 3. We will denote this system with the subscript 3, here is an example for representing the number 4 in ternary, using only two trits: 11_{3}
Similar to the binary system, the ternary system has Three's Complement for representng negative numbers: to negate a three's complement number, the process is exactly the same as in two's complement because we invert the number and add one. However, tritwise inversion is slightly different: for each trit (that's what we call digits in ternary), its inverse can be found by subtracting it from 2.
For example, we represent 4 as 12_{3}
in ternary three's complement.
 For a system of
n
digit unsigned ternary numbers, how many numbers can be represented?  For an
n
digit signed three's complement ternary number (n > 1), what is the number of negative integers?  For an
n
digit signed three's complement ternary number (n > 1), how many zeros are there?  For a 4digit signed three's complement ternary number, what is the representation of 5?