CS101 S12 - Quiz 1 Solutions

Using 7-bit signed (two’s complement) binary numbers, what is the largest positive number? What is the smallest negative number?

In 7-bit two’s complement, the values of the positions are:
```
____  ____  ____  ____  ____  ____  ____
 -64    32    16     8     4     2     1
```
So the largest positive number is 011 1111₂ which is +63₁₀. The smallest negative number is 100 0000₂ which is -64₁₀.
Convert the following 16-bit binary number into hexadecimal.

The trick is to split it into sections of 4 bits, starting from the right. The commas indicate these splits.
```
0 1 1 1,1 1 1 1,0 0 1 1,1 0 1 0
```
Then, each group of four translates to one hexadecimal digit:
```
0 1 1 1,1 1 1 1,0 0 1 1,1 0 1 0
- - - - - - - - - - - - - - - -
8 4 2 1 8 4 2 1 8 4 2 1 8 4 2 1   (values of each bit)
      7       F       3       A   (hexadecimal result)
```
Add and verify the following unsigned binary numbers.
```
1 1 1 1 1 1                      1     1
  1 0 1 1 1 1 = 47                 1 1 0 1 1 1 = 55
+ 0 1 1 1 0 1 = 29               + 1 0 0 1 0 0 = 36
——————————————                   ——————————————
1 0 0 1 1 0 0 = 76               1 0 1 1 0 1 1 = 91
```
Remember:
- Zero ones: answer is zero carry zero
- One one: answer is one carry zero
- Two ones: answer is zero carry one
- Three ones: answer is one carry one
Also, you should be sure to take the opportunity, in questions like this, to verify by converting to decimal and adding.
Suppose we need to send a text message uses 30 distinct characters. How many bits per character are required if we’re using a fixed encoding?

With 4 bits per character, we can have only 2⁴=16 characters. So the answer is 5 bits per character, because 2⁵=32. Six bits is too many: 2⁶=64.
Draw a binary tree that corresponds to the following encoding of four characters. The characters should appear in boxes at the leaves. Branch left on a zero, or right on a one.
```
T 00  
R 010 
N 011 
O 1   
```
Variable-width encoding tree
Use the character encoding from the previous question to decode the following word:
```
0 0,1,0 1 0,1,0 1 1,0 0,1
  T O     R O     N   T O
```