# Homework 2: binary logic

Update: answers posted below each problem.

Due: Thursday September 20, 11:59PM. (Note the updated due date.)

To submit: Send an email to me at jal2016@email.vccs.edu with subject CSC 110 HW2 that contains your answers, and any attachments required.

Note: this assignment may be updated sometime before week 3's class.

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

• 0xFF

11111111. F is the largest single-digit hexadecimal number, and each hex digit can represent exactly 4 binary digits -- and the largest 4-digit binary number is 1111.

• 0x80

10000000. Remember that we can examine each hex digit separately, and 8 in hex (or decimal) is 1000 in binary.

• 0x101

100000001.

• 0x99

10011001.

2. What are the hexadecimal equivalents of the following binary numbers?

• 10000000

0x80

• 11110000

0xF0

• 00001111

0x0F

• 11111111

0xFF

• 10101010

0xAA

3. 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

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

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

1

0

0

0

0

0

0

1

1

0

1

0

1

1

0

0

0

0

0

0

1

0

1

0

0

1

1

1

1

0

1

0

0

1

1

1

1

1

1

1

1

The expression is true if any 2 of A, B, or C are true.

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

X

Y

X & Y

!X & Y

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

0

0

0

0

0

0

1

0

1

1

1

0

0

0

0

1

1

1

0

1

The expression is true if Y is true. In other words (or symbols, rather), (X & Y) | (!X & Y) = Y.

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

P

Q

R

P & Q

P & R

(P & Q) | (P & R)

0

0

0

0

0

0

0

0

1

0

0

0

0

1

0

0

0

0

0

1

1

0

0

0

1

0

0

0

0

0

1

0

1

0

1

1

1

1

0

1

0

1

1

1

1

1

1

1

The expression is true if P is true and at least one of Q or R is true.

• P & (Q | R)

P

Q

R

Q | R

P & (Q | R)

0

0

0

0

0

0

0

1

1

0

0

1

0

1

0

0

1

1

1

0

1

0

0

0

0

1

0

1

1

1

1

1

0

1

1

1

1

1

1

1

The expression is true if P is true and at least one of Q or R is true. Note that the truth table is the same as the previous expression (so the expressions are equivalent: P & (Q | R) = (P & Q) | (P & R)). This can be derived algebraically, using a distributive law similar to the one used with multiplication and addition.

1. If 10 + 30 = 100, what base are we working in? What are the possible bases if 10 + 30 = 40 (hint: there are more than 1)?

If 10 + 30 = 100, then the base must be at least 4, since lower bases don't have symbols for 3 or above. And in base 4, it is true that 10 + 30 = 100 (we really just need to notice that in base 4, 1 + 3 = 10).

Base 4 is the only base that works, since if the base is 5 or higher, 1 + 3 = 4. That tells us the answer to the second question: if 10 + 30 = 40, then the base could be 5, 6, 7, or any higher number.

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

*

000

001

010

011

100

000

000

000

000

000

000

001

000

001

010

011

100

010

000

010

100

110

1000

011

000

011

110

1001

1100

100

000

100

1000

1100

10000

3. Write down the value of x & (x - 1) for x from 0001 to 1111 (working in binary). How is the expression x & (x - 1) related to x?

x

x - 1

x & (x - 1)

0001

0000

0000

0010

0001

0000

0011

0010

0010

0100

0011

0000

0101

0100

0100

0110

0101

0100

0111

0110

0110

1000

0111

0000

1001

1000

1000

1010

1001

1000

1011

1010

1010

1100

1011

1000

1101

1100

1100

1110

1101

1100

1111

1110

1110

In each row, the resulting value can be obtained from x by setting the rightmost bit to 0.

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