Test your comprehsion of the material with these questions. Most of these come directly from examples in class. A great way to prepare for a test is for you to come up with your own questions and check your answers. You can practice doing this with some of my review questions below.
Note that in the case of yes/no questions, you should be able to justify your answer.
In general, being able to explain your reasoning is more important than simply stating an answer, which you could forget or accidentally get wrong.
- Write down a bit string having 6 bits. What number does this bit string represent in the following representation schemes?
- unsigned
- signed
- sign-magnitude
Practice this question with a bit string that starts with a 1, and a bit string that starts with a 0.
Answer: Let's try the bit string 100110. This is the binary code for:
- 32+4+2 = 38 in unsigned
- 38-64 = -26 in signed
- -(4+2) = -6 in sign-magnitude
Now let's look at a bit string that starts with 0. Consider 010101. This is the binary code for:
- 16+4+1 = 21 in unsigned
- 21 in signed (same as unsigned)
- 21 in sign-magnitude (same as unsigned)
- Pick a two digit number (integer). Determine the 8-bit representations for this number using the following representation schemes
- unsigned
- signed
- sign-magnitude
- BCD
Practice this question also with a two digit negative number.
Answer: Let's consider the number 59. If we write this number as a sum of powers of 2 (which we would get on our receipt if we shopped at the "binary store", we have 59 = 32+16+8+2+1.
- Unsigned = 00111011
- Signed = 00111011 (same as unsigned)
- Sign-magnitude = 00111011 (same as unsigned)
- BCD = (code for 5)(code for 9) = 0101 1001.
Now let's try -59.
- Unsigned is impossible.
- Signed = 11000101
- Sign-magnitude = 10111011
- BCD is impossible
- The single-precision floating-point representation is a method of representing real numbers. We allocate 8 bits for the exponent. Explain how we can determine the approximate bound for the largest possible (finite) number that we can represent, and the smallest positve number.
- How would your answers change if we had instead allocated 7 bits for the exponent? Would this be practical for scientific applications?
Answer: If we have 8 bits for the exponent, then we have about 2^8 = 256 possible values for the exponent. These exponents should be evenly divided between positive and negative exponents. Thus, the largest power of 2 we can use is about 2^128. It's more convenient to work using base 10, and since log 2 is about .301, we have 2^128 ~= 10^38. This is an approximate maximum value. Similarly, the smallest positive number will be the negative exponent: 10^-38.
If we had instead used 7 bits for the exponents, then we would start with about 128 possible exponents, with the largest possible exponent value about 64. Then, 2^64 is about 10^19. The most minuscule positive number would analogously be about 10^-19. The question asks us to consider if this would be practical for science. It would not, because in many applicatons in chemistry and physics we need to express values with larger exponents than 19 (and less than -19). Some famous examples are: Avogadro's number which uses 10^23, and the mass of an electron which is on the order of 10^-31 kg.
- This question features some approximate values for large powers of 2. These approximations will appear in brackets. You may find the question easier to grasp initially in terms of these approximate values than just the powers of 2.
Using the fact that the mantissa for a single-precision floating-point number has 23 bits:
- How many real numbers can be exactly represented between two consecutive powers of 2?
- Consider the real numbers that we can exactly represent between 8 and 16. How far apart are they?
- How far apart are the exact real numbers between 2^23 [8 million] and 2^24 [16 million]?
- How far apart are the exact real numbers between 2^24 [16 million] and 2^25 [32 million]?
- What does the answer to the previous question tell us about real number versus integer representation?
- Explain why a financial account balance should not be stored in this format. Illustrate the problem with a specific example.
Answer: Let's continue to use the approximation that 2^20 = 1 million
- 2^23 = 8 million
- The distance from 8 to 16 is 16 - 8 = 8. The 8 million numbers are spread out over the range of real numbers from 8 to 16, so the density is 8 million / 8 = 1 million per integer. Thus, the individual real numbers are 10^-6 (i.e. one one-millionth) apart.
- The distance from 8 million to 16 million is 8 million. The 8 million real numbers are spread out over a distance of 8 million, so the density is 8 million / 8 million = 1. Thus, the individual real numbers are 1 integer apart.
- This part is just like the previous two with different numbers plugged in. The density of the real numbers is (how many reals) / (distance between the extremes) = 8 million / 16 million. Thus, there is 1 real number for every 2 integers, so they are 2 units apart. In other words, the real numbers are restricted to being just the even integers. Odd integers now cannot be exactly represented.
- As a result of our calculations above, once you go past about 16 million, you begin to skip some integer values. In the comparable 32 bit integer representation schemes, they are able to represent consecutive values into the billions.
- Because the mantissa has 23 bits, we can only guarantee precision to one part in 8 million. This is about 7 significant figures of precision. For financial calculations, you need to be correct to the nearest .01. Thus, if you have an amount of money that is 7 orders of magnitude higher than .01 (which is 10^5 dollars or $100,000), you would not be able to represent it exactly. To make matters worse, every time you perform a real-number calculation, there is likely a tiny error present, and these errors can accumulate. As a result, it's more realistic to use double precision instead of single precision. Another solution is to store the dollars and cents as separate integer values to avoid any trouble with precision.
- The binary number 110.1001 equals what base-10 number? If we multiply this binary number by 4, what is the binary result?
Answer: 4 + 2 + (1/2) + (1/16) = 6-9/16 (i.e. six and nine-sixteenths) or 9.5625
If you multiply by 4, note that 4 = 2^2, so move the "." by 2 places to the right to obtain 11010.01.
- In what ways did typical computers of the 1980s differ from those of the 1950s? How do today's PCs differ from those of 20 years ago?
- If the ASCII code for 'A' is 65, what symbol has ASCII code 85?
Answser: 'A' is the first letter of the alphabet. If we add 20 to its ASCII code, we want the 21st letter, which is 'U'.
- The ASCII codes for 'a' and '0' (zero) are 97 and 48, respectively. What is the ASCII code for '3' ? What is the ASCII code for '6' ? The value '3' + '3' is the ASCII code for what letter? When you ask the computer for 3+3, how come it knows to give you 6 as the answer instead of a letter?
Answer: The ASCII code for '3' is '0' + 3 = 48+3 = 51. Similarly, the ASCII code for '6' is '0'+6 = 48 + 6 = 54.
'3' + '3' = 51+51 = 102. If 'a' = 97 then we want the letter which is (102-97=) 5 letters after 'a' which is 'a' + 5 = 'f'.
When we ask the computer to add 3+3, the machine can distinguish between numbers and text. It can tell we are entering numbers. But the machine needs to be told in advance to expect numerical rather than text input. This is why cells in Excel have a "format" that we can specify. Fortunately, in Excel by default if you enter something that looks like a number, Excel will automatically format it to be a number instead of text.
- Basic image properties:
- What does an image look like if we reduce its dynamic range too much? What if we reduce its resolution too much?
- How much memory does an image need if it uses a grayscale system with 16 possible shades of gray, and it measures 400 by 300 pixels?
- What are the dimensions of your computer's screen?
- Give example RGB codes for light green, medium green and dark green.
- When we use indexed color, we often express the R,G and B values in hexadecimal, and the values we can choose are 00, 33, 66, 99, cc and ff. What color is represented by the code #cc0000?
- Using indexed color and dithering, explain how we can approximate a background color close to the value #993355.
- Convert this arithmetic expression to postfix notation: (1+2) * (3+4).
Answer: 1 2 + 3 4 + *
- Suppose an XOR gate has two inputs x and y and an output z. If x = 1 and z = 1, is it possible for us to determine the value of y? If so, what is it?
- Practice this question with other logic gates, and other values of x and z.
- Consider a NAND gate with two inputs x and y and an output z. If x = y, then what can we conclude about z?
Answer: Note that NAND returns the opposite of AND. Consider x = y = 0. In this case, AND would output 0, so NAND outputs 1. If x = y = 1, then AND returns 0, so NAND returns 0. Putting these two cases together, we see that if x = y, then the output (z) of the gates is the opposite of the input. In other words, all we have created is a NOT gate.
- Suppose a machine does 8-bit signed integer arithmetic. Give an example of a computation that will result in overflow. Is underflow possible?
Answer: Note that the range of possible values is -128 to +127. We just need to pose a question whose correct answer is outside this range. For example, 100+100. Underflow is only possible in real-number arithmetic, not integer arithmetic.
- Draw finite automata that accept these sets of binary strings:
- strings containing 101
- strings ending in 101
- strings that start with 1 and end in 0
- strings of length 3
- Write regular expressions that describe these sets of strings:
- 5-letter words that start with T
- words of any length that start with T
- words containing the letter T
- words that contain the letter E and end with T
Answers:
- Suppose that a processor's speed is 2 GHz. Each instruction that executes
needs to undergo 5 stages, and each stage takes 1 cycle of CPU time. How
many instructions can we execute in 1 microsecond if the machine is:
- not pipelined?
- pipelined? (Assume pipeline initially empty & no stalls)