- A. Bit Manipulation
- B. Implementing a Packed Array: Nybbles.java
- C. Asymptotic Analysis and A Bit-Twiddling Puzzle
- D. Submission
This homework assignment has 3 portions. The first two are coding exercises related to bit manipulation. The third is a Gradescope assignment that will test your conceptual knowledge on bit twiddling and asymptotic analysis. The introduction video will prime you in getting started for this assignment (with most emphasis on Nybbles), but it doesn't talk about asymptotic analysis, which is on the Gradescope assignment.
A. Bit Manipulation
For this section, open
You will be completing three functions:
powerOfTwo(int x), and
absolute(int x). Their behavior (and examples) are in the documentation. You only have to complete two out of three for full credit, but we recommend working on all of them.
Do not use for, while, switch, or if cases. Do not import any new libraries or use functionality provided in Math. Your solution should only use Java arithmetic, logical, and bitwise operations (
Hint: If you are feeling confused, look into how Two's Compliment is done in Java. This will give you a head start in CS61C!
All numbers are represented in our code as bits under the hood. For example,
int mask = 15; is exactly equivalent to specifying the bits
int mask = 0b1111;
Also, ints are 32 bits, shorts are 16 bits, longs are 64 bits, and (as always) bytes are 8 bits!
B. Implementing a Packed Array: Nybbles.java
Let's suppose we have an application that strains our computer's primary memory capacity and need to fit large arrays of small integers into as little space as possible. We want a data type that provides an array of integers that are limited in range to $-8$ to $7$. Such integers are representable in 4 bits (half a byte, also known as a nybble). So in principle, it ought to be possible to store $N$ nybbles in a length $N/8$-integer array (packing 8 4-bit integers into each int, as an int is 32 bits). For example, if you wanted the zeroth nybble, you would want bits 0-4 of the 0th int. To get the ninth nybble, you would want bits 4-7 of the 1st int.
Here is a visual of how the underlying
int is related to the Nybbles object:
Here, the top array
[39, 42290814, -35] is the underlying
int, and the bottom array is contents of the Nybbles object. So a client
of the Nybbles class would only know about the bottom array which holds the actual nybbles. The middle array is just the top array with
each integer expanded into its binary representation.
In this case, if we called
get(13) on this object, then we'd first want to figure out the corresponding index in the
int and then
isolate the nybble we care about. In this case, the corresponding index is 1, and the corresponding nybble is 5. Why? Because in our array
arr, we know that
arr has nybbles 0 through 7, and
arr will have nybbles 8 through 15, and we're lookiing for nybble 13. Nybbles in
an integer, just like bits, are indexed from right to left, so the nybble at index 0 of an integer is the rightmost 4 bits. So calling
get(13) in this example will return the nybble
0b1000 which is -8.
Fill in the skeleton to provide a suitable small-int array type. Do not perform any additional new operations in the implementation (you may include as many as you want for testing, if you put them in a different file).
C. Asymptotic Analysis and A Bit-Twiddling Puzzle
Go to Gradescope and complete the
HW5 Multiple Choice assignment within Gradescope. You have unlimited attempts. As with the Proj1 quiz, grades will take a while to update.
Complete 2/3 of the methods in
BitExercise.java (.25 point), pass at least 3 of the tests for
Nybbles.java (1 point) and the Gradescope assignment
HW5 Multiple Choice (.75 point) to get full credit for this homework. Style will not be checked.
Not all tests are provided in the skeleton.
Don't forget to push both your commits and tags for your final submission. As a reminder, you can push your tags by running:
$ git push --tags