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.

We recommending working on the corresponding lab first. (Unlike the homework, you can collaborate with other students on the lab.)

1 Logistics

Work individually (no group work)

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 five puzzles in the homework set. Unlike the corresponding lab, they are not presented in any particular order; if one stumps you the next may well seem easier.

allEvenBits

A mask and emulating the == operator with subtraction will help. (Recall that in two’s complement, negation is flipping all bits and adding 1.)

byteSwap

Lots of masks and shifting in this one. Isolate the bits that are moving into their own variables, clear their destinations in the original number, then put them back in into the number in their new locations.

multFiveEighths

Section 2.3.6 (Multiplying by Constants) and 2.3.7 (Dividing by Powers of Two) in the textbook have most of the solution described, if not explicitly given.

addOK

Overflow with + will always produce a result with the wrong sign. Note that (non-negative) + (negative) can never overflow.

bitParity

^ is your friend. In fact, it is almost all you need.

5 Evaluation

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.