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.

After this lab, there will be a follow-up homework assignment.

1 Logistics

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.

2 Coding Environment

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.

3 Rules

You are restricted to a subset of C

• Constants cannot exceed a single byte (between 0 and 255, or 0x00 and 0xff)
• You cannot have any control constructs (no if, for, etc)
• You can only use int-type values
• Each puzzle has a limited set of operators you are allowed to use
• Each puzzle has a limit on the number of operators you are allowed to use

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.

4 The Puzzles

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.

thirdBits

exploring the use of shifts to make large constants out of small parts

bang

The ! 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 where -x and x are both non-negative. Given the operators you have access to, this allows you to use a much simpler approach than the any bit set method we showed in lecture.

isEqual

The xor operator is one approach to this problem. Another would be to borrow something from your bang solution. Note that more operators are allowed for this problem than previous problems; this is probably necessary.

bitMask

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…

isLessOrEqual

We suggest working by cases. The sign of x - y is a good starting point, but it can overflow if x and y differ in sign…

bitCount

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. Using the parallelism approach mentioned in lecture can help solve this. See Prof. Khan’s slides from Spring 2017 (slide 43) for an approach. Or see the Fall 2016’s 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.

5 Evaluation

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:

Correctness points.

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.

Performance points.

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.

Opt-in Competition

You may elect to provide a publicly visible name and have the operation counts of your working code logged on a competition scoreboard.