## 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`