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

## No comments:

## Post a Comment