Loading…

Write a function that adds two numbers

 

 

Our first instinct in problems like these should be that we’re going to have to work with bits. Why? Because when you take away the+ sign, what other choice do we have? Plus, that’s how computers do it!

 

Our next thought should be to deeply understand how addition works. We can walk through an addition problem to see if we can understand something new-some pattern-and then see if we can replicate that with code.

 

So let’s do just that – let’s walk through an addition problem. We’ll work in base 10 so that it’s easier to see.

 

To add 759 + 674, I would usually add digit [0] from each number, carry the one, add digit [ 1] from each number, carry the one, and so on. You could take the same approach in binary: add each digit, and carry the one as necessary.

 

Can we make this a little easier? Yes! Imagine I decided to split apart the “addition” and “carry” steps. That is, I do the following:

 

1. Add 759 + 674, but”forget” to carry. I then get 323.

2. Add 759 + 674 but only do the carrying, rather than the addition of each digit. I then get 1110.

3. Add the result of the first two operations (recursively, using the same process described in step 1 and 2):

 

1110 + 323 = 1433.

 

Now, how would we do this in binary?

 

1. If I add two binary numbers together, but forget to carry, the ith bit in the sum will be 0 only if a and b have the same ith bit (both 0 or both 1). This is essentially an XOR.

 

2. If I add two numbers together but only carry, I will have a 1 in the ith bit of the sum only if bits i – 1 of a and b are both ls. This is an AND, shifted.

 

3. Now, recurse until there’s nothing to carry.

 

The following code implements this algorithm.

 int add(int a, int b) {

 if (b == 0) return a;

 int sum = a Ab;// add without carrying

 int carry= (a & b) << 1; // carry, but don’t add

return add(sum, carry); // recurse with sum + carry

 }

 

Alternatively, you can implement this iteratively.

 

 int add(int a, int b) {

 while (b != 0) {

 int sum = a Ab; /I add without carrying

 int carry= (a & b) << 1; II carry, but don’t add a sum;

 b = carry;

 }

 return a;

}

 

Problems requiring us to implement core operations like addition and subtraction are relatively common.

 

The key in all of these problems is to dig into how these operations are usually implemented so that we can re-implement them with the constraints of the given problem.


Leave a Comment