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:

    • Does the file format start with a pre-defined header?
    • Does the file format use any kind of data compression scheme?
    • Name two different types of information that the file holds, and in what part of the file. For example, Windows bitmap files (in the version we examined) hold size information near the front of the file, and color information in the main (usually largest) part of the file.
    • What are the goals of the file format?

    Some possible examples: mp3, Microsoft Office formats, OpenOffice formats, JPEG, PNG, GIF, zip, gzip. Try to pick one you actually use, and one more obscure type. This Wikipedia article has a list of just about anything you could think of.

  7. Simple steganography: create a bitmap image that, when you view the underlying data, somehow displays a short message. For example, it says "Hello", or "Obviously you're not a golfer" when you view it as a text file. Hint: choose colors in a way that will insert ascii characters. Special prize if you can encode your entire homework assignment in a picture.