[数据结构与算法]算法分析（剑指offer）01

题目：整数除法

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 ‘*’、除号 ‘/’ 以及求余符号 ‘%’ 。
注意：

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [?2^31, 2 ^31?1]。本题中，如果除法结果溢出，则返回 2 ^31 ? 1

解题：

方法1：做循环减法，与零比较做index累加。只用了if else语句，期间需详细的分类讨论，解决溢出问题，尤其临界值需要谨慎分类，其中-2^31的相反数溢出，不能用。

class Solution {
    public int divide(int a, int b) {
        int i=0;
        if(a==0){
            return 0;
        }
        else if(b==(-1)&&a==(-2147483648)){
            return 2147483647;
        }
        
        else if(b==1){
            i=a;
             if(i<(-2147483648)||i>2147483647){
                return 2147483647;
            }
            else{
                return i;
            }
        }
        else if(b==(-1)){
            i=(-a);
            if(i<(-2147483648)||i>2147483647){
                return 2147483647;
            }else{
                return i;
            }
        }
        else if(a==(-2147483648)){
            if(b<0){
                 if(a>b){
                return 0;
            }
             else if(a==b){
                return 1;
            }
            else{
                while(a<=0){
                    a=a-b;
                    i++;
                }
            }
            }
            else if(b>0){
                if(a>b){
                return 0;
                }
                else{
                    i=0;
                    while(a<=0){
                        a=a+b;
                        i++;
                    }
                    i=(-i)+2;
                }
            }
        }
        else if(a>0&&b>0){
            if(a<b){
                return 0;
            }
            else if(a==b){
                return 1;
            }
            else {
                while(a>=0){
                a=a-b;
                i++;
            }
            
            }
            
        }
        else if(a>0&&b<0){
            if(-a>b){
                return 0;
            }
            else if(i<(-2147483648)||i>2147483647){
                return 2147483647;
            }
             else if(a==(-b)){
                return -1;
            }
            else{
                while(a>=0){
                    a=a-(-b);
                    i++;
                }
                i=(-i+2);
            }
        }
        else if(a<0&&b>0){
            if(-a<b){
                return 0;
            }
            else if(i<(-2147483648)||i>2147483647){
                return 2147483647;
            }
            else if(a==(-b)){
                return -1;
            }
            else{
                i=0;
                while(-a>=0){
                    a=a+b;
                    i++;
                }
                i=(-i)+2;
            }
        }
        else{
            if(a>b){
                return 0;
            }
             else if(a==b){
                return 1;
            }
            else{
                while(a<=0){
                    a=a-b;
                    i++;
                }
            }
        }
        if(i<(-2147483648)||i>2147483647){
            return 2147483647;
        }
        return i-1;
    }
}

方法2：相加来解决，b本身累加与a作比较，这里也需要详细的分类，不过这里的分类规则比上面的写法更简便一点。其中Integer.MAX_VALUE和Integer.MIN_VALUE为int两个临界值，即2147483647和-2147483648

class Solution {
    public int divide(int a, int b) {
        if(a==Integer.MIN_VALUE&&b==-1){
            return Integer.MAX_VALUE;
        }
        boolean flag = a>0&&b>0||a<0&&b<0;
        long d = a;
        long v = b;
        d = d>0?d:-d;
        v = v>0?v:-v;
        int res = 0;
        while(true){
            if(d<v){
                break;
            }
            int cur = 1;
            long tmp = v;
            while(tmp+tmp<=d){
                tmp+=tmp;
                cur+=cur;
            }
            res += cur;
            d-=tmp;
        }
        return flag?res:-res;
}
}