================================================= Assignment #03 - Review of Fundamentals ================================================= - Ian! D. Allen - idallen@idallen.ca - www.idallen.com 1. What is the date of your first midterm test? Thursday, October 7. *** Numeric Section *** 2. Generalize: For an N-bit word size, express as a formula using N as a power of two (i.e. using 2**N) what are the largest (most positive) and smallest (least positive) integers possible for: a) N-bit unsigned b) N-bit signed-magnitude c) N-bit one's complement d) N-bit two's complement Give two answers per data type: formulas for largest and smallest values a) N-bit unsigned Largest = (2**N) - 1 Smallest = 0 b) N-bit signed-magnitude Largest = + ( (2**(N-1)) - 1 ) Smallest = - ( (2**(N-1)) - 1 ) c) N-bit one's complement Largest = + ( (2**(N-1)) - 1 ) Smallest = - ( (2**(N-1)) - 1 ) d) N-bit two's complement Largest = + ( (2**(N-1)) - 1 ) Smallest = - ( (2**(N-1)) ) 3. Conversions from different bases and representations to decimal: a) Given the digits 101010(16), convert to decimal from base "16" = b) Given the digits 101010(10), convert to decimal from base "10" = c) Given the digits 101010(8), convert to decimal from base "8" = d) Given the digits 101010(2), convert to decimal from base "2" = e) Given the digits 101010(-2), convert to decimal from base "-2" = f) Given the digits 101010(2), convert to decimal from bias-127 = g) Given the digits 101010(2), convert to decimal from bias-63 = h) Given the digits 101010(2), convert to decimal from bias-31 = i) Given the digits 101010(2), convert to decimal from bias-16 = Reference: http://en.wikipedia.org/wiki/Signed_number_representations All of these just multiply out using powers of the given base. I'll do one example in full; generalize to the other bases. a) 101010(16) = 1048576 + 4096 + 16 = 1052688 decimal b) 101010(10) = 100000 + 1000 + 10 = 101010 decimal (identity!) c) 101010(8) = 32768 + 512 + 8 = 33288 decimal d) 101010(2) = 32 + 8 + 2 = 42 decimal e) Given the digits 101010(-2), convert to decimal from base "-2" = Successive powers of a negative base alternate in sign! -2^5 -2^4 -2^3 -2^2 -2^1 -2^0 -32 16 -8 4 -2 1 1 0 1 0 1 0 --------------------------------- -32 + 0 + -8 + 0 + -2 + 0 = -42 base 10 For all the bias (or "excess" notation) numbers, we first convert the binary pattern to unsigned decimal: 101010(2) = 42 decimal Then we subtract the bias: f) 101010(2), bias-127 = 42-127 = -85 decimal (same as IEEE 754 exponent) g) 101010(2), bias- 63 = 42- 63 = -21 h) 101010(2), bias- 31 = 42- 31 = 11 i) 101010(2), bias- 16 = 42- 16 = 26 4. Perform the following additions and subtractions in binary, assuming a 6 bit word. Show the Result value plus the values of the Zero, Sign, Carry, and Overflow flag values for each (five answers for each). 010001 101101 + 101111 - 101101 Result: 000000 000000 Zero: 1 Zero: 1 Sign: 0 Sign: 0 Carry: 1 Carry: 0 Ovflo: 0 Ovflo: 0 011010 011010 - 001111 + 001111 Result: 001011 101001 Zero: 0 Zero: 0 Sign: 0 Sign: 1 Carry: 0 Carry: 0 Ovflo: 0 Ovflo: 1 5. If possible, convert the following decimal values into 2's complement form, assuming a 12-bit word. Show your 12-bit results in hexadecimal: a. -513 = DFFh (see below) b. +513 = 201h (see below) c. -2 = FFEh (see below) d. -2048 = 800h (see below) e. 2048 = impossible (see below) f. -2049 = impossible (see below) We need the positive numbers converted before we do the negative numbers. b) +513 513(10) = ??? hex -> use powers-of-16 table: 1, 16, 256, 4096 513 / 256 = 2 rem 1 1 / 16 = 0 rem 1 1 / 1 = 1 rem 0 +513 = 201h = 0010 0000 0001(2) (or note that 513 = 512+1 = 2**9 + 1 = 1000000001(2) a) -513 -513 is negative so treat as positive and bit flip later +513(10) = 201h (from above) --> DFEh (flip the bits using hex bit-flip table) --> DFFh (add one for two's complement) -513 = DFFh = 1101 1111 1111(2) c): -2 -2 is negative, so treat as positive and bit flip later 2(10) = 002h as 12-bits hex --> FFDh (flip the bits using hex bit-flip table) --> FFEh (add one for two's complement) FFEh = 1111 1111 1110(2) (or - just remember that -1 is always "all bits on", and -2 is one bit different!) e) +2048 2048(10) = ??? hex -> use powers-of-16 table: 1, 16, 256, 4096 2048 / 256 = 8 rem 0 0 / 16 = 0 rem 0 0 / 1 = 0 rem 0 = 800h which is negative in 12 bits (sign bit is on)! --> 2048 is too big to fit in 12 bits two's complement --> max (using formula) is +((2**11)-1) = +2047 --> too big for 12 bits! d) -2048 -2048 is negative so treat as positive and bit flip later +2048(10) = 800h (from above) --> 7FFh (flip the bits using bit-flip table) --> 800h (add one for two's complement) -2048 = 800h = 1000 0000 0000(2) (or - just remember that the most negative number has the sign bit on and nothing else in two's complement) --> this is the most negative number we can have in 12 bits f) -2049 -2049 is negative so treat as positive and bit flip later +2049(10) = 801h (from above, just add one) --> 7FEh (flip the bits using bit-flip table) --> 7FFh (add one for two's complement) --> but 7FF is a positive number (sign bit off)! --> doesn't fit in 12 bits (use the formula to confirm this) --> most negative (using formula) is -(2**11) = -2048 --> too negative for 12 bits! 6. Perform the indicated arithmetic in hexadecimal, assuming a 12-bit word. Show the 12-bit hexadecimal result plus the ON/OFF states of the Zero, Sign, Carry and Overflow flags (five answers for each problem). D66 95A C38 ADF +29A -347 +88B -BCD Result: 000 613 4C3 F12 Zero: ON OFF OFF OFF Sign: OFF OFF OFF ON Carry: ON OFF ON ON Ovflo: OFF OFF ON OFF 7. Unix/Linux has traditionally used a 32-bit signed integer to store the number of seconds since midnight on January 1, 1970, UTC. Calculate roughly in what year/month/day this value overflows and time starts going negative. (Assume that a year is 365.25 days.) 32 bits signed means the max positive seconds is +((2**31)-1) or 2,147,483,647 seconds. A year is about 365.25 days or 31,557,600 seconds. 2,147,483,647 / 31,557,600 = 68.049650385 years. year 1970 + 68 = year 2038 The remainder 0.049650385 years is about 18.134803121 days. January 1 + 18 = January 19 (2038) A Wikipedia search confirms the actual date as 03:14:07 UTC on Tuesday, 19 January 2038: http://en.wikipedia.org/wiki/Year_2038_problem 8. Express floating-point 123.4567 as a normalized decimal number using scientific notation with five digits of precision. Normalized: 1.234567 x 10**2 Five digits: 1.2345 x 10**2 (or 1.2346 with rounding) In program code, write this as: 1.2345e2 (1.2345 times 10**2) 9. Add floating-point decimal 4321000.0 to 3.9 and express the result as a normalized decimal number using scientific notation with five digits of precision. 4321000.0 + 3.9 = 4321003.9 Normalized: 4.3210039 x 10**6 Five digits: 4.3210 x 10**6 Note that the original number 4321000.0 is also 4.3210 x 10**6 10. Add *binary* floating-point 1011000.0 to 1.1 and express the result as a normalized binary number using (binary) scientific notation with five (binary) digits of precision. 1011000.0 + 1.1 = 1011001.1 Normalized: 1.0110011 x 2**6 Five digits: 1.0110 x 2**6 Note that the original number 1011000.0 is also 1.0110 x 2**6 11. Looking at the two previous questions, is it possible in a computer to add a small floating-point number to a larger floating-point number without having any effect, i.e. is it true that A+B=B for certain floating-point values where A is much smaller than B? Yes. Both previous questions show cases where A+B=A when A is big and B is small. Because the number of bits of precision is fixed in ordinary floating-point arithmetic inside a computer, there will be some arithmetic that will not have enough precision to represent the true answer. Adding two values of greatly differing magnitudes (e.g. add 3 to 10**99) usually leaves the larger number unchanged, because there are not enough bits of precision to represent the small number being added to it. 12. What is floating-point underflow? Any number that is "too close to zero" to be represented. In IEEE-754 single-precision, numbers closer to zero than about 10**(-38) fall into this "zero hole". (You can actually get numbers smaller than this, using de-normalized floating point - see the notes for details.) 13. Give an example of a number that would cause floating-point underflow if you tried to calculate it or represent it using IEEE-754 single-precision floating-point. Anything closer to zero than 10**(-38), e.g. 10**(-100) 14. Why must you never test floating-point numbers for equality, i.e. why is "if ( x == y )" a bad idea for floating point x and y? Due to errors in precision, floating-point numbers may not achieve exact equality. They may be extremely close together, but not equal. Since you already accept some error when using floating-point numbers, comparison for exact equality makes no sense. The comparisons must be done to with some tolerance, or "epsilon", that you choose depending on your application. 15. What is the correct way to test for floating-point "equality"? Decide how close the numbers should be to be considered equal. Call this small difference value "epsilon". Then use: IF ( abs(a - b) < epsilon ) THEN consider a and b are "equal" where a and b are being compared and epsilon is a small number, e.g. 1.0e-9 16. Write a tiny program fragment (any language, or pseudocode) that uses a floating point loop that starts at 1000.0, adds 0.1 each time through the loop, and stops when the loop counter is within 1.0e-7 ("epsilon") of the floating-point value 2000.0. Give the code for the loop here: /* unreadable method: */ for( counter=1000.0; abs(counter-2000.0) >= 1.0e-7; counter += 0.1 ){ } /* better method (based on code from Chad) */ float numA = 1000.0; float targetNum = 2000.0; float eps = 1.0e-7; while (abs(targetNum - numA) > eps ) { numA += 0.1; } *** Character Section *** 17. Find a hexadecimal table of ASCII characters and translate this string of hexadecimal bytes into ASCII characters: (For unprintable characters, give the ASCII names of the characters, e.g. 07h is the ASCII "BEL" character) 50 65 6e 67 75 69 6e 73 20 41 72 65 20 46 52 45 45 0a 0d P e n g u i n s SP A r e SP F R E E NL CR 18. In ASCII, which comes first (i.e. has lower hex values): upper-case letters or lower-case letters? Upper-case letters have smaller hex values than lower-case; they come first. 19. There is only one bit of difference between an upper-case ASCII character and its lower-case equivalent. What is the hexadecimal and decimal value of this bit? What ASCII character does this bit value represent? 'A' = 0x41 and 'a' = 0x61, the difference is 0x20 (32 decimal) which happens to be the ASCII code for a space (SP). You sometimes see this math in programs that turn upper-case to lower case: read char; char = char | ' '; print char; What does this code do if it reads text that is already lower case? 20. What values (in hexadecimal) result from the following ASCII arithmetic (characters in single quotes are ASCII chars; character ' ' is SPACE): a) 'B' + 1 = 42h+1 = 43h = 'C' b) 'C' - 1 = 43h-1 = 42h = 'B' c) 'D' + ' ' = 44h+20h = 64h = 'd' d) 'q' - 'Q' = 71h-51h = 20h = ' ' (SP = space) e) '8' - '0' = 38h-30h = 08h = BS (backspace [unprintable]) Now, express each of the above hex values as an ASCII printable character, if the hex value is printable. If not printable, look up the value in an ASCII table and give its ASCII character name (e.g. hex 07h is the "BEL" character that rings the terminal bell). 21. How do the ASCII character set and the Unicode character set relate to each other? The first 128 characters of Unicode are ASCII, but in 16-bit form. 'A' = 41h in ASCII (7-bit characters) 'A' = 0041h in Unicode (16-bit characters) 22. What is the default character set used in the Java language? http://www.exampledepot.com/egs/java.nio.charset/ConvertChar.html "Java's native character encoding is Unicode." http://publib.boulder.ibm.com/infocenter/iseries/v5r3/index.jsp?topic=/rzaha/charenc.htm "Internally, the Java(TM) virtual machine (JVM) always operates with data in Unicode." 23. True/False: Plain English text, encoded as ASCII, is identical to the same Plain English text encoded as Latin-1. True - Latin-1 only adds characters with values higher than ASCII, i.e. values above 0x7F (above 127 decimal). 24. True/False: French text, encoded as Latin-1, is identical to the same French text encoded as ASCII. (Trick question.) You can't encode French in ASCII; you don't have any of the accents. False. 25. True/False: Plain English text, encoded as ASCII, is identical to the same Plain English text encoded as Unicode. False. ASCII is a 7-bit character usually stored in an 8-bit byte. Unicode is a 16-bit character. English encoded as ASCII is one-byte-per-character. English encoded as Unicode is two-bytes-per-character (though the numeric values of the one byte and the two bytes will be identical, e.g. 'A' = 41h and 0041h). 26. If you sort a file containing lines of mixed-case ASCII text, what is the resulting order relationship of lines that begin with upper-case letters and lines that begin with lower-case letters? In other words - which lines sort first in the file? See Q18 above. All lines starting with upper-case ASCII will sort before lines with lower-case ASCII. 27. Which file is smaller - Plain English text encoded as Latin-1 or Plain English text encoded as Unicode? See Q25 above. A Unicode file will be double the size of the ASCII file, since every Unicode character takes twice the space. 28. Why can't a single text file contain both French, encoded as 8-bit Latin-1, and Polish, encoded as 8-bit Latin-2? If all 258 8-bit codes are used for French, there are no codes left over for Polish. French and Polish use the same 256 numbers; they just interpret them differently. A file can only be interpreted as either Latin-1 or Latin-2, not both at the same time. 29. Without decoding using any ASCII table, explain why the following sequence of hexadecimal bytes is or is not likely to be from an ASCII text file: c4 05 fe fc d2 c7 34 24 08 05 00 00 00 31 f6 c7 This is not ASCII. Many bytes above are either 8-bit characters (e.g. c4, fe) or are unprintable characters (values less than 0x20 such as 05 and 08). ASCII text contains 7-bit printable characters in the range 20h to 7Eh. *** Boolean Section *** Recall that "NOT x" can be written in text using the "prime" mark: x' 30. True/False: (ab)' == a'b' In English: "NOT(sweet AND sour) == NOT sweet AND NOT sour" ? FALSE: (ab)' == a' + b' (deMorgan) 31. True/False: (a + b)' == a' + b' In English: "NOT(sweet OR sour) == NOT sweet OR NOT sour" ? FALSE: (a + b)' == a'b' (deMorgan) 32. Using deMorgan, write a simplified expression for the Boolean complement of the logic function F(x,y,z) = x'(y + z') F(x,y,z) = x'(y + z') : original F'(x,y,z) = ( x'(y + z') )' : complement = x'' + (y + z')' : deMorgan = x + (y + z')' : identity = x + y'z'' : deMorgan = x + y'z : identity 33. Using deMorgan, write a simplified expression for the Boolean complement of the logic function F(x,y,z) = x' + (yz') F(x,y,z) = x' + (yz') : original F'(x,y,z) = ( x' + (yz') )' : complement = x''(yz')' : deMorgan = x(yz')' : identity = x(y' + z'') : deMorgan = x(y' + z) : identity = xy' + xz : distribute (optional) 34. Show that a = ab' + ab using a Boolean truth table. a b ab' ab ab + ab' -------------------------------------------------- 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 0 1 1 The first column equals the last column. QED. 35. Prove that a = ab' + ab using a chain of simple Boolean Identities. ab' + ab = a(b' + b) : distribute = a(1) : identity = a : identity 36. Construct a Boolean function F(x,y) that implements the XOR operator using only AND, OR, and NOT logic. (The truth table for the simple Boolean function should be the same as the XOR truth table.) F(x,y) = x ^ y : this is XOR = xy' + yx' : Solution 1: using only AND, OR, and NOT = (x + y)(xy)' : Solution 2: using only AND, OR, and NOT 37. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "Call the ADD routine unless: the COST is not zero or the STATUS is not 'broken'." Note that "unless" means "IF NOT TRUE THAT". if ! ( COST != 0 || STATUS != broken ) call ADD : original if !(COST != 0) && !(STATUS != broken) call ADD : deMorgan if COST == 0 && STATUS == broken call ADD : complement 38. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "Call the UPDATE routine unless: the WORK is not less than zero and the SHAPE is not 'round'." Note that "unless" means "IF NOT TRUE THAT". if ! ( !(WORK < 0) && SHAPE != round ) call UPDATE : original if !!(WORK < 0) || !(SHAPE != round) call UPDATE : deMorgan if WORK < 0 || SHAPE == round call UPDATE : complement 39. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "A STALE sale is one where the DATE is greater than or equal to three years old and the COST is bigger than or equal to zero. If the sale is NOT STALE, call the SHIP routine." STALE = DATE >= 3 && COST >= 0 : original if ! STALE call SHIP : original ! STALE = ! ( DATE >= 3 && COST >= 0 ) : substitute ! STALE = !(DATE >= 3) || !(COST >= 0) : deMorgan ! STALE = DATE < 3 || COST < 0 : complement if DATE < 3 || COST < 0 call SHIP : substitute 40. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "In Narnia, you lose (cannot renew) your driving license if your age is 65 or more, or you have 23 or more demerit points. Call the renew() function if this is not true. (Write a simplified IF statement that calls renew() if you are allowed to renew.)" LOSE = AGE >= 65 || POINTS >= 23 : original if ! LOSE call renew() : original ! LOSE = ! ( AGE >= 65 || POINTS >= 23 ) : substitute ! LOSE = !(AGE >= 65) && !(POINTS >= 23) : deMorgan ! LOSE = AGE < 65 && POINTS < 23 : complement if AGE < 65 && POINTS < 23 call renew() : substitue -- | Ian! D. Allen - idallen@idallen.ca - Ottawa, Ontario, Canada | Home Page: http://idallen.com/ Contact Improv: http://contactimprov.ca/ | College professor (Free/Libre GNU+Linux) at: http://teaching.idallen.com/ | Defend digital freedom: http://eff.org/ and have fun: http://fools.ca/