Computer Systems IntroductionCourse ThemeTextbooksSyllabusNotes:FacilitiesCS 105 “Tour of the Black Holes of Computing”C PuzzlesEncoding IntegersEncoding Integers (Cont.)Numeric RangesValues for Different Word SizesUnsigned & Signed Numeric ValuesCasting Signed to UnsignedRelation Between Signed & UnsignedSigned vs. Unsigned in CCasting SurprisesSlide 18Explanation of Casting SurprisesSign ExtensionSign Extension ExampleWhy Should I Use Unsigned?Negating with Complement & IncrementComp. & Incr. ExamplesUnsigned AdditionTwo’s-Complement AdditionDetecting 2’s-Comp. OverflowMultiplicationPower-of-2 Multiply by ShiftingUnsigned Power-of-2 Divide by Shifting– 1 –CS 105 Computer SystemsIntroduction Computer SystemsIntroductionTopics:Topics:Staff, text, and policiesLecture topics and assignmentsLab rationaleCS 105“Tour of the Black Holes of Computing!”Geoff KuenningSpring 2010– 2 –CS 105Course ThemeCourse ThemeAbstraction is good, but don’t forget reality!Many CS Courses emphasize abstractionMany CS Courses emphasize abstractionAbstract data typesAsymptotic analysisThese abstractions have limitsThese abstractions have limitsEspecially in the presence of bugsNeed to understand underlying implementationsUseful outcomesUseful outcomesBecome more effective programmersAble to find and eliminate bugs efficientlyAble to tune program performancePrepare for later “systems” classes in CSCompilers, Operating Systems, Networks, Computer Architecture, Robotics, etc.– 3 –CS 105TextbooksTextbooksRandal E. Bryant and David R. O’Hallaron, Randal E. Bryant and David R. O’Hallaron, “Computer Systems: A Programmer’s Perspective”, Prentice Hall, 2003.Brian Kernighan and Dennis Ritchie, Brian Kernighan and Dennis Ritchie, “The C Programming Language, Second Edition”, Prentice Hall, 1988Larry Miller and Alex QuiliciLarry Miller and Alex QuiliciThe Joy of C, Wiley, 1997– 4 –CS 105SyllabusSyllabusSyllabus on Web: http://www.cs.hmc.edu/~geoff/cs105Calendar defines due datesLabs: cs105submit for some, others have specific directions– 5 –CS 105Notes:Notes:Work groupsWork groupsYou must work in pairs on all labsHonor-code violation to work without your partner!Corollary: showing up late doesn’t harm only youHandinsHandinsCheck calendarElectronic submissions onlyGrading CharacteristicsGrading CharacteristicsLab scores tend to be highSerious handicap if you don’t hand a lab inTests & quizzes typically have a wider range of scoresI.e., they’re primary determinant of your grade»…but not the ONLY oneDo your share of lab work and reading, or bomb tests– 6 –CS 105FacilitiesFacilitiesAssignments will use Intel computer systemsAssignments will use Intel computer systemsNot all machines are created alikeSome Macs are PowerPCsEven Intel Macs aren’t necessarily compatibleKnuth is a 64-bit serverWilkes: x86/Linux specifically set up for this classLog in on a Mac, then ssh to WilkesIf you want fancy programs, start X11 firstDirectories are cross-mounted, so you can edit on Knuth or your Mac, and Wilkes will see your files…or ssh into Wilkes from your dormAll programs must run on Wilkes: that’s where we gradeCS 105 “Tour of the Black Holes of Computing”TopicsTopicsNumeric EncodingsUnsigned & two’s complementProgramming ImplicationsC promotion rulesBasic operationsAddition, negation, multiplication Programming ImplicationsConsequences of overflowUsing shifts to perform power-of-2 multiply/divideCS 105IntegersIntegers– 8 –CS 105C PuzzlesC PuzzlesTaken from old examsAssume machine with 32-bit word size, two’s complement integersFor each of the following C expressions, either:Argue that it is true for all argument valuesGive example where it is not true•x < 0 ((x*2) < 0)•ux >= 0•x & 7 == 7 (x<<30) < 0•ux > -1•x > y -x < -y•x * x >= 0•x > 0 && y > 0 x + y > 0•x >= 0 -x <= 0•x <= 0 -x >= 0int x = foo();int y = bar();unsigned ux = x;unsigned uy = y;Initialization– 9 –CS 105Encoding IntegersEncoding Integers short int x = 15213; short int y = -15213;C short 2 bytes longSign BitSign BitFor 2’s complement, most-significant bit indicates sign0 for nonnegative1 for negativeB2T (X ) xw 12w 1 xi2ii0w 2B2U(X ) xi2ii0w 1UnsignedTwo’s ComplementSignBitDecimal Hex Binaryx152133B 6D 00111011 01101101y-15213C4 93 11000100 10010011– 10 –CS 105Encoding Integers (Cont.)Encoding Integers (Cont.) x = 15213: 00111011 01101101 y = -15213: 11000100 10010011Weight 15213 -1521311111200124140081800160011632132006416400128001128256125600512151200102400110242048120480040961409600819218192001638400116384-32768001-32768Sum 15213 -15213– 11 –CS 105Numeric RangesNumeric RangesUnsigned ValuesUnsigned ValuesUMin = 0000…0UMax = 2w – 1111…1Two’s-Complement ValuesTwo’s-Complement ValuesTMin = –2w–1100…0TMax = 2w–1 – 1011…1Other ValuesOther ValuesMinus 1111…1Decimal Hex BinaryUMax65535FF FF 11111111 11111111TMax327677F FF 01111111 11111111TMin-3276880 00 10000000 00000000-1-1FF FF 11111111 111111110000 00 00000000 00000000Values for W = 16– 12 –CS 105Values for Different Word SizesValues for Different Word SizesObservationsObservations|TMin | = TMax + 1Asymmetric rangeUMax = 2 * TMax + 1 C ProgrammingC Programming#include <limits.h>K&R Appendix B11Declares constants, e.g.,ULONG_MAXLONG_MAXLONG_MINValues platform-specific– 13 –CS 105Unsigned & SignedNumeric ValuesUnsigned & SignedNumeric ValuesX B2T(X)B2U(X)0000 00001 10010 20011 30100 40101 50110 60111 7–88–79–610–511–412–313–214–1151000100110101011110011011110111101234567EquivalenceEquivalenceSame encodings for nonnegative valuesUniquenessUniquenessEvery bit pattern represents unique integer valueEach representable integer has unique bit encoding– 14 –CS 105 short int x = 15213; unsigned short int ux = (unsigned short) x; short int y = -15213; unsigned short int uy = (unsigned short) y;Casting Signed to UnsignedCasting Signed to UnsignedC Allows Conversions from Signed to UnsignedC Allows Conversions from Signed to UnsignedResulting ValueResulting ValueNo change in bit
View Full Document