Multiplication in C without arithmetic operators

Question

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

Answer 1

void main() { int n1, n2, n3, n4, x, y, i; printf("Enter first number"); scanf("%d", &n1); printf("Enter second number"); scanf("%d", &n2); n3 = n2; n4 = n2; n1-=1; for(i = n1;i > 0;i-=1) { do { x = n2 & n3; y= n2 ^ n3; n2 = x << 1; n3 = y; } while (x); n2 = y; n3 = n4; } printf("product of two number is %d", y); getch(); } 

Answer 2

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

For example, adding can be achieved using this method.

 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 this is the question of doing the multiplication by adding:

 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 does not work yet if b is negative, but since this seems like a home problem, I will leave this as an exercise for you.;)

Edit: Although multiplication is intuitive after adding, the add function is not so easy to understand, so I will explain it here.

Say you want to add two numbers, 11010011 and 10101. The usual way to do this is to align them like this:

 11010011 + 10101 

You will notice that when you add two binary numbers, if the i-th bit of both numbers is 1, then the resulting bit is 0, and the bit is transferred to the bit to the left of i.

This wrapping is what the 'c' variable holds in code.

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

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

Then you can see the bits where a and b are different from each other, that is, one of the bits is 1 and the other bit is 0. The resulting bit in this case will be 1 without transfer.

what this line stores:

 b = b ^ a; 

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

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

First, consider where we are, with an example after the first iteration of the loop

 c = a = 00100010 b = 11000110 

This may not be obvious, but b accumulates the amount received. After more iterations of the loop, more bits that are carried are “added” back to b, and transfers are stored again in c. In this sense, you can think of the xor operator as adding operations without hyphenation.

Here is the second iteration of this loop:

 c = a = 00000010 b = 11100100 

3rd iteration:

 c = a = 00000000 b = 11100110 

Now c (and a) is 0, so you no longer need to add. We exit the loop and return b. Please note that even if you continue the cycle, none of the numbers will change.

Answer 3

Maybe check out this wiki for directions: http://en.wikipedia.org/wiki/Binary_multiplier

Answer 4

Yes it is possible. You can do this using logical operators. In the end, everything that the hardware does when using the arithmetic operator.