Homework 2: Bit Operations, Pointers, Linked Lists

Consider this HW a pretty mature beta. Report any errors directly to Josh: hug@cs.berkeley.edu.

In this assignment, we will implement a basic calculator using bitwise operators. This calculator will maintain a history of calculations which we can operate on as well. You will find some skeleton code available to you, and you are free to add any additional methods and fields you think will be helpful.

Unfortunately, the staff procrastinated on creating this homework assignment and wrote the calculator code in a hurry! In their rush, your TAs wrote a pretty buggy adder.

Your task is to write a minimum of 3 JUnit tests to test the addition code in the staff calculator in the included CalculatorTest.java skeleton. At least one of the tests must fail on the StaffCalculator, i.e. should catch a bug in the staff implementation of the adder. Of course, one silly way to induce a test failure is to write a broken test (3 + 2 = -187921). Don't do this! Instead, you'll need to come up with powerful enough simple tests that are able to find the bug in StaffCalculator.

Note that you have no idea what the implementation looks like. This is a good thing! We're treating the add method of StaffCalculator as a mysterious black box that adds numbers. There's no need to know what is inside to write good tests.

The method signature for addition is:

public int add(int x, int y)

Throughout this course, we encourage you to write tests for every method you write, ideally even before you start the implementation of that method. In later assignments, you'll be free to do less rigorous testing, but for now, we want to show that it's not so bad.

By completing this task, you've already written tests that you can use on your calculator implementation (coming later in this assignment). To test your own implementation, read the comments in the setUp() method of CalculatorTest.java.

In this part of the assignment, you will implement the addition functionality of a calculator. Write the add function, which takes in two integers and computes their sum. You are not allowed to use any of the standard math operators, i.e. +, -, /, *, %, ++, --, +=, -=, *=, /=, %=, or any equivalent method calls. Instead, use the bitwise operators &, |, ^, ~, <<, >>, >>>, etc. The one exception: if you choose to use a loop, you may use one standard math operator to increment the loop counter.

This may sound like a trivial task at first, but you'll find that it is actually a rather challenging puzzle. We encourage you to discuss strategies with other students. Most (all?) sensible solutions require some sort of loop. You should strive for clarity over concision. You may find it useful to create a helper method (but this is not required, and the most elegant solutions do not call for one).

Hint 1: Try working out a small example with a truth table of the addition on paper first before translating it into code.

Hint 2: Don't bother thinking about negative numbers at first. Chances are that any solution that works for positive numbers will automatically work for negative ones.

Your function should be located in the Calculator class with the following method signature:

public int add(int x, int y) {
}

Task 3: Multiplying with Bit Operations

Similar to the previous part, you will implement the multiplication functionality of a calculator. Write the multiply function, which takes in two integers and computes their product. As before, you may not use any of the standard math operators +, -, /, *, %, ++, --, +=, -=, *=, /=, %=, or any equivalent method calls. The one exception, as before: if you choose to use a loop, you may use one standard math operator to increment the loop counter. You are allowed to use the add() function you wrote in the previous part, and you should use at least one of the bitwise operators in a non-trivial manner.

Before you begin, write tests. The staff solution will fail some of these tests because of its dependence on the buggy add() function.

Your function should be located in the Calculator class with the following method signature:

public int multiply(int x, int y) {
}

Hint: Try to get multiplication to work where y is a power of 2 first. Once you have that working, think about how you can get it to work with all integers.

MORE FOR MASTERS

This is an optional task for those of you who want a greater challenge. In this task, we'll learn how to process input from the user. We will not provide official support for this task in OH or Piazza, though if things aren't too busy we'll be happy to answer questions. If you are skipping this challenge, click here. There is no shame in skipping this!

Create a new file CalculatorUI.java. Create a user interface for your Calculator by implementing the main method in CalculatorUI shown below:

public static void main(String[] args) {
while (true) {
}
}

This method should prompt the user with a > symbol to enter a command and respond as follows:

Example run:

> 1 + 2
3
> 3 * 4
12

Your calculator only needs to be able to support expressions containing exactly one arithmetic operator.

a + b

Adds a and b together. Note that this expression is entered in by the user as a String. You will need to find some way of extracting out the integer corresponding to a and b. For simplicity, you may assume that there will always be exactly one space between a, +, and b. You may also assume that there will be no space between a negative sign and the corresponding integer.

For example:

1 + - 2  // Invalid expression.  (Space between - and 2)
1 + -2   // Valid expression.
1 + --2  // Invalid expression.  (We will not allow double negative signs)
a * b

Like above, but multiplies a and b together.

quit

Exits the calculator. This means that you should not prompt the user for more input.

StdIn

To get input from the keyboard, you should use StdIn from the Princeton standard library. It is similar to the In class that you used in HW1, but takes input from your operation system's 'standard input' instead of from a file. Think of standard input as a hose running from your operating system into your program. The OS can deliver information from any source via standard input. By default, this source is from the keyboard.

Since this is an extra challenge, we will not explain StdIn in this document. See the StdIn JavaDocs and StdIn documentation for written directions, or this StdIn demo for a video tutorial. You might also find the examples in the examples directory useful.

It is OK if your code crashes on invalid expressions. We will discuss handling errors later in the course.

Compile and run StaffCalculatorUI (or CalculatorUI if you created your own). Try typing expressions that involve only a single + or * sign and you should see results like the following. This UI is very limited and cannot handle longer expressions or real numbers.

> 1 + 2
3
> 3 * -4
-12

We'll now add the ability to print the history of equations that have been entered, along with the result, with the most recent equation first. This command will print one equation (along with its result) on each line. Note that only equations should be stored; do not store other commands such as "sum", "history", etc.

Here is an example run:

> 1 + 2
3
> 3 * 4
12
> history 1
3 * 4 = 12
> dump
3 * 4 = 12
1 + 2 = 3

The dump command prints all entries in the history. The history command prints the n most recent equations. Tasks 5A-5C provide a recommended sequence for implementing this functionality.

Task 5A: Implementing the History Data Structure

To support the command above, we need to store: (1) a history of equations that were run, and (2) their corresponding results. You may assume that (1) will be an equation represented as a String, and (2) will be an integer corresponding to the result.

The data structure we will use is the EquationList class you will find under the list directory. This is similar to the linked list that was covered in lecture, and the diagram below shows an example of its use. You are not allowed to use any of Java's built-in list structures.

+-------------------+    +-------------------+
| EquationList      |    | EquationList      |
+-------------------+    +-------------------+
| equation: "1 + 2" |    | equation: "3 * 4" |
| result:   3       |    | result:   12      |
| next:     --------+--->| next:     null    |
+-------------------+    +-------------------+

Write the saveEquation method in Calculator. You will need to add at least one member variable to the Calculator class. You may create a constructor, but you are not required to do so.

public void saveEquation(String equation, int result) {
}

Fill in the printHistory(int n) and printAllHistory() commands.

Hint: One of these methods is a special case of the other. Can you write that method without copying-and-pasting your code?

public void printHistory(int n) {
}

public void printAllHistory() {
}

Optionally, you may write tests to ensure your saveEquation and printHistory methods work. Alternately, you may proceed to task 5C and use that for testing instead. Generally, I do not recommend performing system-level tests of basic functionality, but since this system is so simple, it is not too unreasonable in this case.

If you're creating CalculatorUI, modify your main method so that it properly handles the history and dump commands. Otherwise, you may want to look inside StaffCalculatorUI to see how and where the methods you wrote in this task are being used.

We will next add an undo command that will allow us to remove the most recent entry from our history, and a clear command that will allow us to clear our entire history.

clear

Clears all entries in history. Subsequent runs of history should not print anything to the terminal, since every entry in history has been removed.

undo

Removes the most recently entered equation from history. All other entries in history should remain unchanged.

For example:

> 1 + 2
3
> 3 * 4
12
> 8 * -2
-16
> dump
8 * -2 = -16
3 * 4 = 12
1 + 2 = 3
> undo
> dump
3 * 4 = 12
1 + 2 = 3
> clear
> dump
>

Your code that performs the undo and clear operations should be added to undoEquation() and clearHistory() respectively.

If you created your own CalculatorUI, update your main method to support these new commands.

Our market research team has discovered that our Calculator users are clamoring for a bizarre feature: for this final part of the assignment, we will implement commands sum and product that will compute the sum and product respectively of all equations in the history.

sum

Computes a sum over the result of each equation in history. If there are no equations, we will return a sum of 0.

For example, if we again have 1 + 2 and 3 * 4 in our history, you should output: (this is computed as (1 + 2) + (3 * 4))

> sum
15

product

Computes a product over the result of each equation in history. If there are no equations, we will return a product of 1. Using the same example as before, you should output: (computed as (1 + 2) * (3 * 4))

> product
36

The code that implements these keywords should be in cumulativeSum() and cumulativeProduct() respectively.

If you created your own CalculatorUI, update your main method to support these new commands.

More for Masters

If you still haven't had enough, here are some more things you might try:

• "Bulletproof" your calculator. Assume that the TA grading your program will attempt to run malformed input - for instance, 1 + (which is invalid because it's missing the second argument), or insert extra spaces to confuse the calculator - for instance, history or 1 + 2. Make sure that your calculator gracefully rejects the first case, and accurately handles the second case. You may continue to assume that there will be no spaces separating a negative sign with the corresponding integer.
• Support nested expressions.

Submission Instructions

To recieve feedback from the autograder via email, push to the ag/hw2 branch, following the directions from lab 1.

To submit, push to the submit/hw2 branch, following the directions from lab 1. Alternatively, refer to this cheatsheet on Piazza.