Binary Representations 15 213 The Class That Gives CMU Its Zip Base 2 Number Representation Bits Bytes and Integers September 1 2006 Topics Electronic Implementation Representing information as bits Bit level manipulations z Boolean algebra z Expressing in C Represent 1521310 as 111011011011012 Represent 1 2010 as 1 0011001100110011 0011 2 Represent 1 5213 X 104 as 1 11011011011012 X 213 Easy to store with bistable elements Reliably transmitted on noisy and inaccurate wires 0 Representations of Integers 1 0 3 3V z Basic properties and operations z Implications for C 2 8V 0 5V 0 0V lecture 02 ppt Encoding Byte Values Memory organization Byte 8 bits Binary 000000002 Decimal 010 Hexadecimal 0016 to to to 111111112 25510 FF16 z Base 16 number representation z Use characters 0 to 9 and A to F z Write FA1D37B16 in C as 0xFA1D37B Or 0xfa1d37b Word Oriented Memory Organization 32 bit 64 bit Words Words Address of first byte in word Addresses of successive words differ by word size z e g 4 32 bit or 8 64 bit Addr 0000 Addr 0000 Addr 0004 Addr 0008 Addr 0012 5 al m ry ci n a x He De Bi 0 0 0000 1 1 0001 2 2 0010 3 3 0011 4 4 0100 5 5 0101 6 6 0110 7 7 0111 8 8 1000 9 9 1001 A 10 1010 B 11 1011 C 12 1100 D 13 1101 E 14 1110 F 15 1111 Programs refer to data by address Addr 0008 address space viewed as a large array of bytes an address is like an index into that array Any given computer has a Word Size Size nominal size of integer valued data 32 bits is still most common z and usually of addresses z though 64 bits is emerging 15 213 F 07 3 Addresses Specify Byte Locations 15 213 F 07 2 15 213 F 07 15 213 F 07 4 Data Representations Bytes Addr Sizes of C Objects in Bytes 0000 0001 0002 0003 0004 0005 0006 0007 0008 0009 0010 0011 0012 0013 0014 0015 C Data Type Typical 32 bit z unsigned int z int z long int z char z short z float z double z long double z char 4 4 4 1 2 4 8 4 Intel IA32 x86 64 4 4 4 1 2 4 8 10 12 4 4 4 4 1 2 4 8 10 12 8 Or any other pointer 15 213 F 07 6 Page 1 15 213 F 07 Byte ordering in multi byte words Representing Strings Big Endian e g SPARC Power PC Strings in C Least significant byte has highest address Little Endian e g x86 Least significant byte has lowest address SPARC S 31 35 32 31 33 00 31 35 32 31 33 00 Digit i has code 0x30 i Variable x has 4 byte representation 0x01234567 Address given by x is 0x100 String should be null terminated z Final character 0 Compatibility Big Endian Byte ordering not an issue 0x100 0x101 0x102 0x103 01 Little Endian 23 45 67 0x100 0x101 0x102 0x103 67 45 23 01 15 213 F 07 7 15 213 F 07 8 General Boolean Algebras Back to bits Boolean Algebra Developed by George Boole in 19th Century x86 S z Standard 7 bit encoding of character set z Character 0 has code 0x30 Example char S 6 15213 Represented by array of characters Each character encoded in ASCII format Operate on Bit Vectors Algebraic representation of logic z Encode True as 1 and False as 0 And Or A B 1 when both A 1 and B 1 0 1 A B 1 when either A 1 or B 1 0 1 A 1 when A 0 0 1 1 0 0 1 0 0 1 1 1 0 15 213 F 07 Contrast Logic Operations in C Contrast to Logical Operators Apply to any integral data type z long int short char unsigned z Anything nonzero as True z Always return 0 or 1 z Early termination Examples Char data type 0x41 0x00 0x69 0x55 010000012 000000002 Examples char data type Watch out for vs and vs 0xBE 101111102 0xFF 111111112 0x41 011010012 010101012 010000012 0x69 0x55 0x7D 011010012 010101012 011111012 11 z View 0 as False View arguments as bit vectors Arguments applied bit wise 01010101 10101010 10101010 15 213 F 07 10 Operations Available in C 01101001 01010101 00111100 00111100 All of the Properties of Boolean Algebra Apply Bit Level Operations in C 01101001 01010101 01111101 01111101 A B 1 when either A 1 or B 1 but not both 9 Operations applied bitwise 01101001 01010101 01000001 01000001 0 0 1 1 1 1 ExclusiveExclusive Or Xor Xor 0 0 0 1 0 1 Not 15 213 F 07 12 Page 2 0x41 one of 0x00 0x41 0x00 the more common booboos in 0x01 C programming 0x01 0x69 0x55 0x69 0x55 0x01 0x01 p p avoids null pointer access 15 213 F 07 Shift Operations Left Shift Encoding Integers Unsigned x y Shift bit vector x left y positions Throw away extra bits on left z Fill with 0 s on right Right Shift x y Argument x 01100010 3 00010000 Log 2 00011000 Shift bit vector x right y positions Logical shift Arithmetic shift z Throw away extra bits on right z Fill with 0 s on left z Replicate most significant bit on Log 2 00101000 w 1 w 2 xi 2 x y i i 0 Sign Bit C short 2 bytes long Argument x 10100010 00010000 B2T X xw 1 2 i short int x 15213 short int y 15213 3 xi 2 i 0 Arith 2 00011000 Two s Complement w 1 B2U X Decimal 15213 15213 Hex 3B 6D C4 93 Binary 00111011 01101101 11000100 10010011 Sign Bit Arith 2 11101000 right For 2 s complement most significant bit indicates sign z 0 for nonnegative z 1 for negative 15 213 F 07 13 Numeric Ranges Encoding Example Cont x y 15213 00111011 01101101 15213 11000100 10010011 Weight 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 Sum 15 15213 1 1 0 0 1 4 1 8 0 0 1 32 1 64 0 0 1 256 1 512 0 0 1 2048 1 4096 1 8192 0 0 0 0 15213 15213 1 1 1 2 0 0 0 0 1 16 0 0 0 0 1 128 0 0 0 0 1 1024 0 0 0 0 0 0 1 16384 1 32768 15213 Unsigned Values UMin 0 UMax TMax TMin 1 0 15 213 F 07 TMax 2w 1 1 011 1 111 1 Decimal 65535 32767 32768 1 0 Hex FF FF 7F FF 80 00 FF FF 00 00 Binary 11111111 11111111 01111111 11111111 10000000 00000000 11111111 11111111 00000000 00000000 15 213 F 07 16 Casting Surprises Expression Evaluation If mix unsigned and signed in single expression signed values implicitly cast to unsigned Including comparison operations By default considered to be signed integers Unsigned if have U as suffix Examples …
View Full Document
Unlocking...