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?
20 = 1 = 1 followed by 0 0’s
21 = 2 = 10 = 1 followed by 1 0’s
22 = 4 = 100 = 1 followed by 2 0’s
2n = 1 followed by n 0’s
40 = 1 = 1 followed by 0 0’s
41 = 4 = 100 = 1 followed by 2 0’s
42 = 16 = 10000 = 1 followed by 4 0’s
4n = 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 8th 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.