Changelog:
- 13 September 2022: add hints regarding tracking “extra” bits in
fiveeigths
- 13 September 2022: copy hint from getbits description on the coding environment to use bottom into hints here
Your Task
-
Work on the corresponding lab first to get familiar with bit puzzles generally.
-
Go to the custom code environment and solve the homework problems.
Note that there is partial credit if you violate some of the restrictions of a puzzle (like the operator count limit) but otherwise solve it.
Hints
Specific advice for the puzzles
- The puzzles are not arranged in order of difficulty. You should not feel obliged to do them in order.
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.
getbits
-
Use bitshifting to create a mask of an appropriate size.
-
Using a solution to
bottom
(from the lab) may be helpful.
fiveeighths
-
You may assume that integer overflow for
+
acts as in two’s complement. -
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.
-
Arithmetic right shift is equivalent to dividing a signed integer by a power of two but always rounding down. Integer division in C always rounds towards zero.
-
If your initial solution idea has problems with loosing information about the fractional part of something/8, think about what would happen to the bits “after the decimal” point if they were preserved by the division (like if the result did not have to be an integer) and still around for the later operations.
-
Similarly, if your initial solution idea has problems with loosing information due to overflow from something*5, think about what happen to the extra bits if they were preserved by the multiplication (like if the result was bigger than 32 bits) and around for later operations.
addok
-
Overflow with
+
will always produce a result with the wrong sign. -
(non-negative) + (negative) can never overflow.
evenbitparity
^
is almost all you need.