Leetcode29-整数除法原理

题目要求简洁：不使用乘，除，取模符号计算两个整数相除，算有点难度。最开始考虑平常手工计算除法的原理，采用减法实现。这种方式有些例子是没问题，但是当被除数特别大，除数很小的时候，会超时，当然本地跑是没有时间限制的。比如Integer.MAX_VALUE / 1 大概需要21亿次运算，所以需要变通的方法。标准的计算是采用移位操作，这个有个前提，任意一个整数可以表示成
ax = a0*2^0 + a1*2^1 + a2*2^2 .... an*2^n
详细思路是：1、假设开始为ax1， 首先给除数移位，直到取到最大an2^n，记住n，然后新的被除数就是去掉an2^n 的部分，假设为ax2 ，接着再给ax2进行1的操作，取得新的n，依次执行，直到被除数小于除数的截止条件，而最终结果就是每一步的 n 移位相加的总和，如代码中 result += 1<< (shift - 1)。也可以使用递归，此处使用循环解决，相对也好理解。

看图放松

其他方面，考虑边界问题，如除数为0，以及被除数是最小整数 Integer.MIN_VALUE ，取模的话是超过最大整数范围的，可以转成long。以下是两个方案的代码。第一部分，减法方式会超时。第二部分是标准解法。代码也包括几个典型case。另外加几个优化，如除数为1，-1的情况，可以提高部分case的计算速度。

public class Leet29 {

    public static void main(String[] args) {
        System.out.println(divide(-16, 3));
        System.out.println(divide(133, 3));
        System.out.println(divide(-333, 3));
        System.out.println(divide(0, 23));
        System.out.println(divide(-3323, 23233));
        System.out.println(divide(-3323, -23233));
        System.out.println(divide(3, 333));
        System.out.println(divide(1, -1));
        System.out.println(divide(-5, 5));
        System.out.println(divide(1, 1));
        System.out.println(divide(-1, -1));
        System.out.println(divide(-2147483648, -1));
    }
    /*
    * *比较清晰标准的解法，具体参考：http://blog.csdn.net/yuqieshidi/article/details/48829465
    * 核心是 ax = a0*2^0 + a1*2^1 + a2*2^2 .... an*2^n
    * 从an*2^n 一层层往下找
    * Accepted
    */
    public static int divideBetter(int dividend, int divisor) {
        int result = 0;
        if (divisor == 0) //除数为0，返回最大值
            return Integer.MAX_VALUE;
        if (divisor == 1){
            return dividend;
        }

        if (divisor == -1 && dividend != Integer.MIN_VALUE ){
            return -dividend;
        }

        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return ~dividend;
        }

        //转成long MIN_VALUE 超过最大整数
        long dividend1 = Math.abs((long) dividend);
        long divisor1 = Math.abs((long) divisor);

        while (dividend1 >= divisor1)//当被除数大于除数时，进行位移操作
        {
            int shift = 0;
            while (dividend1 >= divisor1 << shift) {
                shift++;//记录左移次数（比实际次数多1）
            }
            result += 1 << (shift - 1);
            dividend1 -= divisor1 << (shift - 1);//更新被除数的值
        }

        return ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0))?result:-result;//计算正负数
    }

    //使用减法的版本，是人工算除法的思路，超时无法通过,不能使用乘除取模运算符，正确的是采用位运算。
    public static int divide(int dividend, int divisor) {
        if (dividend == 0 || divisor == 0) {
            return 0;
        }

        int flag = ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) ? -1 : 1;

        if (flag == -1 && (dividend + divisor) == 0) {
            return -1;
        }

        if (flag == 1 && (dividend == divisor)) {
            return 1;
        }

        //Math.abs(v);
        if (flag == 1 && dividend < 0) {
            if (dividend == Integer.MIN_VALUE) {
                dividend = Integer.MAX_VALUE;
            } else {
                dividend = -dividend;
            }
            divisor = -divisor;
        } else if (flag == -1 && dividend > 0) {
            divisor = -divisor;
        } else if (flag == -1 && divisor > 0) {
            dividend = -dividend;
        }

        if (dividend < divisor) {
            return 0;
        }

        int v = 0;
        while (dividend >= divisor) {
            dividend -= divisor;
            v++;
        }

        if (v >= Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }

        if (v <= Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }

        return flag * v;
    }
}