15-213Intro to Computer SystemsRecitation #1By sseshadrToday• Introductions• Datalab Tricks– Floating point questions? Go to Office Hours.• Integer Puzzles• Parity Example• StyleIntroductionsDatalab Tricks• Basics– >>, <<– | vs. ||–& vs. &&–& vs. &&– ! vs. ~• What is x?– int x = (9 | 12) << 1;– x = 26Datalab Tricks• Trick #1: Signed-ness– The MOST significant bit• 0 -> positive or zero• 1 -> negative– What is…• int x = (10 >> 31);• int y = (-10 >> 31);– It’s NOT 1 (what is arithmetic shifting?)– How do we fix that?– Answers:• x = 0 and y = -1Datalab Tricks• Trick #2: Properties of Zero– Masking• 0 & (something) == 0 [why?]•(0-1) & (something) == something •(0-1) & (something) == something [why?]• Why is this useful?– Positive zero vs. negative zero• int x = 0; int y = -x;• Neither x nor y is negative (MSB is 0 for both)• Why is this useful?Datalab Tricks• Trick #3: Negation– Review: take a 5-bit twos compliment system1 0 0 1 01 0 0 1 0-2423212220-16 + 2 = -14Datalab Tricks• Trick #3: Negation– Review: take a 5-bit twos compliment system0 1 1 1 00 1 1 1 0-24232122208+ 4 + 2 = 14Datalab Tricks• Trick #3: Negation– Example:1 0 0 1 0intx = -14; // -141 0 0 1 0intx = -14; // -140 1 1 0 1 int y = ~x; // 130 1 1 1 0 int z = ~x+1; // 14Datalab Tricks• Trick #3: Negation– In general-x == (~x + 1)–Does this always work?–Does this always work?• Tmin?– No!• Tmax?– Yes!• Zero?– Yes!• Everything else?– Yes!Integer PuzzlesInteger Puzzles• (x < 0) => ((x*2) < 0)– Nope. Tmin?•(ux>= 0)•(ux>= 0)– Yup!• (x&7 == 7) => ((x << 30) < 0)– Yup!– (x&7 == 7) means last 3 bits are 1– Examine the “negative bit” of (x<<30)Integer Puzzles• (ux > -1)– Nope. Unsigned comparison means -1 is Umax!•(x > y) => (-x < -y)•(x > y) => (-x < -y)– Nope. Boundary cases.– x = 0, y = Tmin (what is -Tmin?)• (x*x >= 0)– Nope. Overflow into “negative bit”– int x = 65535; // 2^16 - 1Integer Puzzles• (x > 0 && y > 0) => (x + y > 0)– Nope. Overflow into “negative bit”– x, y = Tmax• (x >= 0) => (-x <= 0)– Yup! Why doesn’t break for Tmax?• (x <= 0) => (-x >= 0)– Nope. What is –Tmin?Integer Puzzles• (x|-x) >> 31 == -1– Nope. x = 0• (ux >> 3) == (ux / 8)–Yup! –Yup! • (x >> 3) == (x / 8)– Nope. Careful on rounding!– int x = -19;– int y = x >> 3; // y = -3– int z = x / 8; // z = -2Integer Puzzles• (x & (x-1)) != 0– Nope. x = 0, x = 1Parity Example• Write a function which takes an integer and returns– 1 if there are an odd number of ‘1’ bits–0 if there are an even number of ‘1’ bits–0 if there are an even number of ‘1’ bitsint parity_check(int x){…}• Any ideas?Parity Example• Inspiration:– If we could XOR all of the bits in the argument… we would get the answer!110110010110001111100101001011011101100101100011111001010010110111011001011000111110010100101101XOR0011110001001110 (down to 16 bits)Parity Example• Just keep going!0011110001001110001111000100111000111100010011100011110001001110XOR01110010 (down to 8 bits)Parity Example• Just keep going!01110010011100100111001001110010XOR0101 (down to 4 bits)Parity Example• You can take it from there.– Still confused on high-level algorithm? Can’t write the C code for the Parity Problem? Office Hours.Style• Here is what we grade on:– http://www.cs.cmu.edu/~213/codeStyle.html•It is in your best interest to read it ASAP!•It is in your best interest to read it ASAP!• Autolab isn’t the whole grade. We read your code.Style• Documentation• Whitespace• Line length•Variable names•Variable names• Magic Numbers• Dead Code• Modularity• Error checking•
View Full Document
Unlocking...