How to solve A + B problem
Description
Write a function that add two numbers A and B without using the arithmetic operator ‘+’ and considering using the bit operation.
Steps of solving the problem
Since the problem requires us to use the bit operation, we would need to get familiar with the bit operation knowledge, this is starting point. Let’s choose Javascript for example, by doing a basic google search, we could find out the JavaScript Bitwise Operations — https://www.w3schools.com/js/js_bitwise.asp
Now let’s do some experience. Let’s start with a simple example, do a calculation of 1 + 2. Now firstly convert the number into binary format, now 1 becomes 001 and 2 becomes 010. ok, now 1 + 2 = 3, then what, 3 is 011. Now let’s see what are the bit manipulation of 001 and 010 to 011
You can find out the operation between 1 and 0 is 1, the operation 0 and 0 is 0. That means, the operator OR, XOR are satisfying the solution. Now let’s considering another simple example — 1 + 1
We can find out that the operation between 1 and 1 will become 0, but we also notify that there is carry, but we will consider that later. In this case, let’s summarize the observation
By looking through the chart, now only XOR satisfies the solution.
Now we have a good starting point, with the XOR operator we could get part of the answer. Now let’s consider the second question. How about the carry? A normal thought is that I need to get the carry and save it after the operation. The carry behavior is that when operating 1 and 1, we will get 1 and we will shift to left with one position. For another combination, we will get 0.
Ok, searching operator list again and we will find out that the AND operator satisfies our need.
So now we can get to the next level of the solution -
Let’s assume that we have a and b as the input.
1. Do the XOR between a and b, now get the answer c;
2. Do the AND between a and b, and do a one-bit left shift, get the answer d;
3. Do the XOR between c and d …
Now what? Seems that there may be another round if there is still carry. So what is the end condition? And actually, this will lead to our destination :) And as we analyze, we can know that if there is still carry, we will continue; In another word, if there is NO carry, we are done. Let’s continue our algorithm -
1. Do the XOR between a and b, now get the answer c;
2. Do the AND between a and b, and do a one-bit left shift, get the answer d;
3. Do the XOR between c and d, now get the answer e;
4. Do the AND between c and d, if there is carry (c & d is 1), keep repeating 1 to 3; If no carry, now the answer is e.
Let’s write the pseudocode -
Now coming to the final steps, since we have repeatable steps, we could convert that in the loop. To convert to a loop, we would need to consider how to reuse the variable to save some temp variable. Here we observe that c will become a and d will become b in the next round. And we will use d to determine if the loop is ended.
ok, let’s improve the pseudocode -
So now let’s test the logic in Javascript and it works!
