Divide Two Integers, Leetcode 解题笔记

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

作除法,直接的思路是每次从被除数减去除数,然后计算减的次数。但如果被除数相对于除数非常大,此解法会用很长时间。这里就要使用二分法的变种,即每次给除数*2,以加速上面的算法。

基本知识点:
1. 二进制位移,左移一位乘以2,右移一位处以2。
2. Integer的最小值为-2147483648,最大值为2147483647,所以如果直接把最小值取绝对值,会溢出。这里可以把int转换成long解决这个问题。

以下code摘抄自网络:

public class Solution {
    public int divide(int dividend, int divisor) {
        long a=Math.abs((long)dividend);
        long b=Math.abs((long)divisor);
        long result=0;
        
        //先看内循环,每次从内循环跳出后,除数回归原始,被除数是减剩下的,然后继续。
        while (a>=b){
            long c=b;
            int i=0;
            
            //除数每次*2,然后被除数减去除数,如果被除数比除数还小,则跳出此循环。
            while(c<=a){
                a=a-c;
                c=c<<1;
                result+=1<<i;
                i++;
            }
            
        }

        //判断正负
        if (dividend<0&&divisor>0||dividend>0&&divisor<0){
            result=-result;
        }
        return (int)result;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s