Bits, Bytes, and Integers August 26, 2009Binary RepresentationsEncoding Byte ValuesByte-Oriented Memory OrganizationMachine WordsWord-Oriented Memory OrganizationData RepresentationsByte OrderingByte Ordering ExampleReading Byte-Reversed ListingsExamining Data Representationsshow_bytes Execution ExampleRepresenting IntegersRepresenting PointersRepresenting StringsBoolean AlgebraApplication of Boolean AlgebraGeneral Boolean AlgebrasRepresenting & Manipulating SetsBit-Level Operations in CContrast: Logic Operations in CShift OperationsInteger C PuzzlesEncoding IntegersEncoding Example (Cont.)Numeric RangesValues for Different Word SizesUnsigned & Signed Numeric ValuesRelation between Signed & UnsignedSigned vs. Unsigned in CCasting SurprisesExplanation of Casting SurprisesSign ExtensionSign Extension ExampleWhy Should I Use Unsigned?Negating with Complement & IncrementComp. & Incr. ExamplesUnsigned AdditionVisualizing Integer AdditionVisualizing Unsigned AdditionMathematical PropertiesTwo’s Complement AdditionCharacterizing TAddVisualizing 2’s Comp. AdditionMathematical Properties of TAddMultiplicationUnsigned Multiplication in CSigned Multiplication in CPower-of-2 Multiply with ShiftCompiled Multiplication CodeUnsigned Power-of-2 Divide with ShiftCompiled Unsigned Division CodeSigned Power-of-2 Divide with ShiftCorrect Power-of-2 DivideCorrect Power-of-2 Divide (Cont.)Compiled Signed Division CodeProperties of Unsigned ArithmeticProperties of Two’s Comp. ArithmeticInteger C Puzzles RevisitedBits, Bytes, and IntegersAugust 26, 2009Bits, Bytes, and IntegersAugust 26, 2009TopicsTopics Representing information as bits Bit-level manipulationsz Boolean algebraz Expressing in C Representations of Integersz Basic properties and operationsz Implications for C15-213 F’09class02.ppt15-213“The Class That Gives CMU Its Zip!”–2–15-213: Intro to Computer SystemsFall 2009 ©Binary RepresentationsBinary RepresentationsBase 2 Number RepresentationBase 2 Number Representation Represent 1521310as 111011011011012 Represent 1.2010as 1.0011001100110011[0011]…2 Represent 1.5213 X 104as 1.11011011011012X 213Electronic ImplementationElectronic Implementation Easy to store with bistable elements Reliably transmitted on noisy and inaccurate wires 0.0V0.5V2.8V3.3V0 1 0–3–15-213: Intro to Computer SystemsFall 2009 ©Encoding Byte ValuesEncoding Byte ValuesByte = 8 bitsByte = 8 bits Binary 000000002to 111111112 Decimal: 010to 25510z First digit must not be 0 in C Hexadecimal 0016to FF16z Base 16 number representationz Use characters ‘0’ to ‘9’ and ‘A’ to ‘F’z Write FA1D37B16in C as 0xFA1D37B» Or 0xfa1d37b0 0 00001 1 00012 2 00103 3 00114 4 01005 5 01016 6 01107 7 01118 8 10009 9 1001A 10 1010B 11 1011C 12 1100D 13 1101E 14 1110F 15 1111HexDecimalBinary–4–15-213: Intro to Computer SystemsFall 2009 ©Byte-Oriented Memory OrganizationByte-Oriented Memory OrganizationPrograms Refer to Virtual AddressesPrograms Refer to Virtual Addresses Conceptually very large array of bytes Actually implemented with hierarchy of different memory types System provides address space private to particular “process”z Program being executedz Program can clobber its own data, but not that of othersCompiler + RunCompiler + Run--Time System Control AllocationTime System Control Allocation Where different program objects should be stored All allocation within single virtual address space–5–15-213: Intro to Computer SystemsFall 2009 ©Machine WordsMachine WordsMachine Has Machine Has ““Word SizeWord Size”” Nominal size of integer-valued dataz Including addresses Most current machines use 32 bits (4 bytes) wordsz Limits addresses to 4GB» Users can access 3GBz Becoming too small for memory-intensive applications High-end systems use 64 bits (8 bytes) wordsz Potential address space ≈ 1.8 X 1019bytesz x86-64 machines support 48-bit addresses: 256 Terabytes Machines support multiple data formatsz Fractions or multiples of word sizez Always integral number of bytes–6–15-213: Intro to Computer SystemsFall 2009 ©Word-Oriented Memory OrganizationWord-Oriented Memory OrganizationAddresses Specify Byte Addresses Specify Byte LocationsLocations Address of first byte in word Addresses of successive words differ by 4 (32-bit) or 8 (64-bit)00000001000200030004000500060007000800090010001132-bitWordsBytes Addr.001200130014001564-bitWordsAddr=??Addr=??Addr=??Addr=??Addr=??Addr=??000000040008001200000008–7–15-213: Intro to Computer SystemsFall 2009 ©Data RepresentationsData RepresentationsSizes of C Objects (in Bytes)Sizes of C Objects (in Bytes) C Data Type Typical 32-bit Intel IA32 x86-64z unsigned 4 4 4z int 4 4 4z long int 4 4 4z char 1 1 1z short 2 2 2z float 4 4 4z double 8 8 8z long double – 10/12 10/12z char * 4 4 8» Or any other pointer–8–15-213: Intro to Computer SystemsFall 2009 ©Byte OrderingByte OrderingHow should bytes within multiHow should bytes within multi--byte word be ordered in byte word be ordered in memory?memory?ConventionsConventions Big Endian: Sun, PPC Macz Least significant byte has highest address Little Endian: x86z Least significant byte has lowest address–9–15-213: Intro to Computer SystemsFall 2009 ©Byte Ordering ExampleByte Ordering ExampleBig Big EndianEndian Least significant byte has highest addressLittle Little EndianEndian Least significant byte has lowest addressExampleExample Variable x has 4-byte representation 0x01234567 Address given by &x is 0x1000x100 0x101 0x102 0x10301 23 45 670x100 0x101 0x102 0x10367 45 23 01Big EndianLittle Endian01 23 45 6767 45 23 01–10–15-213: Intro to Computer SystemsFall 2009 ©Reading Byte-Reversed ListingsReading Byte-Reversed ListingsDisassemblyDisassembly Text representation of binary machine code Generated by program that reads the machine codeExample FragmentExample FragmentAddress Instruction Code Assembly Rendition8048365: 5b pop %ebx8048366: 81 c3 ab 12 00 00 add $0x12ab,%ebx804836c: 83 bb 28 00 00 00 00 cmpl $0x0,0x28(%ebx)Deciphering NumbersDeciphering Numbers Value: 0x12ab Pad to 4 bytes: 0x000012ab Split into bytes: 00 00 12 ab Reverse: ab 12 00 00–11–15-213: Intro to Computer SystemsFall 2009 ©Examining Data RepresentationsExamining Data RepresentationsCode to Print Byte Representation of DataCode to Print Byte Representation of Data Casting
View Full Document