=================================================
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/