RepresentationsGoals of Today’s Lecture Radiohead - OK Computer CDPits and LandsInterpretationInterpretation – ASCIIComputer Science Building West WallInterpretation: Code and Data (Hello World!)Interpretation: NumbersWriting Bits is Tedious for PeopleInterpretation: ColorsBinary Representation of IntegersSize and Overflow in Unsigned IntegersAdding Two Integers: Base 10Binary Sums and CarriesOverflow in Unsigned AdditionDetecting Unsigned OverflowModulo ArithmeticModulo ArithmeticWhat about Negative Numbers?Key Standard Pattern AssignmentsMost Common: Two’s ComplementUnsigned and Two’s ComplementRepresentation RelationshipSizes and C Data TypesSign ExtensionSign Extension Proof of Correctness OutlineTwo’s Complement AdditionCharacterizing TAddDetecting Two’s Complement OverflowNegation vs. InversionTwo’s Complement NegationComparing Two’s ComplementsRepresentation: A Collection of BitsBitwise Operators: AND and ORBitwise Operators: Not and XORBitwise Operators: Shift Left/RightCount Number of 1s in an IntegerXOR EncryptionXOR Encryption, ContinuedXOR Encryption, C CodeStupid Programmer TricksExample From Real CodeConclusions1RepresentationsProf. David AugustCOS 2172Goals of Today’s Lecture• Representationso Why binary?o Converting base 10 to base 2o Octal and hexadecimal• Integerso Unsigned integerso Integer addition, subtractiono Signed integers• C bit operatorso And, or, not, and xoro Shift-left and shift-righto Function for counting the number of 1 bitso Function for XOR encryption of a message34Radiohead - OK Computer CD3 Miles of Music5Pits and LandsTransition represents a bit state (1/on/red/female/heads)No change represents other state (0/off/white/male/tails)6Interpretation0 1 1 10101As Music:011101012= 117/256 position of speakerAs Number:011101012= 1 + 4 + 16 + 32 + 64 = 11710= 7516(Get comfortable with base 2, 8, 10, and 16.)As Text: 011101012= 117thcharacter in the ASCII codes = “u”7Interpretation – ASCII8Computer Science Building West WallInterpretation:Code and Data (Hello World!)• Programs consist of Code and Data• Code and Data are Encoded in BitsIA-64 Binary (objdump)10Interpretation:Numbers• Base 10o Each digit represents a power of 10o 4173 = 4 x 103+ 1 x 102+ 7 x 101+ 3 x 100• Base 2o Each bit represents a power of 2o 10110 = 1 x 24+ 0 x 23+ 1 x 22+ 1 x 21+ 0 x 20= 22Divide repeatedly by 2 and keep remainders12/2 = 6 R = 06/2 = 3 R = 03/2 = 1 R = 11/2 = 0 R = 1Result = 110011Writing Bits is Tedious for People• Octal (base 8)o Digits 0, 1, …, 7o In C: 00, 01, …, 07• Hexadecimal (base 16)o Digits 0, 1, …, 9, A, B, C, D, E, Fo In C: 0x0, 0x1, …, 0xf0000 = 0 1000 = 80001 = 1 1001 = 90010 = 2 1010 = A0011 = 3 1011 = B0100 = 4 1100 = C0101 = 5 1101 = D0110 = 6 1110 = E0111 = 7 1111 = FThus the 16-bit binary number1011 0010 1010 1001converted to hex isB2A912Interpretation:Colors• Three primary colorso Redo Greeno Blue• Strengtho 8-bit number for each color (e.g., two hex digits)o So, 24 bits to specify a color• In HTML, on the course Web pageo Red: <font color="#FF0000"><i>Symbol Table Assignment Due</i>o Blue: <font color="#0000FF"><i>Fall Recess</i></font>• Same thing in digital cameraso Each pixel is a mixture of red, green, and blueBinary Representation of Integers• Fixed number of bits in memoryo char: 8 bitso short: usually 16 bitso int: 16 or 32 bitso long: 32 bitso long long: 64 bits• Unsigned integerso Always positive or 0o All arithmetic is modulo 2no unsigned charo unsigned shorto unsigned into unsigned longo unsigned long longBinary Decimal001110 211 31000 8100 4101 5110 6111 7……1{n} 2n-114Size and Overflow in Unsigned IntegersNumber of bits determines unsigned integer rangeOverflow:• 8-bit integer Æ 111111112(25510)•Add 1• What happens?Bits Integer Range32 0 - 4,294,967,29580 -25516 0 - 65,53564 0 - 18,446,744,073,709,551,615Binary Decimal001110 2……1{n} 2n-115Adding Two Integers: Base 10• From right to left, we add each pair of digits• We write the sum, and add the carry to the next column198+264SumCarry011+001SumCarry21614001011016Binary Sums and CarriesabSum abCarry000 000011 010101 100110 111XORAND0100 0101+ 0110 01111010 11006910317217Overflow in Unsigned AdditionModulo Arithmetic: UAddw(u, v) = u + v mod 2w••••••uv+•••u + v•••True Sum: w + 1 bitsOperands: w bitsDiscard Carry: w bitsUAddw(u , v)UAddw(u,v)=u+vu+v<2wu+ v−2wu+v≥2w⎧⎨⎩18Detecting Unsigned Overflow• Task:o Given s = UAddw(u, v)o Determine if s = u + v• Claim:o Overflow iff s < uo ovf = (s < u)o By symmetry iff s < v•Proof:o 0 ≤ v < 2wo No overflow ⇒ s = u + v ≥ u + 0 = uo Overflow ⇒ s = u + v – 2w< u + 0 = uu v2wsu v2wsNo Overflow:Overflow:19Modulo Arithmetic• Consider only numbers in a rangeo E.g., five-digit car odometer: 0, 1, …, 99999o E.g., eight-bit numbers 0, 1, …, 255• Roll-over when you run out of spaceo E.g., car odometer goes from 99999 to 0, 1, …o E.g., eight-bit number goes from 255 to 0, 1, …•Adding 2ndoesn’t change the answero For eight-bit number, n=8 and 2n=256o E.g., (37 + 256) mod 256 is simply 37• This can help us do subtraction…o Suppose you want to compute a – bo Note that this equals a + (256 -1 - b) + 120Modulo ArithmeticModulo Addition Forms an Abelian Group• Closed under additiono 0 ≤ UAddw(u, v) ≤ 2w–1•Commutativeo UAddw(u, v) = UAddw(v, u)• Associativeo UAddw(t, UAddw(u, v)) = UAddw(UAddw(t, u), v)• 0 is additive identityo UAddw(u, 0) = u• Every element has additive inverseo Let UCompw(u) = 2w–uo UAddw(u , UCompw(u)) = 021(negatives…)22What about Negative Numbers?• We have been looking at unsigned numbers• What about negative or signed numbers?• Need new interpretation of bits• Some patterns interpreted as negative numbersBits Patterns32 4,294,967,2968 25616 65,53664 18,446,744,073,709,551,61631021102n1{n}……PatternBinaryKey Standard Pattern Assignments• Which one is best?o Balanceo Zeroso Ease of operations+1+1+10010+0+0000Two’s ComplementOne’s ComplementSign MagnitudeBit Pattern+3+3+3011+2+2+2010-4-3-0100-1-0-3111-2-1-2110-3-2-1101Most Common: Two’s Complement+10010000Two’s ComplementBit Pattern+3011+2010-4100-1111-2110-3101• “Invert and Add 1” to negate•Sign Bit• Zeros, Range• What about arithmetic?Unsigned and Two’s Complement• Unsigned Values• UMin = 0• UMax = 2w–1• Two’s Complement• TMin = –2w–1• TMax = 2w–1–1B2T(X)
View Full Document
Unlocking...