1 Midterm Test #2 - 20%Index

• The Second Midterm Test date is posted on the Course Home Page.
• In class on Wednesday, November 9. Short answer and multiple choice.
• For full mark credit, read the Test Instructions for important directions on how to enter your answers on the mark-sense forms.
• The Second Midterm covers material on Assignments 01 through 08 inclusive and Week Notes 01 through 09 inclusive.
• Basic calculators are permitted for this test and the final exam. (No phones or PDA devices.) You will not need one if you know your powers of two. You will benefit from knowing the powers of two from 2^(-4) to 2^16 and the decimal and binary values of the hexadecimal digits from zero to fifteen. Of course you can work them out; however, having at least some of them memorized will make things go faster for you on the test. (Remember that hexadecimal “A” = decimal 10 = binary 1010.)

2 Final Exam Schedule PostedIndex

• The Final Exam date is posted on the Course Home Page.
• For full mark credit, read the Test Instructions for important directions on how to enter your answers on the mark-sense forms.

3 Lecture Notes for This WeekIndex

3.4 From the Classroom Whiteboard/ChalkboardIndex

• Your in-class notes go here.

• What you might need is a Binary Watch - see image.

3.4.1 Boolean Algebra / Bitwise OperatorsIndex

• Shifting numbers right and left
  • shifiting effect on two’s complement numbers: does it work?
  • Arithmetic Right Shift vs. Logical Right Shift
    • duplicate the top (carry) bit for Arithmetic Right Shift
  • F4240h = 1,000,000(10)
    • so F42400h = 1,000,000 * 16 = 16,000,000
    • so F424h = 1,000,000/16 = 1000000 * 0.0625 = 100 * 625 = 62,500
  • 03641100(8) = 1,000,000(10)
    • so 036411000 = 1,000,000 * 8 = 8,000,000
  • 1010(2) = 10 decimal
    • so 101000(2) = 10 * 2 * 2 = 40 decimal
• Bitwise Operators AND, OR, XOR, NOT (in Java: & | ^ ~)
  • don’t confuse bitwise with logical: & with &&, | with ||, or ~ with !
  • if x=1, y=2 then x&y = 0 (no bits in common)
  • if x=6, y=12 then x&y = 4 (one bit in common)
  • XOR is Exclusive OR - A or B but not both
    • true OR true is true
    • true XOR true is false
  • if a=6,b=3 what is a&b? what is a|b? what is a^b? what is ~a?
  • if a=5,b=10 what is a&b? what is a|b? what is a^b? what is ~a?
• Note: All integer types in Java are signed (except char)!
  • see http://www.javamex.com/java_equivalents/unsigned.shtml
  • Java has a special unsigned (“logical”) right shift operator: >>>
  • need to use bit masking for unsigned arithmetic
• Conversions between upper/lower in ASCII using bitwise OR and AND:
  • 'A' | ' ' = 'a' (OR turns on the 20h bit, making it lower-case)
  • 'a' & ~' ' = 'A' (AND turns off the 20h bit, making it upper-case)
• ASCII parity bit, used to detect errors in data transmission
  • is ‘A’ even or odd parity? convert it to even parity, then to odd
  • is CR even or odd parity? convert it to even parity, then to odd
• Simplifying complex logic using Boolen Algebra - identities - deMorgan
  1. simplify: if ((x < y) && (y < z)) || ((x < y) && (y >=z ))
     • simplifies to just if (x < y) because:
     • let a = (x<y) and b = (y<z), therefore b' = (y>=z)
     • rewrite ab+ab' = a(b+b') = a(1) = a = (x<y)
  2. suppose a stale order means: date > 120 and amount > 0
     1. simplify: print unless stale
        • unless stale means if NOT stale
        • print if NOT (date > 120 && amt > 0)
        • using deMorgan: print if (date <= 120 || amt <= 0)
     2. simplify: print unless (stale and amt < 0)
        • print if NOT (stale && amt < 0)
        • print if ( !stale || amt >= 0)
        • print if ( date <= 120 || amt <= 0 || amt >= 0)
        • print if ( date <= 120 || TRUE )
        • therefore: always print (probably an error in the specifications!)
  3. Show that (xy + x'z + yz')' = y'(x+z')
     • (x'+y')(x+z')(y'+z) -- deMorgan
     • (x'x + x'z' + xy' + y'z')(y'+z) -- expand first two expressions
     • ( 0 + x'z' + xy' + y'z')(y'+z) -- identities
     • x'y'z' + x'z'z + xy'y' + xy'z + y'y'z' + y'z'z -- expand again
     • x'y'z' + 0 + xy' + xy'z + y'z' + 0 -- identities
     • x'y'z' + y'z' + xy' + xy'z -- regroup similar terms
     • y'z' + xy' -- absorption rule
     • y'(x+z') -- QED

3.4.2 Memory, Cache, and Virtual MemoryIndex

• cache (from 06.ppt)
  • what is the purpose of cache memory?
  • how does the size of cache memory affect your programs?
• virtual memory (from 06.ppt)
  • allows CPU to execute programs larger than physical memory
  • one more level of indirection between the program and the memory
  • program (virtual, logical) address - what the program uses
  • memory (physical, real) address - what gets to the memory
  • program has virtual pages (or just “pages”)
  • memory has physical page frames (or just “frames”)
  • page table, valid bit, page faults
  • working set, thrashing

Author: 
| 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/

Plain Text - plain text version of this page in Pandoc Markdown format