## Homework 1 solutions

02 Oct 2011
1. What are the decimal and binary equivalents of the following hexadecimal numbers?

• 0xFF

0xFF = (largest 2-digit hexadecimal number) = (largest number that fits in 1 byte)
= (2^8 - 1) = 255 (base 10) = 11111111 (base 2)

• 0x80

0x80 = 16 × 8 + 1 × 0 = 128 (base 10) = 2^7 (base 10) = 10000000 (base 2)

• 0x101

0x101 = 16^2 × 1 + 16 × 0 + 1 × 1 = 257 (base 10) = 100000001 (base 2)

2. Write a truth table for the following expressions. Give a plain English description of what each expression means (some descriptions will be simpler than others).

• (A & B) | (B & C) | (A & C)

A B C  (A & B) | (B & C) | (A & C)
----------------------------------
0 0 0  0
0 0 1  0
0 1 0  0
0 1 1  1
1 0 0  0
1 0 1  1
1 1 0  1
1 1 1  1

"At least 2 of A, B, or C are true"

• (X & Y) | (!X & Y)

X Y  (X & Y) | (!X & Y)
-----------------------
0 0  0
0 1  1
1 0  0
1 1  1

"Y is true"

• (P & Q) | (P & R)

P Q R  (P & Q) | (P & R)
------------------------
0 0 0  0
0 0 1  0
0 1 0  0
0 1 1  0
1 0 0  0
1 0 1  1
1 1 0  1
1 1 1  1

• P & (Q | R)

P Q R  P & (Q | R)
------------------------
0 0 0  0
0 0 1  0
0 1 0  0
0 1 1  0
1 0 0  0
1 0 1  1
1 1 0  1
1 1 1  1

"P is true and either Q or R is true" (note: same as last expression)

3. If 10 + 30 = 100, what base are we working in?

4, because 1 + 3 = 10.

4. Write down the binary multiplication table for the numbers 0 through 4.

<td></td><td>0</td><td>1</td><td>10</td><td>11</td><td>100</td>

<td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td>

<td>1</td><td>0</td><td>1</td><td>10</td><td>11</td><td>100</td>

<td>10</td><td>0</td><td>10</td><td>100</td><td>110</td><td>1000</td>

<td>11</td><td>0</td><td>11</td><td>110</td><td>1001</td><td>1100</td>

<td>100</td><td>0</td><td>100</td><td>1000</td><td>1100</td><td>10000</td>


Notice how the lines and columns for 10 and 100 are all just adding one or two zeros to end of the other number (just like 10 and 100 in decimal).

5. How is the expression x & (x - 1) related to x? Hint: think in binary, and try examples until you see a pattern. You can assume x > 1.

Some examples:

• x = 1: x & (x - 1) = 1 & 0 = 0
• x = 10: x & (x - 1) = 10 & 01 = 0
• x = 101: x & (x - 1) = 101 & 100 = 100
• x = 111: x & (x - 1) = 111 & 110 = 110
• x = 1101: x & (x - 1) = 1101 & 1100 = 1100
• x = 1100: x & (x - 1) = 1100 & 1011 = 1000

See the pattern? In terms of bits, this operation takes x and sets the righmost 1 bit to 0. This is because the subtraction operation always sets the rightmost 1 bit of x to 0, and because it's the rightmost, it doesn't matter what the bits in x - 1 further to the right look like once we perform the & operation.

6. Pick two file formats (other than those we've discussed in detail already), and research them. Answer the following questions: