FilesExpand file tree

 master

/

029_DivideTwoIntegers29.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

37 lines (33 loc) · 1.02 KB

 master

/

029_DivideTwoIntegers29.java

Copy path

Top

File metadata and controls

• Code
• Blame

37 lines (33 loc) · 1.02 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/**

* Divide two integers without using multiplication, division and mod operator.

*

* If it is overflow, return MAX_INT.

*/

public class DivideTwoIntegers29 {

public int divide(int dividend, int divisor) {

if (divisor == 0) return Integer.MAX_VALUE;

if (dividend == 0) return 0;

long result = helper(dividend, divisor);

return result > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) result;

}

public long helper(long dividend, long divisor) {

boolean isNegative = dividend < 0 != divisor < 0;

dividend = Math.abs(dividend);

divisor = Math.abs(divisor);

if (dividend < divisor) return 0;

long res = 0;

while (dividend >= divisor) {

long t = divisor;

long p = 1;

long tt = t << 1;

while (dividend > tt) {

t = tt;

p <<= 1;

tt <<= 1;

}

res += p;

dividend -= t;

}

return isNegative ? -res : res;

}

}