Divide Integer

很无赖的方法,你不是要overflow么,我用long来存你
但是不能解决根本问题,万一我要你long type divide 怎么办!

public int divide(int dividend, int divisor) {
        if(dividend == Integer.MIN_VALUE && divisor == -1){
            return Integer.MAX_VALUE;
        }
        boolean isNeg = ((dividend ^ divisor) >>> 31) == 1;
        long p = Math.abs((long) dividend);
        long q = Math.abs((long) divisor);
        int res  = 0;
        while(p >= q){
            int counter = 0;
            while(p >= (q << counter)){
                counter++;
            }
            res += 1 << (counter - 1);
            p -= q << (counter - 1);
        }
        return (isNeg)? -res : res;
    }

不用long type, 想办法吧负数变成正数,取绝对值
但是倒霉蛋MIN_VALUE又来
1,被除数是最小值,先加一个正值,这样就能取绝对值了
2,除数是最小值,可以直接返回1或者0

位移的过程中再移就overflow,我们要及时制止!

public class Solution {
    public int divide(int dividend, int divisor) {
        if(divisor == 0){
            return Integer.MAX_VALUE;
        }
        boolean isNeg = ((dividend ^ divisor) >>> 31) == 1;
        int res = 0;
        if(dividend == Integer.MIN_VALUE){
            if(divisor == - 1){
                return Integer.MAX_VALUE;
            } //overflow
            if(divisor != Integer.MIN_VALUE){
                dividend += Math.abs(divisor);
                res++;
            }
        }
        if(divisor == Integer.MIN_VALUE){
            return (dividend == Integer.MIN_VALUE)? 1 : 0;
        }
        dividend = Math.abs(dividend);
        divisor = Math.abs(divisor);
        while(dividend >= divisor){
            int counter = 0;
            while(dividend >= (divisor << counter) && 
            ((Integer.MAX_VALUE / 2) >= (divisor << counter))){ //bug overflow, bug2 large than
                counter++;
            }
            counter = (counter == 0)? 0 : counter - 1;
            res += 1 << counter;
            dividend -= (divisor << counter);
        }
        return (isNeg)? -res : res;
    }
}
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