Assignment 3, due Sept 11

Solutions

Part of the homework for CS:2820, Fall 2015
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. Background: Here is a working Java program (from the file t.java):
    class t {
            static int x(int a, int b) {
                    while (b != 0) {
                            int c = a;
                            a = c ^ b;         //a
                            b = (c & b) << 1;  //b
                    }
                    return a;
            }
    
            static int y( int i ) {
                    return (i < 3)? i: x(x(y(i - 1), y(i - 2)), y(i - 3) );
            }
    
            public static void main( String[] args ) {
                    for (int i = 0; i < 11; i++) {
                            System.out.println( "y(" + i + ") = " + y(i) );
                    }
            }
    }
    

    Warning: the above code has no useful comments because it is designed as a scavenger hunt to motivate a close reading of the textbook's summary of Java operators. In any other context, there would be no excuse for writing such obscure code, particularly without any explanatory comments.

    Answer the following: (0.2 points each part)

    a) What does the ^ operator do on the line marked //a?

    This is the bitwise exclusive-or operator. (It exclusive or's the corresponding bits of each operand to produce the bits of the result. For example, 10 (1010 in binary) exclusive ored with 3 (0011 in binary) gives 9 (1001) in binary.)

    b) What does the & operator do on the line marked //b?

    This is the bitwise and operator. (It takes the logical and of corresponding bits of each operand to produce the bits of the result. For example, 10 (1010 in binary) anded with 3 (0011 in binary) gives 2 (0010) in binary.)

    c) What does the << operator do on the line marked //b?

    This is the left-shift operator. (It takes the bit pattern of its left operand and shifts it leftward the number of bits specified by the right operand. For example, 5 (0101 in binary) shifted left 1 place is 10 (1010 in binary).)

    d) Is ? an operator, and what does it do in the method named y?

    This is only the first half of a three operand conditional operator. The operand to its left is the condition. If the condition is true, the value of the expression is the operand to its right.

    e) Is : an operator, and what does it do in the method named y?

    This is only the second half of a three operand conditional operator. The operand to its left is the value returned if the condition is true, while the operand to the right gives the value returned if the condition is false.

  2. A short question: What does the method named x do in the code given with problem 1? (You may need to do some experiments in order to determine this.) (0.5 points)

    In general, it returns the sum of its integer arguments. For example, x(15,20) returns 35. (Each iteration uses the exclusive-or operation to compute the tentative sum of the bits of the two operands, ignoring the carry bits, and then it uses the and and shift operations to compute the carry bits. Successive iterations continue until there aare no more carries.)

  3. Background: Informally, digital logic gates are devices where each has multiple inputs and one output. The output of a gate may be connected to zero or more inputs of other gates by wires. Each gate has a time delay, as does each wire. The fundamental events in a digital logic system are changes in the values of the inputs or outputs of gates.

    There are many types of gates. For example, an and gate produces an output of true as a result of all of its inputs becoming true (but only after a time delay), and it output of false as a result of any inputs becoming false (again, after a time delay). There are an open-ended number of different kinds of gates. For any particuar kind of gate, there are specific named inputs, for example, every two-input and gate might have inputs named a and b.

    Each wire transmits its input (the output of some gate) to its output (a specific input of some gate) after the wire's delay.

    Answer the following: (0.5 points each part)

    a) Give Java code to define a class that captures all of the attributes of a wire, as described above. We are not interested in methods, just a description of the data.

    class Wire {
            float  delay;      // delay of this wire
            Gate   driven;     // what gate does this wire drive
            String input;      // what input of that gate does this wire drive
    
    	//Bug: do we need to know the following?  Unclear.
            Gate   driver;     // what gate does this wire drive
    }
    

    b) Give Java code to define a class that captures all of the attributes of a gate, as described above. Because there are subclasses of gates, you should only include material that you infer, from the above, is universally applicable to all kinds of gates.

    import java.util.LinkedList;
    
    class Gate {
            float  delay;      // delay of this gate
            string name;       // name of this gate
            LinkedList <wire> driven = new LinkedList <wire> ()
    
    	//Bug: do we need to know the following?  Unclear.
            LinkedList <wire> driver = new LinkedList <wire> ()
    
    	//Bug: there are multiple types of gates, how do we deal with this?
    	//Bug: and for each gate type how do we handle multiple named inputs?
    }
    

    c) Focusing only on the information given above, suggest, at a fairly high level, what a text file might look like that is used to initialize a simulation model. Think as if you might have to implement this, so don't describe anything complicated. Keep it as simple as possible!

    Here is an example syntax that might work

    gate and a 10.0
    gate or b 3.5
    gate not c 4.8
    wire a b in1 1.0
    wire a c in 1.5
    wire c a in1 1.0
    

    In the above, each line begins with gate or wire inidcating what part the line describes.

    Lines starting with gate are followed by the type of the gate, the name of the gate, and the delay of the gate.

    Lines starting with wire are followed by the name of the source gate, the name of the destination gate, the name of the specific input to the destination, and the delay of the wire.

    It would be reasonable to require that the gates referenced by each wire be defined before that wire. This avoids the problem of having to deal with forward references.