====================================================== Assignment #08 - Bitwise, Boolean, Z+S+C+O flags, LMC Computer ====================================================== - Ian! D. Allen - idallen@idallen.ca - www.idallen.com Available online: Wednesday March 9, 2011 Upload due date: Upload answer file before 23:59 (midnight) on Wednesday March 16, 2011 Answers will be posted shortly after the due date/time and discussed in class, if there are any questions about the answers. Late assignments may or may not be marked. 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 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 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. Some of the questions may 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 tests and exams. ============================================================================== 0. 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. *** Bitwise Operators Section: AND OR XOR NOT *** 1. For eight-bit numbers a=6Ch and b=36h give answers in binary and hex: a) What is a&b? _________(2) = ___________h ? b) What is a|b? _________(2) = ___________h ? c) What is a^b? _________(2) = ___________h ? d) What is ~a? _________(2) = ___________h ? e) What is ~b? _________(2) = ___________h ? 2. For any value a, what is the bit pattern that results from a^a ? 3. For any value a, what is the bit pattern that results from a | ~a ? 4. For any values a and b, explain what happens after the following two sequential XOR operations, e.g. try a=5,b=10 (or other values) and see what happens to a after you do these two XOR operations in this order: a = a^b a = a^b How has a changed after each of the above two operations? Does this result depend on the values of a and b? 5. For any values a and b, explain what happens after the following three sequential XOR operations, e.g. try a=5,b=10 (or other values) and see what happens to a and b after you do these three XOR operations in this order: a = a^b b = a^b a = a^b How have a and b changed after the above three operations? Does this result depend on the values of a and b? 6. Java integers (including constants) are 32 bits. Give the values of "x" in 32-bit hexadecimal after each of these Java statements: ( Hint: 0 = 00000000h as 32-bit hexadecimal ) int x = 0xF | 0xF00; x = 00000F0Fh a) int x = ~0; x = _________________h ? b) int x = ~1; x = _________________h ? c) int x = ~0xF; x = _________________h ? d) int x = ~0xFFFF; x = _________________h ? e) int x = ~0xFFFFFFFF; x = _________________h ? f) int x = ~0x11111111; x = _________________h ? g) int x = ~0x80000000; x = _________________h ? *** Boolean Section - see 03.ppt *** 7. What is the opposite (the inverse of, the "NOT" of) these conditions: if ( x == 0 ) ? opposite: if ( x != 0 ) a) if ( x < 0 ) ? opposite: _____________________ ? b) if ( x > 0 ) ? opposite: _____________________ ? 8. Using deMorgan, write a simplified expression for the Boolean complement of the logic function F(u,v,w) = u'(v + w') 9. Using deMorgan, write a simplified expression for the Boolean complement of the logic function F(u,v,w) = u' + (vw') 10. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "Call the add routine unless: the cost is less than zero or the colour is 'red'." 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 MiddleEarth, you lose (cannot renew) your driving license if your age is over 40 or you have 32 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.)" 12. 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 50 or more, or you have more than 11 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: "An order is classified as "overdue" if the cost is more than $10 and the time is more than 90 days. Call the inventory routine if the size is bigger than 10 litres and the order is not overdue." 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 time 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 'final'." 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 not 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 zero. 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: 2007A654h 600A3B65h 900000E2h AA0000EFh B9000037h F000765Ah E9900000h 20. The IEEE 754 floating-point number 7EDCBA98h 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: 2007A654h 600A3B65h 900000E2h AA0000EFh B9000037h F000765Ah 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 87 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 21 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 and answer these questions (all integers are unsigned): a) What is the maximum number of sectors per allocation unit possible? b) What is the maximum number of root directory entries 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 two 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"? *** Zero, Sign, Carry, Overflow Section - see 02.ppt *** Reference: 02.ppt slides 47-49, 53-54 - slide 54 has an error - change second-line 0100+0010 to be 0100+0110 - see the Week 07 notes for handling flags set by Subtraction. 31. Build a Truth Table for two's complement "overflow", based on the rule that the Overflow flag is set if the carry in to the sign bit does not equal the carry out. Use these headings on the truth table columns: ------------ ------------- A B CI R CO OV ------------ ------------- Columns A, B, and CI are possible inputs. R, CO, and OV are outputs. Columns A and B are the sign bits of the two numbers being added. Column CI is the possible carry in to the sign bit. CO (carry out), R (result), and OV (overflow flag) are outputs. The truth table must have eight rows, for all possible combinations of the three inputs A, B, and CI. R is the sign bit of the result (based on A, B, and CI). CO is the carry out (also based on A, B, and CI). OV is whether or not the Overflow flag is set (based on CI and CO). Fill in the whole 8x6 table. 32. How do you know that a two's-complement addition has set the Overflow flag? (There are at least two ways. Give one or both.) 33. Copy the left column of the table in 02.ppt slide 54. Fix the second sum to be 0100+0110. Perform the given two's complement additions. Without looking at the answers, fill in the remaining four columns based on the results. Add another column that states whether the result is correct if treated as unsigned math instead of two's complement. Your answer will have four rows and five columns: RESULT CARRY OVERFLOW SIGNOK UNSIGNOK 34. Perform the following four 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). The "Carry" flag indicates a "Borrow" when doing subtraction of a big number from a smaller number. 011010 011010 + 001111 - 001111 Result: Result: Zero: Zero: Sign: Sign: Carry: Carry: Ovflo: Ovflo: 010111 010110 + 101001 - 010110 Result: Result: Zero: Zero: Sign: Sign: Carry: Carry: Ovflo: Ovflo: 35. Perform the following four 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). 010101 100101 + 101011 - 100101 Result: Result: Zero: Zero: Sign: Sign: Carry: Carry: Ovflo: Ovflo: 011010 011010 - 001111 + 001111 Result: Result: Zero: Zero: Sign: Sign: Carry: Carry: Ovflo: Ovflo: 36. Perform the indicated arithmetic in hexadecimal, assuming a 12-bit word. Show the hexadecimal Result plus the states of the Zero, Sign, Carry and Overflow flags (five answers for each problem). The "Carry" flag indicates a "Borrow" when doing subtraction of a big number from a smaller number. D8A 948 C8B ACE +276 -35A +839 -BDF ------------------------------- Result: Zero: Sign: Carry: Ovflo: 37. Add 16-bit 4999h to 9321h and give the Result, Zero, Sign, Carry, and Overflow. Is the result correct for unsigned math? for signed math? 38. Add 16-bit 7BCDh to AFFFh and give the Result, Zero, Sign, Carry, and Overflow. Is the result correct for unsigned math? for signed math? 39. Add 16-bit 59F9h to 5321h and give the Result, Zero, Sign, Carry, and Overflow. Is the result correct for unsigned math? for signed math? 40. Add 16-bit AA9Ch to 8BCDh and give the Result, Zero, Sign, Carry, and Overflow. Is the result correct for unsigned math? for signed math? 41. Add 18-bit AA9Ch to 8BCDh and give the Result, Zero, Sign, Carry, and Overflow. Is the result correct for unsigned math? for signed math? (NOTE: The 18 is not a mistake. These are 18-bit numbers.) *** Little-Man Computer [LMC] Section *** 42. List the Instruction Cycle activities for the Little Man Computer (LMC). 43. With reference to the full extended LMC opcode table (LMC_opcodes.html), which LMC instruction(s) would not work "properly" if the LM incremented the counter *after* performing the instruction instead of before? 44. What is the purpose of the LMC mnemonic pseudo-instruction DAT? 45. Which LMC instructions set the values of the three LMC light flags? 46. What is the only way that the N (negative) flag can come on? Give an example. 47. Can the N flag and P (positive) flag ever both be on at the same time? Give an example. 48. Can the N flag and Z (zero) flag ever both be on at the same time? Give an example. 49. a) What value appears in the Calculator if you start with 999 and then add one? 50. b) What are the on/off states of the three lights N,Z,P afterward? 51. a) What value appears in the Calculator if you start with zero and then subtract one? 52. b) What are the on/off states of the three lights N,Z,P afterward? For each of the following nine actions, give the final value in the Calculator and indicate the on/off state of the three LMC indicator lights N, Z, and P. Assume that no lights are on to begin with. 53. a) Input 400 into Calculator. ANSWER: N: Z: P: 54. b) 600 is subtracted. ANSWER: N: Z: P: 55. c) 600 is subtracted again. ANSWER: N: Z: P: 56. d) 600 is subtracted again. ANSWER: N: Z: P: 57. e) 600 is subtracted again. ANSWER: N: Z: P: 58. f) 600 is subtracted again. ANSWER: N: Z: P: 59. g) 600 is added. ANSWER: N: Z: P: 60. h) 600 is added again. ANSWER: N: Z: P: 61. i) 600 is added again. ANSWER: N: Z: P: Full marks are awarded only if you show your method, the same method you will have to use on tests and exams. -- | 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/