- Go to the custom code environment.
- Solve as many of the puzzles as you can during the lab time (or in a roughly equivalent amount of time
outside of the lab) using a restricted subset of C (described below).
We expect everyone to complete the first two puzzles, and most to complete the first three.
We expect very few students to attempt all six puzzles within the lab time.
(For the lab, you do not need to complete all the puzzles;
we intend to give full credit as long as your submissions to the coding environment are consistent
with spending an appropriate amount of effort on the puzzles.)
- These puzzles should help you understand the following homework, which, unlike
the lab, must be completed individually and its entirety.
The C Subset
- 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
- You can only use
int-type values. You can use temporary variables and multiple statements, and we encourage you to do this.
- All temporary variables must be initialized on declaration (e.g.
int temporary = 0;)
>>operators are arithmetic shifts
- 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. Assignments to variables do not count towards this limit.
- Solutions violating any of the above rules except the number of operators will result in 0 points.
A partial score is awarded if you have the correct functionality following
all of the rules except the operator count.
Testing outside the Coding environment
- You can copy-and-paste code from the coding environment to your own computer for testing.
This can let you get useful compiler error messages and add
Specific advice for the puzzles
- The puzzles are arranged in approximate order of difficulty and build on each other.
- Use shifts to make the large constant from smaller parts.
- You need to distinguish between
0and non-zero values.
0is the only value where
- There is a much simpler approach than the “any-bit-set” example from lecture given the above.
- It may help to remember how to negate numbers in two’s complement.
^(xor) operator is very helpful.
- Another approach is borrow from a
- Consider creating two masks of the form
0..01..1with different numbers of
0s, then combine them.
- The sign of
x - yis a good starting point.
- You may need special cases for overflow/underflow.
- Use masks to select parts of the number and add those parts together.
- Performing multiple operations in parallel like the “any bit set” example in lecture will help stay under the operation limit. Note that you can perform two additions in parallel in a similar matter to how we demonstrated performing multiple
|s in parallel. For example, you can add
y=0x3+0x1at the same time by performing the one addition
z=0x40003 + 0x70001, then extracting
xfrom the upper bits of
yfrom the lower bits.
- See also 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.