CS107 Handout 06Spring 2008 April 4, 2008Computer Memory: Bits and BytesThis handout was written by Nick Parlante and Julie Zelenski.To begin, we are going to take a glimpse into the inner workings of a computer. Thegoal is that by seeing the basics of how the computer and compiler cooperate, you willbetter understand how language features work.Basic ArchitectureAlmost all modern computers today are designed using the Von Neumann architectureof 1954. In the Von Neumann architecture, the computer is divided into a CentralProcessing Unit, CPU, and memory. The CPU contains all the computational power ofthe system while the memory stores the program code and data for the program. VonNeumann's innovation was that memory could be used to store both the programinstructions and the program's data. The instructions that constitute a program are laidout in consecutive words in memory, ready to be executed in order. The CPU runs in a"fetch-execute" cycle where it retrieves and executes program instructions frommemory. The CPU executes the current instruction, and then fetches and executes thenext instruction, and so on. The sort of instructions the CPU executes are detailed later inthis handout.MemoryThe smallest unit of memory is the "bit". A bit can be in one of two states— on vs. off, oralternately, 1 vs. 0. Technically any object that can have two distinct states canremember one bit of information. This has been done with magnets, gear wheels, andtinker toys, but almost all computers use little transistor circuits called "flip-flops" to storebits. The flip-flop circuit has the property that it can be set to be in one of two states, andwill stay in that state and can be read until it is reset.Most computers don't work with bits individually, but instead group eight bits togetherto form a "byte". Each byte maintains one eight-bit pattern. A group of N bits can bearranged in 2N different patterns. So a byte can hold 28 = 256 different patterns. Thememory system as a whole is organized as a large array of bytes. Every byte has itsown "address" which is like its index in the array. Strictly speaking, a program caninterpret a bit pattern any way it chooses. By far the most common interpretation is toconsider the bit pattern to represent a number written in base 2. In this case, the 256patterns a byte can hold map to the numbers 0..255.The CPU can retrieve or set the value of any byte in memory. The CPU identifies eachbyte by its address. For this class, we will write memory operations like arrayoperations, so something like the notation Mem[20]=34 sets the value of memory ataddress 20 to the value 34. The byte is sometimes defined as the “smallest addressable2unit” of memory. Most computers also support reading and writing larger units ofmemory— 2 byte "half-words" (sometimes known as a “short” word) and 4 byte"words". Half-words and words span consecutive bytes in memory. By convention theaddress of any multiple-byte thing is the address of its lowest byte— its "base-address".So the 4-byte word at address 400 is composed of bytes 400, 401, 402, and 403. Mostcomputers restrict half-word and word accesses to be "aligned"— a half-word must startat an even address and a word must start at an address that is a multiple of 4.Thankfully, most programming languages shield the programmer from the detail ofbytes and addresses. Instead, programming languages provide the abstractions ofvariable and type for the programmer to manipulate. In the simplest scheme, a variable isimplemented in the computer as a collection of bytes of memory. The type of thevariable determines the number of bytes required. Here are the basic types and theirsizes:Character— The ASCII code defines 128 characters and a mapping of thosecharacters onto the numbers 0..127. For example, the letter 'A' is assigned 65 inthe ASCII table. Expressed in binary, that's 26 + 20 (64 + 1), and so the byte thatrepresents 'A' is:01000001All standard ASCII characters have zero in the uppermost bit (the "mostsignificant" bit) since they only span the range 0..127. Some computers use anextended character set which adds characters like é and ö using the previouslyunused numbers in the range 128..255. Some systems use the 8th bit to storeparity information so a modem for example, can notice if a byte has beencorrupted. Some memory hardware systems keep a 9th parity bit for everybyte so the hardware can notice if memory is getting flaky— avoidingtroublesome HAL 9000 type problems.Short Integer— 2 bytes or 16 bits. 16 bits provide 216 = 65536 patterns. Thisnumber is known as “64k”, where 1 “k” of something is 210=1024. For non-negative numbers these patterns map to the numbers 0..65535. For example,consider the 2-bye short representing the value 65. It has the same binary bitpattern as the 'A' above in the lowermost (or "least significant") byte and zerosin the most significant byte. However, if a short occupies the 2 bytes ataddresses 450 and 451, is the most significant byte at the lower or highernumbered address? Unfortunately, this is not standardized. Systems that arebig-endian (Motorola 68K, PowerPC, Sparc, most RISC chips) store the most-significant byte at the lower address, so 65 as a short would look like this:0000000001000001A little-endian (Intel x86, Pentium) system arranges the bytes in the oppositeorder, so it would look like this:01000001000000003This means when exchanging data through files or over a network betweendifferent endian machines, there is often a substantial amount of "byte-swapping" required to rearrange the data. Sigh, standards (or lack thereof).To get negative numbers, there's a slightly different system which interpretsthe patterns as the numbers -32768..32767, with one bit reserved for storingsign information. The "sign bit" is usually the most significant bit of the mostsignificant byte.Long Integer— 4 bytes or 32 bits. 32 bits provide 232 = 4294967296 patterns. Mostprogrammers just remember this numbers as “about 4 billion”. The signedrepresentation can deal with numbers in the approximate range ±2 billion. 4bytes is the contemporary default size for an integer. Also known as a "word".The representation of a long is just like that of a short. On a big-endianmachine, the four bytes are arranged in order of most significant to least andvice versa for a little-endian machine.Floating Point— 4, 8, 10, or 12 bytes. Almost all computers use the standard