====================================================== Assignment #08 - Bitwise, Boolean, Memory (cache, virtual) ====================================================== - Ian! D. Allen - idallen@idallen.ca - www.idallen.com Read *all* the words in this assignment. Goal: Demonstrate mastery of bitwise and boolean operations. Demonstrate understanding of virtual memory paging. Available online: Wednesday November 2, 2011 Deliverables: One correctly-named plain text file uploaded to Blackboard. Upload due date: Upload answer file before 10:00 (10am) on Saturday November 12, 2011 Late assignments or wrong file names may or may not be marked. Answers will be posted shortly after the due date/time and discussed in class, if there are any questions about the answers. Submission method: Create a plain text file using the *exact* name: assignment08.txt Upload the file via the Assignment08 "Upload File" facility in Blackboard. Use "Attach File" and "Submit" to upload your plain text file. No wordprocessor documents. Do not send email. Use only "Attach File". Use the *exact* file name given above. Upload only one single file of plain text, not HTML, not MSWord. No fonts, no word-processing. Plain text only. Did I mention that the format is plain text (VIM/Nano/Pico/Gedit or Notepad)? NO WORD PROCESSOR, PDF, RTF, or HTML DOCUMENTS ACCEPTED. No marks are awarded for submitting under the wrong assignment number. Not all assignments will be marked. See the Week 1 Notes for details. Answers will be posted after the due date/time so that you can check your answers before coming to class and ask questions about the answers in class. Please check your answers (and my answers!). I go over each assignment in class if there are questions about the answers. No questions means no review - I'll presume you know the material. Questions similar to ones on these assignments will appear on your tests and exams. DO THIS: Edit this file and answer the following questions underneath each question, showing the method or formula you used to get the answer. Many of the questions already give you the answer - you must show the full method you use to generate that answer. Upload the file containing the question, methods, formulas, and answers before the due date. Some of the answers below will require reading the links published in the weekly course notes. Full marks are awarded only if you show your method, the same method you will have to use on your midterm test and final exam. Marks are awarded for original work, not for cut-and-paste. Any answers that are found to be cut-and-paste from some other document will require you to resubmit the entire lab as hand-written (and may result in a charge of plagiarism or academic fraud as well). Do your own thinking; write your own answers. ============================================================================== 1. What is the date for your Second Midterm Test? You may use a simple calculator on your Second Midterm Test. No phones or PDA devices. You will not need a calculator; the math will be simple powers of two. 2. What is the date, time, and room number of your Final Exam? *** Bitwise Operators Section: AND OR XOR NOT *** 3. For eight-bit numbers x=66h and y=3Ch give answers in binary and hex: a) What is x|y? _________(2) = ___________h ? b) What is x&y? _________(2) = ___________h ? c) What is x^y? _________(2) = ___________h ? d) What is ~y? _________(2) = ___________h ? e) What is ~x? _________(2) = ___________h ? 4. For any value x, what is the bit pattern that results from x | ~x ? 5. For any value x, what is the bit pattern that results from x^x ? 6. For any values x and y, explain what happens after the following two sequential XOR operations, e.g. try x=5,y=10 (or other values) and see what happens to x after you do these two XOR operations in this order: x = x^y x = x^y How has x changed after each of the above two operations? Does this result depend on the values of x and y? 7. For any values x and y, explain what happens after the following three sequential XOR operations, e.g. try x=5,y=10 (or other values) and see what happens to x and y after you do these three XOR operations in this order: x = x^y y = x^y x = x^y How have x and y changed after the above three operations? Does this result depend on the values of x and y? 8. Java integers (including constants) are 32 bits. Give the values of "i" in 32-bit hexadecimal after each of these Java statements: ( Hint: 0 = 00000000h as 32-bit hexadecimal ) int i = 0xF0 | 0xF000; i = 0000F0F0h a) int i = ~0x80000000; i = _________________h ? b) int i = ~0x12345678; i = _________________h ? c) int i = ~1; i = _________________h ? d) int i = ~0; i = _________________h ? e) int i = ~0xF; i = _________________h ? f) int i = ~0xFFFF; i = _________________h ? g) int i = ~0xFFFFFFFF; i = _________________h ? Hint: Make sure you operate on all 32 bits in every line above. *** Boolean Section - see 03.ppt *** 9. What is the opposite (the inverse of, the "NOT" of) these conditions: if ( i != 0 ) ? opposite: if ( i == 0 ) a) if ( i > 0 ) ? opposite: _____________________ ? b) if ( i < 0 ) ? opposite: _____________________ ? 10. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "Call the add routine unless: the cost is greater than zero or the colour is 'tan'." Note that "unless X" means "IF NOT X" (the logical complement). 11. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "In Gondor, you lose (cannot renew) your driving license if your age is 32 or older or you have more than 40 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.)" 12. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "In Shire, you lose (cannot renew) your driving license if your age is more than 40, or you have 11 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.)" 13. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "A purchase is classified as "stale" if the price is $50 or more and the invoice is 80 days or more. Call the classify routine if the size is 10 or more litres and the order is not stale." 14. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "An order is classified as "priority" if the cost is more than $10 or the invoice is less than 90 days. Call the notify routine if the cost is more than $10 and the order is not priority." Find the bug in the above logic. What is wrong? As a programmer, what would you tell your boss about this specification? 15. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "Call the DEL routine unless: the COST is not zero or the STATUS is not 'first'." Note that "unless X" means "IF NOT X" (the logical complement). 16. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "Call the UPDATE routine unless: the COST is less than zero and the TYPE is not 'oval'." Note that "unless X" means "IF NOT X" (the logical complement). 17. 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 four years old and the COST is bigger than or equal to one. If the sale is NOT STALE, call the SEND routine." *** Miscellaneous Section *** 18. Define the term "word" as it is used in computer architecture. [See Wikipedia: Word (computing)] 19. Put an "X" beside all the 32-bit sign/magnitude negative numbers: 600A3B65h 900000E2h AA0000EFh B9000037h F000675Ah E9900000h 200A7654h 20. The IEEE 754 floating-point number 6EDCBA89h is positive. Without converting, give the hexadecimal for the same number, only negative. 21. Without converting, put an "X" beside all the IEEE 754 negative numbers: 600A3B65h 900000E2h AA0000EFh B9000037h F000765Ah 200A7654h E9900000h 22. The following hexadecimal memory dump contains two big-endian four-byte two's-complement integers, starting at address 101. What decimal values do these two big-endian four-byte integers have? ADDRESS: ---------- MEMORY BYTES ---------- 100: 00 01 DF 5E 86 FE 20 A1 7A 00 00 11 13 02 00 4F 3A F1 ... 23. The following hexadecimal memory dump contains two little-endian four-byte two's-complement integers, starting at address 102. What decimal values do these two little-endian four-byte integers have? ADDRESS: ---------- MEMORY BYTES ---------- 100: FF 01 DE 5E 86 FE 20 A1 79 61 62 63 64 FF C4 F4 A3 1F ... 24. The following is a partial hexadecimal memory dump of the boot sector of an MS-DOS disk (MS-DOS means an Intel-based PC - what byte order?): 0000: EB 3C 90 4D 53 44 4F 53 35 2E 30 00 02 04 01 00 0010: 02 00 04 00 00 F8 F6 00 13 00 20 00 11 00 00 00 Read the above dump and give the hexadecimal and decimal values of the following unsigned integer items of different widths (sizes in bytes). The size of the integer is to the right of the offset, separated by a slash. The name of the item is also given below. Offset/Size: type of item: value in hex, value in decimal ----------- ------------------------------------------------ 000Bh/2: bytes per sector: 00 02 -> 0200h = 512 decimal a) 000Dh/1: sectors per allocation unit (cluster): ____________? b) 0010h/1: number of copies of FAT: ____________? c) 0011h/2: number of root directory entries: ____________? d) 0016h/2: number of sectors per FAT: ____________? e) 0018h/2: number of sectors per track: ____________? f) 001Ah/2: number of heads: ____________? 25. Looking at the previous question, note the size of each integer (in bytes) and answer these questions (all integers are unsigned): a) What is the maximum number of root directory entries possible? b) What is the maximum number of sectors per allocation unit possible? 26. The eight-character ASCII text string "12345678" is stored in memory starting at location zero. (These are eight ASCII characters.) See http://easycalculation.com/hex-converter.php a) Give the eight hexadecimal character bytes as stored in memory: b) Interpret these eight bytes as two 32-bit two's complement integers in little-endian form and give their two decimal values: c) Interpret these eight bytes as four 16-bit two's complement integers in big-endian form and give their four decimal values: d) Add one to each of the four big-endian integers from (c) and give the resulting changed ASCII text string (eight ASCII characters): *** Computer Basics Section - see 01.ppt *** 27. What is the modern version of Moore's Law? 28. Why can't Moore's law continue indefinitely? 29. What is the "von Neumann bottleneck"? 30. What are some ways to work around the "von Neumann bottleneck"? *** Memory Section - see 06.ppt *** 31. Cache memory is faster than main memory. Why not make all the memory in the computer cache memory? 32. Expand these acronyms into words: RAM, ROM, PROM, EPROM, EEPROM, ROTFL 33. Is the BIOS in your computer stored in RAM or ROM? 34. Put these in increasing order of access time (faster to slower) and indicate beside each type of device approximately what its access time is: Magnetic Tape Access time: Main Memory Access time: Level 2 Cache Access time: Optical Disk Access time: Registers Access time: Level 1 Cache Access time: Fixed Hard Disk Access time: 35. Define "a cache hit": 36. Define "a cache miss": 37. List and briefly describe the three Principles of Locality: 38. With reference to cache size, why is a small loop of code often faster than a large loop? 39. What is the basic feature that Virtual Memory enables? 40. What is the difference between a Physical Address and a Virtual Address? 41. What is a "page fault"? 42. How much slower (orders of magnitude) is a page fault compared to an ordinary memory access that does not cause a page fault? 43. With reference to virtual memory, why is a small program often faster than a large program? 44. What is virtual memory "thrashing"? 45. What is a "working set" for a program using virtual memory? 46. With reference to Chapter 6 Slides 46-47, describe what happens when the CPU generates the 13-bit Virtual Address 1FCCh: 47. The code that the operating system uses to service Page Faults cannot itself reside in Virtual Memory - it must always remain in actual Physical Memory. Why can't it be in Virtual Memory? Full marks are awarded only if you show your method, the same method you will have to use on tests and exams. Marks are awarded for original work, not for cut-and-paste. Any answers that are found to be cut-and-paste from some other document will require you to resubmit the entire lab as hand-written (and may result in a charge of plagiarism or academic fraud as well). Do your own thinking; write your own answers. -- | 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/