Fill in the missing parts (only) of Adder.java without using the operators +, -, /, *, or \%, ++, --, +=, -=, *=, /=, %=, or any method calls. Instead, use the bitwise operators &, |, ^, ~, <<, >>, >>>, and &=, etc. The usual admonition applies: Don't fight the problem!
public class Adder {
/** The value x+y. */
public static int add(int x, int y) {
/* FILL IN */
for (i = 0; i < 32; i += 1) {
/* FILL IN */
}
/* FILL IN */
}
}
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. Let's suppose we have an application that strains our computer's primary memory capacity and need to fit large arrays of these integers into as little space as possible. Specifically, I'd like to be able to store $N$ integers in an N/8 array (packing 8 4-bit integers into each int). Fill in the template below to provide a suitable small-int array type. Do not perform any new operations in the implementation (you may include as many as you want for testing, if you put them in a different file).
/** Represents an array of integers each in the range -8..7.
* Such integers may be represented in 4 bits (called nybbles). */
public class Nybbles {
/** An array of size N. */
public Nybbles(int N) {
// DON'T CHANGE THIS.
data = new int[(N+7) / 8];
this.N = N;
}
/** The size of THIS. */
public int size () { return N; }
/** Return the Kth integer in THIS array, numbering from 0.
* Assumes 0 <= K < N. */
public int get(int k) {
if (k < 0 || k >= N)
throw new IndexOutOfBoundsException();
else
return /* REPLACE WITH ANSWER */ 0;
}
/** Set the Kth integer in THIS array to VAL. Assumes
* 0 <= K < N and -8 <= VAL < 8. */
public void set (int k, int val) {
if (k < 0 || k >= N)
throw new IndexOutOfBoundsException();
else if (val < -8 || val >= 8)
throw new IllegalArgumentException();
else
data[ /* REPLACE WITH ANSWER */ 0 ] =
/* REPLACE WITH ANSWER */ 0;
}
// DON'T CHANGE OR ADD TO THESE.
private private int N;
private private int[] data;
}
For these problems, you should give a brief explanation as part3.txt. You should not use any fancy typesetting tools (like LaTeX, Word, etc.). Just submit a text file. You are not required to explain your solutions, but you are encouraged to do so. Provide simple and tight asymptotic bounds for each of the following. Here, "simple" means roughly "no unnecessary terms or constants" and "tight" means "either the largest $\Omega(\cdot)$ and $O(\cdot)$ bounds you can find, or if possible, a $\Theta(\cdot)$ bound.
int j;
j = 0;
for (int i = 0; i < N; i += 1) {
for ( ; j < M; j += 1) {
if (bump (i, j))
break;
}
}
Assume that M and N are integer constants, and bump
is a constant-time ($O(1)$) method that returns a boolean result.
We're
looking for a $\Theta$ result that uses M and N.
public static int f1 (int n) {
int x = 0;
for (int i = 0; i < n; i++) {
x++;
}
return x;
}
public static int f5 (int n) {
if (n <= 1) {
return 1;
}
return f1(n) + f5(n/2) + f5(n/2);
}
Give your answer as $\Theta$ result that uses n.
These problems will not be graded. Feel free to submit answers, though they won't be examined unless you make a specific request for someone to do so. These problems are intended as particularly challenging problems to reinforce your understanding of asymptotic analysis.