## Thursday, February 9, 2012

### C program to multiply, divide and find reminder for x by 4 without arithmetic operators?

One of my friends asked me an interesting interview question. The question is like this: How to multiply, divide and find reminder of a number X by 4 without using arithmetic operators?

Since we are not supposed to use arithmetic operators, none of the +,-,*,/% can be used. Binary operators always help us in this regard.

The solution is:
```#include<stdio.h>
int main()
{
int x=25;
int y;
printf("x is : %d\n",x);
printf("x mul by 4 :%d\n",x<<2);
printf("x div by 4 :%d\n",x>>2);
printf("x mod  4 :%d\n",x&3);
return;

}
```
The result is:
```#./a.out
x is : 25
x mul by 4 :100
x div by 4 :6
x mod by 4 :1
```
Let us see how we got this:

1. Multiply a number by 4:  When we left shift(<<) a number once, the number gets multiplied by 2. When we left shift the number twice, it gets multiplied by 4.

2. Division of a number by 4:  Same as multiply, only difference being instead of left-shift, we use right shift for division(>>).

3. Reminder of a number by 4: This is little interesting. Let us see the binary representation of some of the numbers:
`0 - 00001 - 00012 - 00103 - 00114 - 01005 - 01016 - 01107 - 01118 - 10009 - 1001`
If you look at the above binary numbers carefully, you can draw a conclusion. The last 2 bits indicate the reminder of that number by 4.  Isn't it? Reminder of 4/4 is 0(00), 5/4 is 1(01), 6/4 is 2(10) and so on. So, its simple. All we need to do is mask the first 2 bits to get the reminder and hence we do a bitwise ANDing by 3(0011).

Happy learning!!! 