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

Best method(跟discuss vote最高相似)：只有一種情況整數(shù)除以整數(shù)會overflow，那就是Integer.MIN_VALUE除以-1，這種情況特殊分析。

之所以要用long a, b代替dividend和divisor是因為：比如Integer.MAX_VALUE除以1，第21行的while循環(huán)，1不管怎么右移，因為是整數(shù)，永遠無法比Integer.MAX_VALUE大。所以會一直死循環(huán)。所以被除數(shù)和除數(shù)都用Long型，但是result不能用Long型，因為返回的時候會報錯：原因是損失精度

?

基本思路：long a = dividend, long b = divisor， 商c可以表示為 2^k + 2^m + ....;

a = b * c = b * (?2^k + 2^m + ....) ? = ? ?b*2^k + b*2^m + ...?

b*2^k 表示把divisor b左移k位（即b<<k）, 而且b<<k+1就會大于a，根據(jù)這個性質(zhì)，我們可以找出k，即一直把b左移一位直到b大于a為止，這樣移動的結果比如(b<<x) ?> a, 那么x-1就是我們要找的k. 構造商的話，我們就定義一個int res, res |= 1<<k

?

1 public class Solution { 2 public int divide(int dividend, int divisor) { 3 if (dividend==Integer.MIN_VALUE && divisor==-1) return Integer.MAX_VALUE; 4 boolean isNeg = false; 5 long a = dividend; 6 long b = divisor; 7 if (b == 0) 8 throw new ArithmeticException(); 9 if (a < 0) { 10 isNeg = !isNeg; 11 a = -a; 12 } 13 if (divisor < 0) { 14 isNeg = !isNeg; 15 b = -b; 16 } 17 long num = a; 18 int res = 0; 19 while (num >= b) { 20 int i = 0; 21 while (num >= (b<<i)) { 22 i++; 23 } 24 res |= 1<<(i-1); 25 num -= b<<(i-1); 26 } 27 return isNeg? -res : res; 28 } 29 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/EdwardLiu/p/3800518.html

總結

以上是生活随笔為你收集整理的Leetcode: Divide Two Integers的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。