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 - 0000
1 - 0001
2 - 0010
3 - 0011
4 - 0100
5 - 0101
6 - 0110
7 - 0111
8 - 1000
9 - 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!!!

Tweet