Division Operation without using division operator!!! FAQ in Core Dev Compny Telephonic

 We can use bit logic to reduce the time complexity to O(logn) where n is Quotient

Algorithm will be as follow as we know

1. Left shifting an unsigned number by 1 multiplies that number by 2.
2. Right shifting an unsigned number by 1 divides that number by 2.

Therefore the procedure for the division algorithm, given a dividend and a divisor .
core logic will be to left shift (multiply by 2) untill its greater then dividend , then continue this routine with the the difference between the dividend and divisor and divisor till the point where dividend is less than divisor or their difference is zero.

Lets see one example: dividend=23 divisor=3

then left shift for 3 i.e 3 will converted to3, 6,12,24,… since 12 <23 hence now dividend is 11 and quotient in 4(two time shift operation) now again 3,6,12.. 6<11 hence dividend is 11-6=5 and quotient =4+2=6 now only 3<5 hence remainder =2 quotient =6+1=7 so answer.

Time Complexity O(logn) Number of bits in Quotient

#include
using namespace std;

int dividend,divisor,remainder;
int division(int p,int q){
int quotient=1;
/*if divisor and diviend are equal then quotient=1*/
if(p==q){
remainder=0;
return 1;
}
/*if dividend is smaller than divisor then remainder=dividend*/
if(p dividend*/
while(p>=q){
q<<=1; quotient<<=1; } /*shift right for one time so that divisor become smaller than dividend*/ q>>=1;
quotient>>=1;
/*again call division recurcively*/
quotient+=division(p-q,divisor);
return quotient;
}
int main(){
cout<<"\nEnter dividend:"; cin>>dividend;
cout<<"\nEnter divisor:"; cin>>divisor;
cout<<"\nQuotient:"<<<"\nRemainder:"

}

Time Compelxity O(log(Quotient))
Space Complexity O(1)

(left shift ) one time i.e divide by 2 and if we do <<(right shift) one time i.e multiplied by 2 if we do n times the 2power n time it will do same operation) simultanuosly we are doing left shift for quotient also. Thus we get quotient for that division. After doing this one time again we call the function recursively after subtracting the with remaining numbers.

Lets see one example: dividend=23 divisor=3

then left shift for 3 i.e 3 will converted to3, 6,12,24,… since 12 <23 hence now dividend is 11 and quotient in 4(two time shift operation) now again 3,6,12.. 6<11 hence dividend is 11-6=5 and quotient =4+2=6 now only 3<5 hence remainder =2 quotient =6+1=7 so answer got

Similar  Iterative program for doing the same is


int div(int a, int b)
{
if(!b) return -1;
if(a<b) {
printf("%d / %d = %d , remainder %d\n", a, b, 0, a);
return 0;
}
int q = 1, t=d, d=1;
while (t<a)
{
d=t;
t=t<<2;
q=q<<1;
}
while (d+b<a)
{
d=d+b;
++q;
}
printf("%d / %d = %d , remainder %d\n", a, b, q, a-d);
return 0;
}


A Good Discussion You Can Also Found here Algogeek