Bits, Bytes, and IntegersTopics Representing information as bits Bit-level manipulations Boolean algebra Expressing in C Representations of Integers Basic properties and operations Implications for C15-213 F ‘08class02.ppt15-213“The Class That Gives CMU Its Zip!”– 2 –15-213, S ‘09Binary RepresentationsBase 2 Number Representation Represent 1521310as 111011011011012 Represent 1.2010as 1.0011001100110011[0011]…2 Represent 1.5213 X 104as 1.11011011011012X 213Electronic Implementation Easy to store with bistable elements Reliably transmitted on noisy and inaccurate wires 0.0V0.5V2.8V3.3V0 1 0– 3 –15-213, S ‘09Encoding Byte ValuesByte = 8 bits Binary 000000002to 111111112 Decimal: 010to 25510 First digit must not be 0 in C Hexadecimal 0016to FF16 Base 16 number representation Use characters „0‟ to „9‟ and „A‟ to „F‟ 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 1111– 4 –15-213, S ‘09Byte-Oriented Memory OrganizationPrograms 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” Program being executed Program can clobber its own data, but not that of othersCompiler + Run-Time System Control Allocation Where different program objects should be stored All allocation within single virtual address space• • •– 5 –15-213, S ‘09Machine WordsMachine Has “Word Size” Nominal size of integer-valued data Including addresses Most current machines use 32 bits (4 bytes) words Limits addresses to 4GB Becoming too small for memory-intensive applications High-end systems use 64 bits (8 bytes) words Potential address space 1.8 X 1019bytes x86-64 machines support 48-bit addresses: 256 Terabytes Machines support multiple data formats Fractions or multiples of word size Always integral number of bytes– 6 –15-213, S ‘09Word-Oriented Memory OrganizationAddresses Specify Byte Locations 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, S ‘09Data RepresentationsSizes of C Objects (in Bytes) C Data Type Typical 32-bit Intel IA32 x86-64 char 1 1 1 short 2 2 2 int 4 4 4 long 4 4 8 long long 8 8 8 float 4 4 4 double 8 8 8 long double 8 10/12 10/16 char * 4 4 8» Or any other pointer– 8 –15-213, S ‘09Byte OrderingHow should bytes within multi-byte word be ordered in memory?Conventions Big Endian: Sun, PPC Mac, Internet Least significant byte has highest address Little Endian: x86 Least significant byte has lowest address– 9 –15-213, S ‘09Byte Ordering ExampleBig Endian Least significant byte has highest addressLittle Endian Least significant byte has lowest addressExample 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, S ‘09Reading Byte-Reversed ListingsDisassembly Text representation of binary machine code Generated by program that reads the machine codeExample 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 Numbers Value: 0x12ab Pad to 32 bits: 0x000012ab Split into bytes: 00 00 12 ab Reverse: ab 12 00 00– 11 –15-213, S ‘09Examining Data RepresentationsCode to Print Byte Representation of Data Casting pointer to unsigned char * creates byte arraytypedef unsigned char *pointer;void show_bytes(pointer start, int len){int i;for (i = 0; i < len; i++)printf("0x%p\t0x%.2x\n",start+i, start[i]);printf("\n");}Printf directives:%p: Print pointer%x: Print Hexadecimal– 12 –15-213, S ‘09show_bytes Execution Exampleint a = 15213;printf("int a = 15213;\n");show_bytes((pointer) &a, sizeof(int));Result (Linux):int a = 15213;0x11ffffcb8 0x6d0x11ffffcb9 0x3b0x11ffffcba 0x000x11ffffcbb 0x00– 13 –15-213, S ‘09Representing Integersint A = 15213;int B = -15213;long int C = 15213;Decimal: 15213Binary: 0011 1011 0110 1101Hex: 3 B 6 D6D3B0000IA32, x86-64 A3B6D0000Sun A93C4FFFFIA32, x86-64 BC493FFFFSun BTwo‟s complement representation(Covered later)000000006D3B0000x86-64 C3B6D0000Sun C6D3B0000IA32 C– 14 –15-213, S ‘09Representing Pointersint B = -15213;int *P = &B;FF7F00000C89ECFFx86-64 PDifferent compilers & machines assign different locations to objectsFB2CEFFFSun PFFBFD4F8IA32 P– 15 –15-213, S ‘09char S[6] = "15213";Representing StringsStrings in C Represented by array of characters Each character encoded in ASCII format Standard 7-bit encoding of character set Character “0” has code 0x30» Digit i has code 0x30+i String should be null-terminated Final character = 0Compatibility Byte ordering not an issueLinux/Alpha S Sun S323131353300323131353300– 16 –15-213, S ‘09Boolean AlgebraDeveloped by George Boole in 19th Century Algebraic representation of logic Encode “True” as 1 and “False” as 0And A&B = 1 when both A=1 and B=1& 0 10 0 01 0 1~0 11 0Not ~A = 1 when A=0Or A|B = 1 when either A=1 or B=1| 0 10 0 11 1 1^ 0 10 0 11 1 0Exclusive-Or (Xor) A^B = 1 when either A=1 or B=1, but not both– 17 –15-213, S ‘09A~A~BBConnection whenA&~B | ~A&BApplication of Boolean AlgebraApplied to Digital Systems by Claude Shannon 1937 MIT Master‟s Thesis Reason about networks of relay switches Encode closed switch as 1, open switch as 0A&~B~A&B= A^B– 18 –15-213, S ‘09General Boolean AlgebrasOperate on Bit Vectors Operations applied bitwiseAll of the Properties of Boolean Algebra Apply01101001& 010101010100000101101001| 010101010111110101101001^ 0101010100111100~ 010101011010101001000001 01111101 00111100 10101010– 19 –15-213, S ‘09Representing & Manipulating SetsRepresentation Width w bit vector represents subsets of {0, …, w–1} aj= 1 if j
View Full Document
Unlocking...