Assignment 7, due Mar 13Solutions
Part of
the homework for CS:2630, Spring 2015

0) (srcdst)&3 = 0 (identical alignment)
1) (srcdst)&3 = 1
2) (srcdst)&3 = 2
3) (srcdst)&3 = 3
a) Which of the above cases could be handled by logic similar to that for the ultrafast version of strlen() given in the notes? (0.5 points)
Case 0.
b) Which two of the above cases could be improved significantly by logic that copied one halfword at a time? (0.5 points)
Case 0 and case 2. Of course, in case 0, it would be better to copy whole words, but working with halfwords allows us to copy two bytes at a time instead of working with eacy byte individually.
Consider this bit of highlevel language code in the style of C and Java (it is largely the same in Python, except for the curly braces and semicolons):
{ int b = 1; do { int c = a ^ b; b = (a & b) << 1; a = c; } while (b != 0); }
This code transforms the integer variable a from its value prior to the code to a new value after it.
a) The code of the loop body describes a logic circuit found in Chapter 8 of the notes. What is the name of that circuit? (0.3 points)
It is an incrementer, using the and function to compute the carry (as variable b) and the exclusive or function to compute the sum.
b) What does this code do to the variable a? (Try it if you can't figure it out.) (0.3 points)
It increments it. Here is a demonstration, written in Python:
a = 0 while a < 20: b = 1 while b != 0: c = a ^ b b = (a & b) << 1 a = c print( a )
c) If the integer variables in this code are 32 bits each, what is the maximum number of iterations of the loop? (0.4 points)
32. The loop propagates the carry from one bit position to the next, so the worst case is when the number being incremented is all ones, that is, ...11111_{2}.
There is an overflow if the sign of the addend a and the sign of the augend b are the same, but the sign of the sum c = a + b is different.
For example, if you add two positive numbers and get a negative result, there was an overflow.
a) Give a boolean equation for V as a function of a_{n–1}, b_{n–1} and c_{n–1}, (for an n bit word). (0.5 points)
First note that x ⊕ y is true when x and y are different and false when they are the same, so all of the "samedifferent" logic can be done with exclusiveor operators. There are many equivalent solutions. Here are some of them:
V = ¬(a_{n–1} ⊕ b_{n–1}) ∧ (a_{n–1} ⊕ c_{n–1})
V = (¬a_{n–1} ⊕ b_{n–1}) ∧ (b_{n–1} ⊕ c_{n–1})
V = (a_{n–1} ⊕ ¬b_{n–1}) ∧ (c_{n–1} ⊕ a_{n–1})
b) Draw the corresponding logic circuit, in the style of the figure captioned Derivation of the condition codes in Chapter 8. (Draw only the part of the circuit that gives the V output in terms of the inputs and output(s) of the most significant full adder in the circuit.) (0.5 points)
There are, of course, many ways of drawing the circuit. Here is one that puts it in the context of an adder and the other condition codes: