-
Notifications
You must be signed in to change notification settings - Fork 22
/
DivideTwoNumbersWithoutUsingDivisionOperator
81 lines (67 loc) · 2.66 KB
/
DivideTwoNumbersWithoutUsingDivisionOperator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/*
Question: Given dividen and divisor, return the quotient without using / operator
Solution Source:
http://www.prasannatech.net/2009/01/division-without-division-operator_24.html
http://www.careercup.com/question?id=5647672717344768
ALGORITHM:
For the sake of completeness, I would like to highlight the algorithm, which is quite simple.
Before that one should understand some basics of bit shifting.
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 would be to
left shift (multiply by 2) the divisor till it reaches dividend/2, then continue this routine with the
difference between the dividend and divisor and divisor till the point where dividend is less than divisor
or their difference is zero. This is similar to finding an element in a sorted list using the binary search
algorithm, the Java code is furnished below.
VERY IMP NOTE: With modifications in the main method as mentioned in the below program,
the program does work for negative numbers also.
*/
package DivideTwoNumbersWithoutUsingDivisionOperator;
import java.util.Scanner;
public class UsingShiftOperators {
static int divident;
static int divisor;
static int remainder;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
try{
System.out.println("Enter the divident and divisor respectively");
divident = in.nextInt();
divisor = in.nextInt();
int ans = getQuotient(Math.abs(divident),Math.abs(divisor));
if((divident>0&&divisor>0)||(divident<0&&divisor<0))
System.out.println(ans);
else if(((divident>0&&divisor<0)||(divident<0&&divisor>0)))
System.out.println(-ans);
}
finally{
in.close();
}
}
private static int getQuotient(int tempDivident, int tempDivisor) {
int quotient = 1;
if(tempDivisor==tempDivident){
remainder = 0;
return 1;
}
if(tempDivisor > tempDivident){
remainder = tempDivident;
return 0;
}
while(tempDivident >= tempDivisor){
/* Here divisor <> divisor and quotient */
tempDivisor=tempDivisor<<1; // Multiply by 2
quotient=quotient<<1;
}
/* We have reached the point where divisor > dividend, therefore divide divisor and quotient by 2 */
tempDivisor=tempDivisor>>1; // Divide by 2
quotient=quotient>>1;
/* Call division recursively for the difference to get the exact quotient */
return quotient+getQuotient(tempDivident-tempDivisor, divisor);
}
}
/*Analysis:
If n = dividend and m = divisor, then
Time Complexity = O(lgn) where n = dividend
Space Complexity = O(1)
*/