This page does not represent the most current semester of this course; it is present merely as an archive.
The purpose of this assignment is to become more familiar with bit-level representations of numbers. You’ll do this by solving a series of programming
puzzles. Many of these puzzles are quite artificial, but you’ll find yourself thinking much more about bits in working your way through them.
Follow the instructions of your lab TAs. In general, you may work together however you wish as long as they do not say otherwise.
After this lab is over you will be given a homework assignment which is much like the lab (the same structure, but with different puzzles). The homework assignment you must do individually (no group work), so if you do work with others during lab make sure you understand everything your group does.
Submit code via the custom code environment. That environment is focused on code correctness and obeying coding limitations; you might find it useful to write code in C on your own computer where you can use
printf, get good compiler error messages, etc., and then paste your code into the code environment. You can also go the other way, copying from the code environment and pasting in your own editor.
You are restricted to a subset of C
Violating any of the above rules except the number of operators will result in 0 points. Partial credit is awarded if you have the correct functionality following all of the rules except the operator count.
There are six puzzles in the lab. We encouraging doing them in order; they build in complexity and success on one can help you succeed on the next. You do not need to complete all six puzzles; we expect everyone to get the first three, most to get the first four, but very few to complete all six.
The lab is intended to help you think about homework concepts, and is graded on participation. At the end of lab time, feel free to stop and wait for the homework to be released Thursday morning.
exploring the use of shifts to make large constants out of small parts
! operator (which you are trying to recreate) needs to distinguish between 0 and non-zero. One characteristic of 0 is it is the only value
x are both non-negative.
See the lecture notes from Sep-01.
Consider creating two masks of the form
0..01..1 with different numbers of
0s, then combine them. There are several other working solution techniques too…
We suggest working by cases. The sign of
x - y is a good starting point, but it can overflow if
y differ in sign…
This is a hard one if you want to hit the operation limit. The basic idea is to use masks to select parts of the number and add those parts together as a vector. See the lecture notes from Sep-01 12:30 lecture (near the end) and Sep-06 3:30 lecture (near the beginning) for Prof Tychonievich’s effort to explain the approach.
Lab is graded on participation (only).
But it is getting you ready for the homework; the homework will have different puzzles but will be otherwise similar and will be graded as follows:
Each puzzle you must solve has been given a difficulty rating between 1 and 4 and is worth that many points. This is awarded all-or-nothing per puzzle: you either obeyed the coding rules and got all inputs correct or you did not.
There are an additional 2 points per puzzle that are awarded if you use a small number of operators. Again, this is all-or-nothing: you either met the limit or you did not. Why all or nothing? Partly because it is a proxy for
did you use an efficient approach or not, but there is a real-world case for it too: for some real-time systems fast enough is fast enough and too slow is unusable.
You may elect to provide a publicly visible name and have the operation counts of your working code logged on a competition scoreboard.