Contents

1. How many bits will we need to distinguish between 52 alternatives?

2. How many alternatives can we distinguish between using 14 bits?

3. If we add 4 bits to a binary representation, by how much (what factor) do we increase the number of alternatives we can distinguish?

For each of the following numbers in base 10, show their equivalents in each of the bases in the table:

Base 10	Base 2	Base 8	Base 16
173	______	______	______
152	______	______	______
111	______	______	______
63	______	______	______
64	______	______	______

Fill in the blank entries in this table with decimal and other equivalents:

Base 10	Base 2	Base 8	Base 16
______	______	______	7F
______	10101001	______	______
______	______	777	______

1. What fraction is 0.1101_bin in decimal?

2. What number does A.A_hex represent in decimal? How would you write it in binary?

3. the repeating expansion 0.3333 (etc.) represents one third in decimal; what repeating expansion represents one third in binary? Hint: in decimal, if we add 3 copies of 0.3333 (etc.), we get 0.9999 (etc.), which is equivalent to 1.

1. Assume that we represent floating point numbers using decimal representation with a sign bit for the magnitude (or mantissa), 8 digits for the magnitude itself, a sign bit for the exponent and 2 digits for the exponent itself. What are the largest (positive) and smallest (negative) numbers we can represent (assume that the mantissas have an implicit decimal point after the first digit). What is the difference between these two values?

2. Assume that we represent floating point numbers in binary using 16 bits: one sign bit for the magnitude (or mantissa), 8 bits for the magnitude itself, one sign bit for the exponent and 6 bits for the exponent itself. How many different possible floating point numbers can we represent?

1. Convert the numbers 234_dec and 172_dec into binary. Show how they added together in binary, making sure to indicate the "carries" at each point in the computation.

2. What is the largest number that might occur in a "carry" when adding:
   • two binary numbers?

   • two decimal numbers?

   • two hexadecimal numbers?

As a matter of fact, it turns out that the logarithms of 17, 27, 37 and 47 in bases 2 and 10 are as given in the following table. Note that the ratio of the base 2 and base 10 logarithms remains constant over the course of all these values.

n	log10(n)	log2(n)	Ratio
17	1.230449	4.087463	3.321928
27	1.431364	4.754888	3.321928
37	1.568202	5.209453	3.321928
47	1.672098	5.554589	3.321928

1. Use the results from above to compute the following: if a number requires 5 digits to represent in decimal, about how many binary digits will be needed to represent it?

2. What do you expect the value of log₁₆(n) / log₂(n) will be, for any n? Explain why.

One way to think about multiplication of a number n by a number m is that we are adding together m copies of n. On the other hand, if m is an even power of 2, we can just shift the binary representation of n left by log₂(m). For example, in order to multiply 37 by 8, we can just shift its binary representation left by 3 bits, since log₂(8) = 3.

But what if the number m is not an exact power of 2? Then perhaps we can break it down into a sum of two powers of 2. For example, since 24 = 8 + 16, if we want to multiply 37 by 24, we can add together two left-shifted versions of 37, since

		  37 * 24
		
		= 37 * (8+16)
		
		= (37*8) + (37*16)

On the other hand, some numbers are not even the sum of two powers of 2. But, it turns out that every number can be represented as a sum of powers of 2, since every number can be written in binary. We can use this fact to view the multiplication of two numbers as follows: write each number in binary. Use the bits of one number to control which "shifted copies" of the second number are added together: for each 1-bit in the first number, make a copy of the second number which is shifted left by as many places as that 1-bit sits left ward in the first number. Now add together all the shifted copies of the second number and this is the result of the multiplication.

Consider the following graphic illustrating the process:

Exercise: Show a similar calculation of 38 * 51.

Assume that a certain text uses only the 26 capital letters, plus spaces, commas, periods, parentheses, question marks and exclamation points. If the text can be written with 200 of these symbols, about how many bits will be required to write it out in a straight-forward manner? Justify your answer.