Homework 5: Bit Operations and Asymptotic Analysis

A. Bit Manipulation

For this section, open BitExercise.java. You will be completing three functions: lastBit(int x), 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 (&, |, ^, &&, etc.).

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:

Nybbles image

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.

D. Submission

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