It is Thursday in the Twin Cities of Minneapolis and St. Paul and the sun is shining. Later this afternoon my wife and I will go walking for an hour. Not too many days left before it gets really cold and start to snow.
After doing the last HackerRank challenge which was rated easy I decided to go back to the “Cracking the Coding Interview” book by Gayle Laakmann McDowell and start tackling the hard problems listed in chapter 17 of the book.
I started on the white board. I then moved to the Eclipse IDE, and after my approach was working I took a look at the solution in the book. I found very interesting the proposed solution. I learned something that I did not know and probably most developers do not. Not sure when would you like to add two numbers without having to use the plus operator which all compilers map to the add assembly language operator.
Let me start by showing the test scaffolding that I wrote for this problem.
/*
* Test scaffolding.
*/
public static void main(String[] args) {
// // **** open scanner ****
// Scanner sc = new Scanner(System.in);
//
// // **** read values to sum ****
// int a = sc.nextInt();
// int b = sc.nextInt();
//
// // **** close scanner ****
// sc.close();
// **** generate two random integers within the specified range ****
Random rand = new Random(System.currentTimeMillis());
int a = Math.abs(rand.nextInt() % 100000);
int b = Math.abs(rand.nextInt() % 100000);
// ???? ????
System.out.println("main <<< a: " + a + " b: " + b);
// **** for future reference ****
int s = a + b;
// // ???? ????
// System.out.println("main <<< s: " + s);
// **** build sum map ****
buildSumMap();
// // ???? ????
// System.out.println("main <<< sm: " + sm.toString() + "\n");
// **** ****
int sum = 0;
// **** sum values ****
sum = sumValues(a, b);
// **** compare results ****
if (s == sum)
System.out.println("main <<< sumValues sum: " + sum + " == s: " + s);
else
System.err.println("main <<< sumValues sum: " + sum + " != s: " + s);
// **** add values ****
sum = addValues(a, b);
// **** compare results ****
if (s == sum)
System.out.println("main <<< addValues sum: " + sum + " == s: " + s);
else
System.err.println("main <<< addValues sum: " + sum + " != s: " + s);
}
I started by using the Scanner class to read the values to add. I was simple to enter a couple numbers and then try the main method which adds them. Shortly we will see some executions which illustrate this approach.
After I was done it was easier to test by clicking on the “Run Solution” icon to execute the program in the IDE and not having to enter a couple integers. For that I just had the program generate a couple positive integers in the specified range.
As usual the comments // ???? ???? indicate a debug statement. I left the one that displays the numbers to make sure all was well. The program then computes the sum by using the plus ‘+’ sign. This is done to check if the method returns the same result.
Form my approach I wrote the buildSumMap() method. It generates a hash map that we will use in the sumValues() method to produce the sum. Will provide more detail on the method in a few paragraphs.
I then verify that the actual sum matches the value returned by the method.
After my approach was completed and tested, I wrote the addValues() method to experiment with it. It seems to work well. It is simpler but you need some background that does not seem to be common knowledge. As I mentioned before, I learned something new.
4 7 11 123 456 579 9 1 10 99 1 100 999 1 1000
In these tests I manually entered the two numbers to add and executed the program. It was good enough while I was working on my solution. After I was done I switched to the following:
main <<< a: 1737 b: 1727 main <<< sumValues sum: 3464 == s: 3464 main <<< addValues sum: 3464 == s: 3464
I still display the numbers but I do not enter them. The program selects two random numbers and runs the methods. Initially I run just my method. After reading the solution, implementing and experimenting with it, I modified the test to run both methods.
// **** global sum map ****
static HashMap<Integer, ArrayList<Integer>> sm;
/*
* Build sum map.
*/
static void buildSumMap() {
// **** create the sum map ****
sm = new HashMap<Integer, ArrayList<Integer>>();
// *** populate the hash map ****
int a = 0;
int b = 0;
int c = 0;
for (int key = 0; key < 8; key++) { // **** set a, b and c **** a = key & 0x01; b = (key >> 1) & 0x01;
if (key <= 3)
c = 0;
else
c = 1;
// // ???? ????
// System.out.println("buildSumMap <<< key: " + key + " c: " + c + " b: " + b + " a: " + a);
// **** set sum and carry ****
ArrayList<Integer> value = new ArrayList<Integer>();
value.add((c + a + b) & 0x01); // [0] sum
value.add(((c + a + b) >> 1) & 0x01); // [1] carry
// **** save sum and carry ****
sm.put(key, value);
}
}
I decided to emulate the way CPUs operate. They tend to perform additions shifting registers. Thinking on this I created the specified hash map holding all the possible states when a carry, a and b bits are added. We have four possibilities without a carry bit and other four with the carry bit set.
I used an array list to hold the sum and the resulting carry bit for each of the eight possibilities.
/*
* Sum values without using a plus sign.
*/
static int sumValues(int aa, int bb) {
// **** simple checks ****
if ((aa == 0) && (bb == 0))
return 0;
if (aa == 0)
return bb;
if (bb == 0)
return aa;
// **** for starters ****
int sum = 0;
// **** loop until no more bits are left to process ****
int a = 0;
int b = 0;
int c = 0;
int shiftCnt = 0;
while (!((aa == 0) && (bb == 0))) {
// **** extract a and b ****
a = aa & 0x01;
b = bb & 0x01;
// // ???? ????
// System.out.println("sumValues <<< c: " + c + " b: " + b + " a: " + a);
// **** build key ****
int key = c << 2 | b << 1 | a;
// // ???? ????
// System.out.println("sumValues <<< key: " + key);
// **** look up key in hash map to get sum and carry ****
ArrayList<Integer> value = sm.get(key);
// // ???? ????
// System.out.println("sumValues <<< value: " + value.toString());
// **** update sum ****
sum <<= 1;
sum |= value.get(0);
// **** update carry ****
c = value.get(1);
// // ???? ????
// System.out.println("sumValues <<< sum: " + sum + " c: " + c); // **** to process next bits **** aa >>= 1;
bb >>= 1;
// **** count this shift ****
shiftCnt++;
// // ???? ????
// System.out.println("sumValues <<< aa: " + aa + " bb: " + bb + " shiftCnt: " + shiftCnt + "\n");
}
// // ???? ????
// System.out.println("sumValues <<< sum: " + sum + " c: " + c);
// **** ****
sum <<= 1;
sum |= c;
// // ???? ????
// System.out.println("sumValues <<< sum: " + sum); // **** invert bits **** int temp = sum; sum = 0; for ( ; shiftCnt >= 0; shiftCnt--) {
sum <<= 1; sum |= temp & 0x01; temp >>= 1;
}
// **** return sum ****
return sum;
}
The sumValues() method performs some simple checks to avoid executing the code on some specific cases.
Note that I left in the source code several debug statements. In production I would delete most of them. In general you typically want to have a mechanism to enable log statements.
Let’s get back to the code. We initialize the sum which holds the result for this method. We initialize some variables and enter a loop.
We build a key to look for a value in the hash map. The key defines one of the eight possible conditions. We then look up the value in the hash map.
We compute the sum by shafting the sum variable and copying in the lowest bit the sum of the carry, a and b bits. We then update the value of the resulting carry bit.
We shift the input values to get ready to process the next set of bits. We count the number of shifts we are making. This information will be required later on
After we complete processing all the bits we shift the sum once more to set the last carry bit.
Note that we have been operating from the less significant bit up to the most significant. This is the normal way we perform a sum. CPUs perform all bit additions simultaneously. There are many gates involved per bit.
To get to the result we need to change the order of the bits. We update the sum by copying its value to a temp variable and then shifting it to reverse the order. When done we just return the sum of the two values.
This code seems to work as expected. The following method is the one from the book.
/*
* Simple way to add two values.
* Recursive method.
* Stop recursion when there is nothing to carry.
* Need to know this method.
*/
static int addValues(int ss, int cc) {
// **** stop when there is nothing to carry ****
if (cc == 0)
return ss;
// **** add without carry (XOR) ****
int sum = ss ^ cc;
// **** carry but do not add (shifted AND) ****
int carry = (ss & cc) << 1;
// **** add the sum and carry (must be in this order) ****
return addValues(sum, carry);
}
The addValues() method is recursive. It works based on the concept of splitting the sum without carry by using an XOR operation and adding to it the shifted AND of the bits which represents the carry bits. By adding them until the carry reaches zero we are able to compute the sum of the two values.
I spent time figuring out and testing the approach. It seems to work well. You need to have learned this before hand in order to use the approach for this question. Remember that all CPUs are able to add.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.
Keep on reading and experimenting. It is the best way to learn and refresh your knowledge!
John
Follow me on Twitter: @john_canessa