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

Homework #2 (part 1)

Due: Mon 22-Jan-2007 as you enter class.

SOLUTIONS

1. Express -122 in 8-bit 2’s complement (that is, as a signed byte).

To do this, we find positive 122 in 8-bit binary and then negate it.

We learned two distinct ways to convert 122 to binary. First, we can repeatedly take out the largest remaining power of 2, as in:

122 = 64 + 58
= 64 + 32 + 26
= 64 + 32 + 16 + 10
= 64 + 32 + 16 + 8 + 2
Then we write the corresponding bits, including 0’s for the missing powers of 2
= 1 1 1 1 0 1 0₂ (the subscript 2 means “binary”)
Finally, we pad this to 8 bits to get:
122 = 0111 1010₂

Alternatively, we can repeatedly take the remainder when dividing by 2 to get the bits in reverse, as in:

122 % 2 = 0
122 / 2 = 61, 61 % 2 = 1
61 / 2 = 30, 30 % 2 = 0
30 / 2 = 15, 15 % 2 = 1
15 / 2 = 7, 7 % 2 = 1
7 / 2 = 3, 3 % 2 = 1
3 / 2 = 1, 1 % 2 = 1
1 / 2 = 0. Done.

Now we read the bits on the right from the bottom up to get: 122 = 111 1010₂, and then we pad out to 8 bits as above to get:
122 = 0111 1010₂

To find -122, we just negate this value by flipping the bits and adding 1:
122 = 0111 1010₂
flip = 1000 0101
+1
1000 0110 = -122

Check: Converting to hex, we have 1000 = 8 and 0110 = 4 + 2 = 6, so we can check our result with the following Java code:
System.out.println((byte)0x86);
And, indeed, this prints out -122.

2. For what value of x does ((byte) 137) == x) evaluate to true?

137 is larger than the largest signed byte value, which is 127, so this is an example of overflow.

Converting to binary (as above), 137 = 1000 1001 (unsigned). Actually, 137 is stored as an int at that point, so it is 32 bits, as such:
0000 0000 0000 0000 0000 0000 1000 10001

Now, when we cast 137 to a byte, we keep only the lowest 8 bits. So we get:
1000 1001. But these are now interpreted as signed bits. So this is a negative number. Which one? Well, we negate it to find out:

original: 1000 1001
flipped: 0111 0110
+1
negation: 0111 0111 = 0x77 = 7*16 + 7 = 119.

Since we negated the number to get 119, the answer is -119.

Check: The following prints “true”:
int x = -119;
System.out.println(((byte) 137) == x);

3. Convert 0xE3 to binary, octal, and decimal.

0xE = 14 = 8 + 4 + 2 = 1110₂
0x3 = 2 + 1 = 0011₂
So, 0xE3 = 1110 0011₂

For octal, it’s perhaps easiest to convert the binary to a multiple of 3, so 9 bits, then convert these in groups of 3 to octal:

0xE3 = 1110 0111 = 011 100 011 = 0343 (that’s 343₈)

Finally, 0xE3 = 14 * 16 + 3 = 227.

Check: The following prints out 227 three times:
System.out.println(0xE3);
System.out.println(0343);
System.out.println(Integer.valueOf("11100011",2));

4. Convert decimal 173 to binary, octal, and hexadecimal.

To hex: 173 = 10 * 16 + 13, so the digits are 10 (0xA) and 13 (0xD).
So: 173 = 0xAD.

Now, 0xA = 8 + 2 = 1010₂ and 0xD = 8 + 4 + 1 = 1101₂, so:
173 = 0xAD = 1010 1101₂.

Finally, we group the bits by 3 to convert to octal as such:
173 = 0xAD = 1010 1101 = 010 101 101 = 0255 (that’s 255₈).

Check: The following prints out 173 three times:
System.out.println(0xAD);
System.out.println(0255);
System.out.println(Integer.valueOf("10101101",2));

5. We know that (1 + 2 + 4 + 8 + ... + 2ⁿ) + 1 = 2⁽ⁿ⁺¹⁾. Rewrite this statement in binary (rather than decimal) and briefly explain why writing it this way makes it plainly true.

1 = 1
2 = 1 0
4 = 1 0 0
8 = 1 0 0 0
… …
2ⁿ = 1 0 0… 0 0 0 [ 1 followed by n 0’s ]
------------
sum= 1 1 1 1 1 1 1 [ (n+1) 1’s]
+ 1
------------
1 0 0 … 0 0 0 [ 1 followed by (n+1) 0’s ]
= 2⁽ⁿ⁺¹⁾

Powers of 2 in binary are a 1 followed by 0’s. Specifically, 2ⁿ is a 1 followed by n 0’s. So each addend in that (1 + 2 + 4 + 8 + ... + 2ⁿ) contributes a bit in the sum 1111…111. Adding 1 leads to the next power of 2, plainly. Any explanation like this will suffice.

6. In just a few words of plain English, assuming n and m are positive int’s, describe under what conditions x will be set to true in this code:
boolean x = (n / m * m == n);

This tests if m is a factor of n. That is, if (n % m == 0).

Consider: if m is not a factor of m, then n/m will truncate (it’s integer division, after all). Thus, n/m will be smaller than expected. When we multiply by m, we will get a result smaller than n. So, for m,n > 0, if m is not a factor of n, (n / m * m < n).

Now, if m is a factor of n, then n/m will equal an integer, so there is no truncation. Thus, when we multiply by m again, we will get n.

Check: The following code never says “Oh no!”:
for (int n=1; n<1000; n++)
for (int m=1; m<1000; m++) {
boolean x = (n / m * m == n);
boolean y = (n % m == 0);
if (x != y) System.out.println("Oh no!");
}

7. For what two values of byte b does (((byte)-b) == b)) evaluate to true?

0 should be readily apparent. For the other value, consider that we are asking when negative b equals b. This cannot be true in the general case! So we expect that this problem involves overflow, where math gets a bit wacky. Now, positive 127 (the largest byte) can be negated to -127, so that’s not it. But -128 (the smallest byte), when negated, should be +128, but that’s too big to fit in a byte! So what is -128 when negated:

-128 = 1000 0000 (in 8-bit two’s complement)
flipped = 0111 1111
+1
negated = 1000 0000 = -128
Bingo! Due to overflow, -(-128) == -128 if we’re dealing in signed bytes.

Now, to be very precise about what’s happening here: Java does not do math in signed bytes! So here is how the left-hand side is evaluated:
a) start with ((byte) –b)
b) evaluate b, which is -128, which is widened to an ‘int’, so we have ((byte) -(-128))
c) evaluate -(-128) to get +128, so now we have ((byte)128). The key is that 128 is still an ‘int’ here, and at this point it is positive (we have negated -128)
d) cast the 128 to a signed byte. This is where the overflow occurs!!! 128 is too large to fit in a signed byte, and it overflows to -128!
e) widen the signed byte -128 back to an ‘int’. Remember: Java does not do math in signed bytes. So to evaluate the equals, it must cast back to an ‘int’. Thus, the left hand side evaluates to the ‘int’ -128.

Now onto the right-hand-side:
a) evaluate b, which is -128.
b) widen the signed byte -128 to an ‘int’, producing the ‘int’ -128.

So at this point, both sides contain the ‘int’ value -128, and so yes, they are ==.

Check: The following code prints out -128 and 0:
for (int i=-128; i<=127; i++) {
byte b = (byte) i;
if (((byte)-b) == b)
System.out.println(b);
}

8. In Two’s Complement, the number 111…1 always represents what decimal number?

-1. To see this, we first see that +1 is always 000…0001. So to find -1, we negate this:

+1 = 000...0001
flipped = 111...1110
+1
-1 = 111...1111

Check: The following code prints out -1’s:

9. The following code will not loop forever. Very briefly, why not?

int x = 1;
while (x > 0) x++;

Overflow. Eventualy, x reaches the largest valid int, 2³¹-1. Then, we add one, and it overflows, actually becoming the smallest negative int, -2³¹. In any case, it is then negative, and so (x > 0) is false, and the loop breaks.

Check: Run the code Wait 5 or 10 seconds. Watch it halt.

10. What will the following code print out?
int a = 68, b = 3;
int x = a++ - --b;
System.out.printf("%c%c%3d",x,a,b);

In evaluating x, a is post-incremented, so 68 is used, and b is pre-decremented, so 2 is used. 68 – 2 equals 66. So after this line:
a = 69, which is ASCII E (A is 65, B is 66, C is 67, D is 68, E is 69)
b = 2
x = 66, which is ASCII B.
When we print these out, the %c means to cast to a char and print as ASCII, and the %3d says to print as an ‘int’ but to make the field 3 chars wide, so we get:

BE 2 (the underlines are spaces, so that’s ‘B’ ‘E’ ‘<space> <space> ‘2’)

Check: Run the code, watch it print BE 2.

11. What will the following code print out?
System.out.println(1 + '2' % 3 * 4);

You should know that % has the same precedence as *, and both are left-to-right, so the % comes first. ‘2’ is ASCII 50, so we get:

(1 + '2' % 3 * 4) = (1 + (50 % 3) * 4)
= (1 + 2 * 4)
= (1 + 8 )
= 9

Check: Run the code, watch it print 9.