Homework 5 | CS 61B Fall 2021 Main Course Info Staff Beacon Resources Piazza Navigation Navigation Introduction A. Bit Manipulation B. Implementing a Packed Array: Nybbles.java C. Asymptotic Analysis and A Bit-Twiddling Puzzle D. Submission Homework 5: Bit Operations and Asymptotic Analysis Navigation A. Bit Manipulation B. Implementing a Packed Array: Nybbles.java C. Asymptotic Analysis and A Bit-Twiddling Puzzle D. Submission Introduction 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 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! 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[0] has nybbles 0 through 7, and arr[1] 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. D. Submission 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
