**- How to add two numbers without using the + plus operation?**

**- How to multiply two numbers without using the**

`*`

?As we cannot use the `+`

operator, we probably have to use the intrinsic
computer operators: the binary operators, but first, take a look at an
addition. We know numbers have to be added from the right to the left without
forgetting to count the carry.

```
874
+ 459
-----
1333
```

If we decompose the operation of the addition and the carry, we get:

```
874
+ 459
-----
223 (a) addition without carry
+1110 (b) carry
```

If we get `(a)`

and `(b)`

, we can apply recursively the same process by
supposing the carry would eventually be null:

```
223
+1110
-----
1330 (a)
0 (b) carry
```

How can we achieve that in binary? The addition without the carry can be obtain
by a `XOR`

and the carry is only a `AND`

with a shift on the left. Here is an
example:

```
9 1001
^ 5 0101
---------
12 1100
```

```
9 1001
& 5 0101
---------
0001
```

```
9 1001
+ 5 0101
-------------
9^5 1100
(9&5)<<1 0010
-------------
1110
```

Our basis case is when additionning `a`

and `b`

if `b`

is equal to `0`

then
the result is `a`

.

C++ implementation:

```
int add(int a, int b) {
if (b == 0) return a;
return add(a^b, (a&b) << 1);
}
```

To multiply two numbers `a`

and `b`

, we start by multiplying the first digit on
the right of `b`

with `a`

. Then we multiply the second digit with `a`

but with a
shift on the left.

```
26 (a)
* 13 (b)
-----
78
+ 260 (26 * 1) << 1
-----
338
```

We will proceed the exact same way but in base two. Hence if the digit of `b`

is
1, we can add `a`

then we shift for the next result. As we have to know if `b`

is equal to 0 modulo 2, we shift `a`

instead of `b`

and we remove the last digit
of b by shifting on the right.

```
int mult(int a, int b) {
if (a == 0 || b == 0) return 0;
if (b == 1) return a;
int result = 0;
while (b != 0) {
if (b&1) {
result = add(a, result);
}
a = a << 1;
b = b >> 1;
}
return result;
}
```

Finally, we didn't need too much instructions to achieve our goal!

## References:

- Cracking the coding interview - Gayle Laakmann