Write a function that adds two numbers You should not use + or any arithmetic operators.

**My initial thoughts:**

We should take care of two things: adding and carry. Addition can be done using XOR(^). Carry can be done using AND(&). The only tricky part is that when we have two bits like 1 and 0 but then we have carry from previous position, then 1 & 0 = 0 suggests no carry but actually 1 + 0 + 1 will produce a carry. So we branch into two case: 1 + 1 will definitely produce a carry no matter what; 1 + 0 + 1 will produce new carry.

**My initial codes:**

public static int add(int a, int b) {
int result = 0;
int carry = 0;
for (int i = 0; i < Integer.SIZE; ++i) {
int bitIAtA = a & (1 << i);
int bitIAtB = b & (1 << i);
carry &= (1 << i);
result |= bitIAtA ^ bitIAtB ^ carry;
carry |= ((bitIAtA & bitIAtB) << 1 | ((bitIAtA ^ bitIAtB) & carry) << 1);
}
return result;
}

**Solution:**

To investigate this problem, let’s start off by gaining a deeper understanding of how we add numbers. We’ll work in Base 10 so that it’s easier to see. To add 759 + 674, we would usually add digit[0] from each number, carry the one, add digit[1] from each number, carry the one, etc. 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 we decided to split apart the “addition” and “carry” steps. That is, we do the following:

- Add 759 + 674, but “forget” to carry we then get 323
- Add 759 + 674 but only do the carrying, rather than the addition of each digit. We then get 1110
- Add the result of the first two operations (recursively, using the same process de- scribed in step 1 and 2): 1110 + 323 = 1433

Now, how would we do this in binary?

- If we add two binary numbers together but forget to carry, bit[i] will be 0 if bit[i] in a and b are both 0 or both 1. This is an XOR
- If we add two numbers together but only carry, we will have a 1 in bit[i] if bit[i-1] in a and b are both 1’s. This is an AND, shifted
- Now, recurse until there’s nothing to carry

public static int add_no_arithm(int a, int b) {
if (b == 0)
return a;
int sum = a ^ b; // add without carrying
int carry = (a & b) << 1; // carry, but don't add
return add_no_arithm(sum, carry); // recursion
}

### Like this:

Like Loading...

*Related*