DOC PREVIEW
Princeton COS 126 - TOY II

This preview shows page 1-2-15-16-17-32-33 out of 33 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Introduction to Computer Science • Sedgewick and Wayne • Copyright © 2007 • http://www.cs.Princeton.EDU/IntroCSTOY IIWhat We've Learned About TOYData representation. Binary and hex.TOY.•Box with switches and lights.•16-bit memory locations, 16-bit registers, 8-bit pc.•4,328 bits = (255 × 16) + (15 × 16) + (8) = 541 bytes!•von Neumann architecture.TOY instruction set architecture. 16 instruction types.TOY machine language programs. Variables, arithmetic, loops.0A: 0003 30B: 0009 90C: 0000 00D: 0000 00E: 0001 110: 8A0A RA ← mem[0A] a11: 8B0B RB ← mem[0B] b12: 8C0D RC ← mem[0D] c = 013: 810E R1 ← mem[0E] always 114: CA18 if (RA == 0) pc ← 18 while (a != 0) {15: 1CCB RC ← RC + RB c = c + b16: 2AA1 RA ← RA - R1 a = a - 117: C014 pc ← 14 }18: 9C0C mem[0C] ← RC19: 0000 haltQuick Review: Multiplyloopinputsconstantsoutputmultiply.toyWhat We Do TodayData representation. Negative numbers.Input and output. Standard input, standard output.Manipulate addresses. References (pointers) and arrays.TOY simulator in Java and implications.Data RepresentationDigital WorldData is a sequence of bits. (interpreted in different ways)•Integers, real numbers, characters, strings, …•Documents, pictures, sounds, movies, Java programs, …Ex. 01110101•As binary integer: 1 + 4 + 16 + 32 + 64 = 117 (base ten). •As character: 117th Unicode character = 'u'.•As music: 117/256 position of speaker.•As grayscale value: 45.7% black.Decimal and binary addition.Subtraction. Add a negative integer.Q. How to represent negative integers? 1 1 1 013 0 0 0 0 1 1 0 1+ 092 + 0 1 0 1 1 1 0 0 105 0 1 1 0 1 0 0 1Adding and Subtracting Binary Numberscarriese.g., 6 - 4 = 6 + (-4))Representing Negative IntegersTOY words are 16 bits each.•We could use 16 bits to represent 0 to 216 - 1.•We want negative integers too.•Reserving half the possible bit-patterns for negative seems fair.Highly desirable property. If x is an integer, then the representation of -x, when added to x, yields zero. x 0 0 1 1 0 1 0 0+(-x) + ? ? ? ? ? ? ? ? 0 0 0 0 0 0 0 0 0 x 0 0 1 1 0 1 0 0 + 1 1 0 0 1 0 1 1+(-x) 1 1 1 1 1 1 1 1 + 1 0 0 0 0 0 0 0 0 0 -x: flip bits and add 1-5-41 1 1 11 1 1 ?1 1 1 1 1 11 011 1 1 11 1 1 ?1 1 1 1 0 01 110 0 0 00 0 0 ?0 0 0 0 0 00 10+4Two's Complement IntegersTo compute -x from x:•Start with x. •Flip bits.•Add one.leading bit determines signTwo's Complement Integers1 1 1 10 1 1 ?1 1 1 1 1 11 1113 12 11 1015 14 79 8 6 4 1 03 250 0 0 00 0 0 ?0 0 0 0 0 00 100 0 0 00 0 0 ?0 0 0 0 1 10 000 0 0 00 0 0 ?0 0 0 0 1 00 000 0 0 00 0 0 ?0 0 0 0 0 10 000 0 0 00 0 0 ?0 0 0 0 0 00 001 1 1 11 1 1 ?1 1 1 1 1 11 111 1 1 11 1 1 ?1 1 1 1 1 01 111 1 1 11 1 1 ?1 1 1 1 0 11 111 1 1 11 1 1 ?1 1 1 1 0 01 110 0 0 01 0 0 ?0 0 0 0 0 00 007FFF00040003000200010000FFFFFFFEFFFDFFFC8000+32767+4+3+2+1+0-1-2-3-4-32768hexdec binaryProperties of Two's Complement IntegersProperties.Leading bit (bit 15 in Toy) signifies sign.Addition and subtraction are easy.0000000000000000 represents zero.Negative integer -x represented by 216 - x.Not symmetric: can represent -32,768 but not 32,768.Java. Java's int data type is a 32-bit two's complement integer.Ex. 2147483647 + 1 equals -2147483648.Representing Other Primitive Data Types in TOYBigger integers. Use two 16-bit words per int.Real numbers.•Use "floating point" (like scientific notation).•Use four 16-bit words per double.Characters.•Use ASCII code (8 bits / character).•Pack two characters per 16-bit word.Note. Real microprocessors add hardware support for int and double.Standard Input and OutputStandard OutputStandard output.•Writing to memory location FF sends one word to TOY stdout.•Ex. 9AFF writes the integer in register A to stdout.00: 0000 001: 0001 110: 8A00 RA ← mem[00] a = 011: 8B01 RB ← mem[01] b = 1 do {12: 9AFF write RA to stdout print a13: 1AAB RA ← RA + RB a = a + b14: 2BAB RB ← RA - RB b = a - b15: DA12 if (RA > 0) goto 12 } while (a > 0)16: 0000 haltStandard InputStandard input.•Loading from memory address FF loads one word from TOY stdin.•Ex. 8AFF reads an integer from stdin and store it in register A.Ex: read in a sequence of integers and print their sum.•In Java, stop reading when EOF.•In TOY, stop reading when user enters 0000.while (!StdIn.isEmpty()) { a = StdIn.readInt(); sum = sum + a;}StdOut.println(sum); 00: 0000 010: 8C00 RC <- mem[00] 11: 8AFF read RA from stdin12: CA15 if (RA == 0) pc ← 1513: 1CCA RC ← RC + RA14: C011 pc ← 11 15: 9CFF write RC16: 0000 halt00AE00460003000000F724Standard Input and Output: ImplicationsStandard input and output enable you to:Put information from real world into machine.Get information out of machine.Process more information than fits in memory.Interact with the computer while it is running.Information can be instructions!Booting a computer.Sending programs over the InternetSending viruses over the InternetPointersaddrLoad Address (a.k.a. Load Constant)Load address. [opcode 7]•Loads an 8-bit integer into a register.•7A30 means load the value 30 into register A.Applications.•Load a small constant into a register.•Load an 8-bit memory address into a register.11311211101001511407?6190806140100030215716A16316016opcode dest da = 0x30;Java code(NOTE hex literal)register stores "pointer" to a memory cellArrays in TOYTOY main memory is a giant array.•Can access memory cell 30 using load and store.•8C30 means load mem[30] into register C.•Goal: access memory cell i where i is a variable.Load indirect. [opcode A]•AC06 means load mem[R6] into register C.Store indirect. [opcode B]•BC06 means store contents of register C into mem[R6].a variable indexa variable index3031323334353637……0000000100010002000300050008000D……TOY memoryExample: Reverse an arrayTOY implementation of reverse.•Read in a sequence of integers and store in memory 30, 31, 32, …•Stop reading if 0000. •Print sequence in reverse order.Java version:int i = 0;while (!StdIn.isEmpty()){ a[i] = StdIn.readInt(); i++;}i--;while (i >= 0){ StdOut.println(a[i]); i--;}(We’ll just assume a[] is big enough)TOY Implementation of ReverseTOY implementation of reverse.•Read in a sequence of


View Full Document

Princeton COS 126 - TOY II

Download TOY II
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view TOY II and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view TOY II 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?