multiplication in C without arithmetic operators

Question

Is it possible to multiply two numbers with out using arithmetic operators using C? Using the left shift operator, I can multiply any number by 2 only. How about other numbers?

Answer 1

To solve this problem, the first thing you want to do is figure out how to get simple arithmetic operations using just bitwise operators.

For example, addition can be achieved using this technique

int add(int a, int b) {
   int c;
   while (a != 0) {
      c = b & a;
      b = b ^ a;
      c = c << 1;
      a = c;
   }
   return b;
}

Then it's a matter of doing multiplication using addition:

int mult(int a, int b) {
   int i = 0;
   int c = 0;
   while (i < b) {
      c = add(c, a);
      i = add(i, 1);
   }
   return c;
}

This multiplication doesn't yet work if b is negative, but since this looks like a homework problem, I'll leave that as an exercise for you. ;)

Edit: While multiplication is intuitive once you have addition, the addition function is not so easy to understand, so I'll explain it here.

Let's say you want to add two numbers, 11010011 and 10101. The usual way to do it is to line them up like so:

11010011
 + 10101

You'll notice that when you add two binary numbers, if the ith bit from both numbers is 1, then the resulting bit is 0, and there is a carry over to a bit to the left of i.

This carry is what the variable 'c' in the code stores.

//...
c = b & a;
//...
c << 1;
//...

We bit wise and b and a to get only the bits where both a and b are 1, then we left shift it by 1 to get the carry bits.

Then you can look at the bits where a and b differ, i.e. one of the bits is 1 and the other bit is 0. The resulting bit in this case will be 1 with no carry.

that's what this line stores:

b = b ^ a;

The line above essentially removes the bits where both a and b are 1 (now stored in c).

So now you have another two numbers b and c, that you need to add together.

First let's look at where we're at with the example after the first iteration of the loop

c = a = 00100010
    b = 11000110

It might not be entirely obvious yet, but b is accumulating the resulting sum. Through more iterations of the loop, more bits that are carried over are "added" back to b, with carries stored again in c. In that sense, you can think of the xor operator as an addition operation without carry.

Here's the second iteration of that loop:

c = a = 00000010
    b = 11100100

3rd iteration:

c = a = 00000000
    b = 11100110

Now c (and a) is 0, so there is no more carry to add. We exit the loop and return b. Note that even if you continue the loop, none of the numbers will change.

Answer 2

It is possible, see this wiki for a direction: http://en.wikipedia.org/wiki/Binary_multiplier