**Assignment 02: Data Representation** This assignment will familiarize you with bit-level representations of integers and floating point numbers and with various operations performed on these data types. You will *solve* a series of programming *puzzles*. Even though many of the puzzles are quite artificial, you will find yourself thinking much more about bits in working your way through them. You must work in a group of two people in solving the problems. You should complete this assignment using pair programming, and you and your partner should submit one solution. **The assignment will be much easier if you and your partner brainstorm each puzzle before coding!** # Learning Goals - Learn how integers and floats are represented in memory - Learn how to use bitwise operators in C # Grading Walk-Throughs This assignment will be graded as "Nailed It" / "Not Yet" by a TA. To pass ("Nailed It") the assignment, you must 1. Complete the assignment and submit your work to gradescope. + You should start this assignment in class on the day shown on the calendar. + *Complete the assignment as early as possible*. 1. Schedule a time to meet with a TA. You can meet with them after the submission deadline. + You must book a time to meet with a TA + Sign-up on the Google Sheet *with at least 36 hours of notice*. + Contact your TA on Slack after signing up. + All partners must meet with the TA. If you cannot all make it at the same time, then each of you needs to schedule a time to meet with the TAs. 1. Walk the TA through your solutions prior to the deadline. + Walk-throughs should take no more than 20 minutes. + You should be well prepared to walk a TA through your answers. + You may not make any significant corrections during the walk-through. You should plan on making corrections afterward and scheduling a new walk-through time. Mistakes are expected---nobody is perfect. + You must be prepared to explain your answers and justify your assumptions. TAs do not need to lead you to the correct answer during a walk-through---this is best left to a mentor session. 1. The TA will then either + mark your assignment as "Nailed It" on gradescope, or + mark your assignment as "Not Yet" and inform you that you have some corrections to make. 1. If corrections are needed, then you will need to complete them and then schedule a new time to meet with the TA. + You will ideally complete any needed revisions by the end of the day the following Monday. If you have concerns about the grading walk-through, you can meet with me after you have first met with a TA. # Overview Materials this assignment are available on the course VM. I strongly recommend that you complete this assignment on the VM. To start, you should - connect to the Pomona VPN (if needed because you are off-campus), - `ssh` into `itbdcv-lnx04p.campus.pomona.edu` (using VSCode or a terminal and shell), and - then grab and extract the starter code. ~~~bash # Navigate to that directory cd ~/cs105/assignments # Copy and unpack the starter code tar xvf /data/A02-DataRepresentation.tar # Navigate into the new directory cd A02-DataRepresentation ~~~ For any command above, you can use [explainshell.com (match command-line arguments to their help text)](https://explainshell.com/) to get a pretty detailed explanation. For example, Running these commands will result in the creation of a directory named `A02-DataRepresentation` containing a file named `bits.c`. The `bits.c` file contains function declarations for several programming puzzles. Each function heading tells you what operations are allowed. Some functions, for example, require you to use only *straightline* code (no loops or conditionals) and a limited number of C arithmetic and logical operators. This assignment is heavily inspired by work from R. Bryant and D. O'Hallaron. Here is an example how doing so (**you can copy and past from the above animation!**): If you do not see an animation above this line (or if you see the animation but you don't see the progress bar), you will need to refresh the page (sometimes more than once). Or you can go directly to the player: https://asciinema.org/a/519851 # Examples Here are two examples representative of what you'll find in `bits.c`. ~~~c linenumbers // pow2plus1(x) - returns 2^x + 1, where 0 ≤ x ≤ 31 // Example: pow2plus1(7) = 2^7 + 1 = 129 int pow2plus1(int x) { // TODO: implement this function } // pow2plus4(x) - returns 2^x + 4, where 0 ≤ x ≤ 31 // Example: pow2plus4(7) = 2^7 + 4 = 132 int pow2plus4(int x) { // TODO: implement this function } ~~~ And here are the solutions. ~~~c linenumbers // pow2plus1(x) - returns 2^x + 1, where 0 ≤ x ≤ 31 // Example: pow2plus1(7) = 2^7 + 1 = 129 int pow2plus1(int x) { // Exploit ability of shifts to compute powers of 2 return (1 << x) + 1; } // pow2plus4(x) - returns 2^x + 4, where 0 ≤ x ≤ 31 // Example: pow2plus4(7) = 2^7 + 4 = 132 int pow2plus4(int x) { // Exploit ability of shifts to compute powers of 2 int result = (1 << x); // Now add four to the result result += 4; return result; } ~~~ # Tips and Tricks My number one tip is to take the given examples and write them out on paper in binary. You should even upload your hand drawn pictures on gradescope--this will help you and your TA during your grading walk-throughs. - `int bit_and(int x, int y)` + [De Morgan's laws - Wikipedia](https://en.wikipedia.org/wiki/De_Morgan's_laws "De Morgan's laws - Wikipedia") - `int bit_xor(int x, int y)` + [XOR gate circuit (Section XOR gate using NAND gate)](https://electronicsphysics.com/xor-gate-diagram-using-only-nand-or-nor-gate/ "XOR gate circuit diagram using only NAND or NOR gate - edumir-Physics") + Hint: a "NAND" gate is an `&` operation followed by a `~` operation - `int is_not_equal(int x, int y)` + Which single bit-wise operator tells you if bits are the same or not? - `int copy_lsb(int x)` + Which shift operation "fills" all bits with the same value? - `int bang(int x)` + Negating zero should leave you with the same value for the sign bit. - `int twos_max(void)` + Can you get a 32-bit value with all ones and then flip the most significant (sign) bit? - `int is_not_negative(int x)` + Can you isolate the sign bit and get rid of (ignore) all lower order bits? - `int add_is_possible(int x, int y)` + How large do the inputs need to be to cause an overflow? + What is the sign of `x`, `y`, and their `sum` during an overflow? + [Number base converter](https://baseconvert.com/) - `unsigned unsigned negate_float(unsigned f)` + [Single-precision floating-point format - Wikipedia](https://en.wikipedia.org/wiki/Single-precision_floating-point_format "Single-precision floating-point format - Wikipedia") * [IEEE 754 32-Bit Standard](https://en.wikipedia.org/wiki/Single-precision_floating-point_format#IEEE_754_standard:_binary32) * [Exponent](https://en.wikipedia.org/wiki/Single-precision_floating-point_format#Exponent_encoding) * [Conversion to decimal](https://en.wikipedia.org/wiki/Single-precision_floating-point_format#Converting_binary32_to_decimal) + [NaN - Wikipedia](https://en.wikipedia.org/wiki/NaN#Floating_point "NaN - Wikipedia") + [IEEE-754 Floating Point Converter](https://www.h-schmidt.net/FloatConverter/IEEE754.html) + [Hex to Binary Converter](https://www.rapidtables.com/convert/number/hex-to-binary.html) - `int float2int(unsigned f)` * You can break `f` into the sign, exponent, and fractional parts, and then decide what to return based on these values. + [IEEE-754 Floating Point Converter](https://www.h-schmidt.net/FloatConverter/IEEE754.html) # Submitting Your Assignment You will submit your code and/or responses on gradescope. **Only one partner should submit.** The submitter will add the other partner through the gradescope interface. - [Submitting an Assignment](https://help.gradescope.com/article/ccbpppziu9-student-submit-work) - [Adding Group Members](https://help.gradescope.com/article/m5qz2xsnjy-student-add-group-members) - [gradescope Student Help Center](https://help.gradescope.com/category/cyk4ij2dwi-student-workflow)