division without division operator

[nitin1]

i have to do division without divison/multiplication/mod operator. how can i ?

 int divide(int dividend, int divisor) {

        int p=1;

        if(dividend<0)
        {
             p*=-1;
             dividend*=-1;
        }

        if(divisor<0)
        {p*=-1;
           divisor*=-1;
        }

        while(dividend>=divisor)
        {
             dividend-=divisor;
        }

        return dividend*p;

    }

i have done this, but this giving time limit exceeded when input is 1234567890,1. how can i do it efficiently ?

[Ancient Dragon]

you can divide by subtraction. Try out a few examples using pencil & paper to find out how its done. Or read this tutorial

[deceptikon]

i have to do division without divison/multiplication/mod operator.

Yet another dumb assignment that serves no purpose in reality. Can't educators think of more practical exercises?

[nitin1]

@ancient dragon please read my last line. it is giving time limit excedded. so i want any other effiecent way.

@deceptikon lol. it's not a assignment. It is asked by facebook this year in the first round ;) so i think it is not that much bad question like you thinking it ;)

[pritaeas]

time limit exceeded when input is 1234567890,1

Dividing by 1 is not very smart indeed. Add a check, if the divisor equals 1, return the dividend. No need to do 1234567890 loops.

[Gonbe]

Hmm bit-wise operators don't seem to be blacklisted. You could implement binary long division with them.

[deceptikon]

so i think it is not that much bad question like you thinking it ;)

Nope, it's still a bad question. Unfortunately, employers and the like have this annoying tendency to pick up stupid trivia and techniques that haven't been productive since the 50s. They're hardly viable as measures of one's knowledge or skills, but it is what it is.

I agree with Gonbe though, the expected solution is highly likely to involve bit twiddling.

[nitin1]

hmm sir! you are right! but what can we do in this if facebook like thing is still asking these type of questions ? :-| SO can you help how bit wise operators are helping in this ?

[deceptikon]

I'll post something substantial when I have a bit more time, assuming someone else doesn't beat me to the punch.

[deceptikon]

Here's one possible example of using bitwise operators for this:

int divide(int dividend, int divisor)
{
    unsigned long lhs = dividend;
    unsigned long rhs = divisor;
    int result = 0;

    if (rhs == 1)
        return lhs;

    while (lhs > rhs) {
        unsigned long quotient = 1;
        unsigned long sub = rhs;

        while ((sub << 1) <= lhs) {
            quotient <<= 1;
            sub <<= 1;
        }

        result += quotient;
        lhs -= sub;
    }

    return result + (rhs == lhs);
}

I'll leave optimization and handling of negative numbers to you.

[Delnith]

If I'm not mistaken, you could put your data into a look and subtract that value by the number of times you wish to divide by. Ex/ 25/5 = 25-5 5 separate times. Something like that could very easily work.

[somjit{}]

@nitin1

the division by substraction seemed pretty straight forward.. atleast for non complicated cases with small inputs. this is a simple code i came up with just sitting down with a pencil n paper ..

 #include<stdio.h>


    int main()
    {
        int divsr,divden,i=0,rem=0;
        divden=30;
        divsr=5;
        printf("before division:\n");
        printf("divident: %3d   quotient:%3d\n",divden,i);

        printf("now dividing...\n\n");
        while(divden>divsr){

            divden-=divsr;
            ++i;
            printf("divident: %3d   quotient:%3d\n",divden,i);
        }
        if((divden<divsr)&&((rem=divden)>0)){
            printf("\nafter division:\tdividend:%3d divisor:%3d quotient:%3d remainder:%3d\n",((i*divsr)+rem),divsr,i,rem);
        }
        else if((divden==divsr)){
            divden-=divsr;      // eliminates the off by one error
            ++i;        
            printf("%3d is completely divisible by %3d, remainder: 0   quotient :%3d\n",((i*divsr)+rem),divsr,i);
        }   
        return 0;
    }

u can replace the "divdn=30" lines with a printf()-scanf() pair easily.
hope it helps. :)

[somjit{}]

put a BIG dividend in the above code, in terms of Million, and a small divisor, and the thing takes forever!!!
the only thing positive from this code , to me, is i got a sense of the rate of while loop operations.. 42 thousand loops in around 8-10 secs...(i gave up after that.. the feeling i got while the program ran was very unsettling).

facebook apparantly wanted the bitwise operator division method...