[LeetCode] Divide Two Integers (Java) | Life In Code

[LeetCode] Divide Two Integers (Java) | Life In Code
Divide two integers without using multiplication, division and mod operator.

1. a本来是想一直-b，然后减到<0了，算counter。但是这样慢，所以类似c++ vector的思路，每次发现还没减没，那减数就翻倍（b <<= 1）
2. 然后到了一定程度，b实在太大了，大于a剩余的部分了，那么就停止。然后剩下的a再一点点开始减，b回归成最开始的值，重做这两步。

重点是一旦超过，b应该不要一下回到原始值，而是应该一点一点/2这样做

We can keep subtract divisor from dividend until dividend is smaller than 0, than count the subtract numbers. But it will costs a very long time if the divisor is very small comparing to dividend.

Shift can be used to solve this problem. We shift the divisor left until it just smaller than dividend but if we keep shifting one more bit, it’s larger than dividend. Than we can add the shifted value to the result and subtract the shifted value from dividend. Keep doing this until dividend is smaller than divisor. In fact, every integer can be represented by a set of base 2 so that shifting can be used.

One thing needs to be mentioned is that we need to convert the integer to long type. Otherwise the Math.abs() value of Integer.MIN_VALUE will be quite strange.

any number can be converted to the format of the following:

num=a_0*2^0+a_1*2^1+a_2*2^2+...+a_n*2^n

    public int divide(int dividend, int divisor) {

        long p = Math.abs((long)dividend);

        long q = Math.abs((long)divisor);

        

        int ret = 0;

        while (p >= q) {

            int counter = 0;

            while (p >= (q << counter)) {

                counter++;

            }

            ret += 1 << (counter - 1);

            p -= q << (counter - 1);

        }

        

        if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0))

            return ret;

        else

            return -ret;

    }

http://segmentfault.com/a/1190000003789802
我们设想87 / 4，本来应该的得到21余3，那么如果我们把87忽略余数后分解一下，87 = 4 * 21 = 4 * 16 + 4 * 4 + 4 * 1，也就是87 = 4 * (1 * 2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0)，也就是把商分解为27 = 1 * 2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0，所以商的二进制是10101。我们可以不断的将4乘2的一次方，二次方，等等，直到找到最大那个次方，在这里是2的四次方。然后，我们就从四次方到零次方，按位看商的这一位该是0还是1。

    public int divide(int dividend, int divisor) {
        if(dividend == Integer.MIN_VALUE && (divisor == 1 || divisor == -1)){
            return divisor == 1 ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        }
        return (int)divideLong(dividend, divisor);
    }
    
    public long divideLong(long dd, long dv){
        boolean isPos = (dd > 0 && dv > 0) || (dd < 0 && dv < 0); 
        dd = Math.abs(dd);
        dv = Math.abs(dv);
        int digits = 0;
        // 通过将除数乘2，乘4，乘8，一直乘下去，找到商的最高的次方
        // 比如87/4=21，商的最高次方是4，即2^4=16，即4 * 16 < 87
        while(dv <= dd){
            dv <<= 1;
            digits++;
        }
        // 重置除数，把最高次方减1得到实际最高位，刚才循环中多加了一次
        long res = 0;
        dv >>= digits;
        digits--;
        // 看商的每一位是否应该为1
        while(digits >= 0){
            if(dd >= (dv << digits)){
                dd -= dv << digits;
                res += 1 << digits;
            }
            digits--;
            System.out.println(res);
        }
        return isPos ? res : - res;
    }

https://gist.github.com/xuelangZF/32b1ccc98b8dd4ce67e9

就是说不用乘法，除法，求模运算来实现两个整数相除，看起来很简单，我可以用除数减去被除数，直到除数小于被除数，记录减法操作的次数即可。假设是计算m/n，那么时间复杂度为O(m/n)。用Python实现后，Time Limit Exceeded。我们考虑有没有更加优化的算法呢？

我们对除数减去被除数的过程稍作改进。假设求m/n，我们不一次次的 m-n，而是找到n的一个倍数，使得m-x*n尽可能小，这样能减少循环减法的次数，进而提高效率。我们知道在按位操作中，n << k相当于 n * 2^k，因此可以用2^k 来找合适的x。

我们需要这样的一个数字k，它使得n 2^k < m < n 2^(k+1)， 然后用m - n*2^k，得到新的m'。再找相应的k'，做减法，如此循环即可

http://blog.csdn.net/linhuanmars/article/details/20024907
对于这道题目，因为不能用乘除法和取余运算，我们只能使用位运算和加减法。比较直接的方法是用被除数一直减去除数，直到为0。这种方法的迭代次数是结果的大小，即比如结果为n，算法复杂度是O(n)。

那么有没有办法优化呢？ 这个我们就得使用位运算。我们知道任何一个整数可以表示成以2的幂为底的一组基的线性组合，即num=a_0*2^0+a_1*2^1+a_2*2^2+...+a_n*2^n。基于以上这个公式以及左移一位相当于乘以2，我们先让除数左移直到大于被除数之前得到一个最大的基。然后接下来我们每次尝试减去这个基，如果可以则结果增加加2^k,然后基继续右移迭代，直到基为0为止。因为这个方法的迭代次数是按2的幂知道超过结果，所以时间复杂度为O(logn).

这种数值处理的题目在面试中还是比较常见的，类似的题目有Sqrt(x)，Pow(x, n)等。上述方法在其他整数处理的题目中也可以用到，大家尽量熟悉实现这些问题

1. public int divide(int dividend, int divisor) {  
2.     if(divisor==0)  
3.         return Integer.MAX_VALUE;  
4.       
5.     int res = 0;  
6.     if(dividend==Integer.MIN_VALUE)  
7.     {  
8.         res = 1;  
9.         dividend += Math.abs(divisor);  
10.     }  
11.     if(divisor==Integer.MIN_VALUE)  
12.         return res;  
13.     boolean isNeg = ((dividend^divisor)>>>31==1)?true:false;  
14.     dividend = Math.abs(dividend);  
15.     divisor = Math.abs(divisor);  
16.     int digit = 0;  
17.     while(divisor<=(dividend>>1))  
18.     {  
19.         divisor <<= 1;  
20.         digit++;  
21.     }  
22.     while(digit>=0)  
23.     {  
24.         if(dividend>=divisor)  
25.         {  
26.             dividend -= divisor;  
27.             res += 1<<digit;  
28.         }  
29.         divisor >>= 1;  
30.         digit--;  
31.     }  
32.     return isNeg?-res:res;  
33. }  

那么有没有办法优化呢？ 这个我们就得使用位运算。我们知道任何一个整数可以表示成以2的幂为底的一组基的线性组合，即num=a_0*2^0+a_1*2^1+a_2*2^2+…+a_n*2^n。基于以上这个公式以及左移一位相当于乘以2，我们先让除数左移直到大于被除数之前得到一个最大的基。然后接下来我们每次尝试减去这个基，如果可以则结果增加加2^k,然后基继续右移迭代，直到基为0为止。因为这个方法的迭代次数是按2的幂知道超过结果，所以时间复杂度为O(logn)。
http://oj.leetcode.com/problems/divide-two-integers/
http://www.acmerblog.com/leetcode-divide-two-integers-5977.html
http://jane4532.blogspot.com/2013/06/divide-2-integersleetcode.html

Also check Bit Hack Misc
Read full article from [LeetCode] Divide Two Integers (Java) | Life In Code