In bits we trust

November 28, 2016

pic


- 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