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