% Author: Ian! D. Allen - idallen@idallen.ca - www.idallen.com % Date: Fall 2011 - September to December 2011 - Updated 2011-11-04 23:49 EDT % Title: Week 08 Notes for CST8281 - Fall 2011 - [Course Home Page] - [Course Outline] - [All Weeks] - [Plain Text] Midterm Test #2 - 20% ====================== - 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.) Final Exam Schedule Posted ========================== - 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. Lecture Notes for This Week =========================== From the Class Notes link on the Course Home Page ------------------------------------------------- - [Course Home Page] - [All Weeks] ### Assignments - [Assignment #06] - midterm corrections. - [Assignment #07] - Floating Point, Endian, Shifts, Characters, Booleans - In class exercise. The `' '` character is an ASCII `SP` (space): - Give the ASCII characters and hexadecimal for these four equations: - `'A' + ' ' = '?' = 0x??` - `'A' | ' ' = '?' = 0x??` - `'a' + ' ' = '?' = 0x??` (this will not be ASCII - how can you tell?) - `'a' | ' ' = '?' = 0x??` From Blackboard Course Documents -------------------------------- These documents have restricted distribution and cannot be put on the [Course Home Page]. - [02.ppt] - Data Representation - Character encoding: ASCII, Unicode, Line Endings - [06.ppt][02.ppt] - Memory - see memory speeds on slide 7 - see memory types, memory hierarchy (speeds), cache, virtual memory - ignore slides 12-34, 37 - ignore anything on “segmentation” - focus on “paging” only - [03.ppt][02.ppt] - Boolean Algebra and Digital Logic - ignore Digital Logic and slides 19-73, 75-76 - Boolean Algebra From the Internet ----------------- - - - Bitwise Operators in Java - - - - see “Avoiding thrashing” - - - From the Classroom Whiteboard/Chalkboard ---------------------------------------- - Your in-class notes go here. - What you might need is a Binary Watch - see image. ![Binary Watch (photo courtesy of Lucas)] ### Boolean Algebra / Bitwise Operators - 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 - 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=z)` - rewrite `ab+ab' = a(b+b') = a(1) = a = (x 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 ### Memory, Cache, and Virtual Memory - 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 -- | 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 [Course Home Page]: .. [Course Outline]: course_outline.pdf [All Weeks]: indexcgi.cgi [Plain Text]: week08notes.txt [Test Instructions]: 000_test_instructions.html [Assignment #06]: assignment06.txt [Assignment #07]: assignment07.txt [02.ppt]: http://blackboard.algonquincollege.com/ [Binary Watch (photo courtesy of Lucas)]: binary_watch.jpg [Pandoc Markdown]: http://johnmacfarlane.net/pandoc/