# In bits we trust

#### November 28, 2016

- 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:

1. Cracking the coding interview - Gayle Laakmann