- A. Bit Manipulation
- B. Implementing a Packed Array: Nybbles.java
- C. Asymptotic Analysis and A Bit-Twiddling Puzzle
- D. Submission
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!
Note that 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$ integers in an $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. Remember that 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 Written 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),
Nybbles.java (1 point) and the Gradescope assignment
HW5 Written (.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