力扣29. 两数相除题解

原题链接29. 两数相除 - 力扣（LeetCode）

主要不能用乘除取余，于是用位运算代替：

Java题解

class Solution {
    public int divide(int dividend, int divisor) {
        //全都转为负数计算, 避免溢出, flag记录结果的符号
        int flag = 1;
        if(dividend < 0) {
            flag = -flag;
        }else {
            dividend = -dividend;
        }

        if(divisor < 0) {
            flag = -flag;
        }else {
            divisor = -divisor;
        }

        int div = divisor;

        // -(用多少个负数的divisor)
        int ans = 0;

        while(div >= dividend) {
            // 记录这次用了多少个divisor的负数 (避免溢出)
            int numDiv = -1;

            // 如果div乘二后不溢出并且小于被除数剩下的值则乘二，本次用的divisor数量也乘二
            while((div << 1) < div && (div << 1) >= dividend) {
                numDiv = numDiv << 1;
                div = div << 1;
            }

            // 被除数减去 负数的divisor * (-numDiv)
            dividend -= div;
            // 增加用的divisor数量
            ans += numDiv;
            // 重置除数
            div = divisor;
        }

        // 两个三十二位整数合法相除，只有可能正溢出，不可能负溢出，判断特殊条件
        if(ans == Integer.MIN_VALUE && flag == 1) {
            return Integer.MAX_VALUE;
        }else if(flag == 1) { // ans为不带符号的商的负数
            return -ans;
        }else {
            return ans;
        }
    }
}

        记录下比较有意思的点，我原来返回结果写的是 -flag * ans，因为担心在ans为Integer.MIN_VALUE，flag为-1时写(flag * (-ans))会溢出，但是试了下 -1 *  (-(-2147483648)) 的结果居然是 -2147483648，并没有想象中的奇怪值。实际上它的补码10000000 00000000 00000000 00000000， 取负数以后仍然是10000000 00000000 00000000 00000000， 先按位取反得到：01111111 11111111 11111111 11111111， 加一10000000 00000000 00000000 00000000，又变回原来的了，java是静默溢出，-1 *  (-(-2147483648))会溢出两次，但是结果仍不变