Name: SOLUTION SET________, Andrew Id: koz_________, Section: A+B_

Computer Science 15-111 (Sections A & B), Spring 2007

Quiz 1
Thu 25-Jan-2007

SOLUTIONS

All work is by hand. No computers or calculators or other devices allowed.

Show your work! Correct answers without supporting calculations will not receive any points.

Time: 25 minutes.

1. How can you quickly tell if a binary number is a power of 2 but not a power of 4?

2⁰ = 1 = 1 followed by 0 0’s
2¹ = 2 = 10 = 1 followed by 1 0’s
2² = 4 = 100 = 1 followed by 2 0’s
2ⁿ = 1 followed by n 0’s

4⁰ = 1 = 1 followed by 0 0’s
4¹ = 4 = 100 = 1 followed by 2 0’s
4² = 16 = 10000 = 1 followed by 4 0’s
4ⁿ = 1 followed by 2n 0’s (that is, an even number of 0’s)

Thus: a binary number is a power of 2 but not a power of 4 if it is:
a 1 followed by an odd number of 0’s.

2. We learned that Two’s Complement allows for “addition by subtraction”. Demonstrate this by solving (41 - 19) via addition (that is, 41 + (-19)) using signed bytes (that is, in 8-bit Two’s Complement). Convert your answer back to decimal.

41 = 32 + 8 + 1 = 0010 1001
19 = 16 + 2 + 1 = 0001 0011
flipped = 1110 1100
+1 = 1110 1101 = -19

41 = 0010 1001
+-19 = + 1110 1101
---------
0001 0110 (ignore the carry past the 8^th bit)
Check: 0001 0110 = 2 + 4 + 16 = 22 (and, yes, 41 – 19 = 22).

3. What will the following code print out?
System.out.println(0x32);
System.out.println(032);
System.out.println((char)32);
0x32 is hex = 3*16 + 2 = 50. 032 is octal = 3*8 + 2 = 26. char 32 = <space>.
So this prints out 50<newline>26<newline><space><newline>

4. List one value of double d that makes the following expression evaluate to true:
((Math.ceil(d) == Math.rint(d)) &&
(Math.round(d) != Math.floor(d)))

Math.ceil(d) is d if d is the integer greater than or equal to d.
Math.rint(d) will round d to the nearest integer.
If these two are equal, then d must be within 0.5 of the next-highest integer.

Note that one possibility is that d is in fact an integer, since ceil(d) == rint(d) for all integer values of doubles. But this is excluded by the second condition, since for all integer values of doubles, round(d) == floor(d).

So we need a non-integer value where round(d) != floor(d). This is also true for all doubles within 0.5 of the next-highest integer.

So: the answer is any double within 0.5 of the next-highest integer. Such as, say, 1.6 or, if you prefer negatives, -1.4.

5. State and prove (with a truth table) one of DeMorgan’s Laws.

We’ll do &&: !(a && b) == (!a || !b) [or: (a && b) == !(!a || !b)]

a b a&&b !(a&&b) !a !b (!a || !b)
0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0

The columns for !(a&&b) and (!a || !b) are identical, thus !(a&&b) == (!a || !b). QED.

6. What will the following code print out?
System.out.println(17 % 9 % 3);
System.out.println(5 * 8 % 30 / 3);

On line 1: % is left-to-right, (17 % 9 % 3) = ((17 % 9) % 3) = (8 % 3) = 2.
On line 2: all 3 ops are same precedence and left-right, so:
(5 * 8 % 30 / 3) = (40 % 30 / 3) = (10 / 3) = 3.
It prints out 2<newline>3<newline>.

7. For int’s x and y, write an equivalent expression to (x % y) that does not use the mod operator (%).

There are numerous correct answers. Here is one of them:

x/y truncates, and x/y*y is the largest multiple of y that is closer to 0 than x (I say it that way rather than “less than” since this way holds true also for negative x values).

But (x % y) is the amount left over after we subtract out exactly the value just described.

Hence: (x % y) = x - x/y*y

8. What will the following code print out? Write spaces as <space>.
int x = 7, y = 3;
double z = Math.pow(x/y,2);
while (x-- > ++y) z++;
System.out.printf("%2d%1.2f",y,z/x);

z = Math.pow(7/3,2) = Math.pow(2,2) = 4.0
The while loop proceeds as follows, where each row shows the values of x, y, and z before the while’s test is evaluated, what the test was, what the result was, and how the variables were set after the result and the body (z++) was executed:

before after
x y z test result x y z
7 3 4.0 7 > 4 true 6 4 5.0
6 4 5.0 6 > 5 true 5 5 6.0
5 5 6.0 5 > 6 false 4 6 6.0

So after the loop, x=4, y=6, and z=6.0, so z/x = 6.0/4 = 1.5.
Now, the %2d for y prints out the value 6 in a field of width 2: <space>6
And the %1.2f for z/x prints out the value 1.5 in a field of min-width 1 (which is irrelevant here) and with 2 digits after the decimal, or: 1.50
Putting these together, we get: <space>61.50

9. Write a snippet of Java code that demonstrates short-circuit evaluation.

There are many possible answers. Basically, use an && where the first argument is false, or use an || where the first argument is true. For example:

boolean x = (false && foo()); // method foo will never be called!

10. What does the following program print out?
class Foo {
public static int x = 0;
public static boolean foo() {
System.out.print("A");
return (++x < 3);
}
public static boolean foo(int x) {
System.out.print("B");
return (x > Foo.x);
}
public static void main(String[] args) {
int x = 4;
while (foo(x)) while (foo()) ;
}
}

Basically, this prints “B” ever time foo(x) is called, and “A” every time foo() is called.

Also, Note: each time the outer while loop evaluates to true (foo(x) returns true), we enter the outer while loop’s body, which is the inner while loop. We then run the inner while loop repeatedly until it returns false. Note that the inner while loop’s body is the null statement, so all it does is keep testing foo() until foo() returns false. Once the inner while loop is finished, we return to the outer while loop and keep looping in the outer while loop until its test (foo(x)) returns false.

Here is the call sequence, with the value of Foo.x both before and after each call:

before method after
Foo.x call prints evaluates to Foo.x
0 foo(4) B (4 > 0) == true 0
0 foo() A (1 < 3) == true 1
1 foo() A (2 < 3) == true 2
2 foo() A (3 < 3) == false 3
3 foo(4) B (4 > 3) == true 3
3 foo() A (4 < 3) == false 4
4 foo(4) B (4 > 4) == false 4

From this table, we see that the program prints out: BAAABAB.