LeetCode刷题——29. Divide Two Integers（Part 2靠大家）

上篇文章写了以我自己的思路来解决这个问题，但是运行时间过长，看了leetcode 上的高效写法是使用位运算的解法，当初我自己写这个问题是也想到了可以用位运算快一点，但是因为基础差，对位运算的掌握不牢靠，还是选择使用了减法的思路，在此将leetcode上高效解法做一个思路分析，加深下自己对位运算的理解

LeetCode上高效解法代码

class Solution {
    
    public static int divide(int dividend, int divisor) {
        //首先处理Integer的最小值溢出问题（和我思路一样）
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        //判断结果符号（这个写法比我的号，但是结果的时候用到了乘法，难道符合题意？？费解  ）
        int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
        //取被除数最大值
        long dvd = Math.abs((long) dividend);
        //取除数最大值
        long dvs = Math.abs((long) divisor);
        //定义结果
        int res = 0;
        //循环条件：当被除数大于等于除数时候
        while (dvd >= dvs) {
           //为防止溢出,这里使用long类型
            long temp = dvs;
            long mult = 1;
            //<< 移位操作,向左移动1位
            //当dvd大于dvs*2的mult次方的时候,即计算dvd中最多有2的几次方个dvs
            while (dvd >= (temp << 1)) {
                temp <<= 1;
                mult <<= 1;
            }
            System.out.printf("%d里面有,2的%d次方个%d\r\n", dvd, mult, dvs);
            //计算新的dvd,和累加mult
            dvd -= temp;
            res += mult;
        }
        
        return res * sign;
    }
    
}

用例

[100,3]

输出结果

100里面有,2的32次方个3
4里面有,2的1次方个3

总结

上面的算法将以前的减操作优化称为位移操作，一次可以累加2的n次方个，减少了循环次数，所以比Part 1 中算法要快