29. Divide Two Integers

给定两个int整数,分别为被除数和除数,要求不用乘除、取模,得到商的整数值。对于溢出时,int最大的边界值。
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.

思路:
先得到商的符号 sign= +/-;然后将被除数、除数都转为正数,最后将得到的结果根据 sign的符号返回。题目不能用除法,所以得用加减法,当被除数 = INT_MAX时,速度太慢,为了加快速度,用二倍累积,将减数不断的2倍累加,商值也2倍累加,加快运行速度。

难点:对于被除数=INT_MIN,除数=1/-1的情况;除数 = INT_MIN的情况,因为都转为正数处理,所以会溢出。对溢出情况,单独处理。以及二倍累积时,sum + sum > INT_MAX这也出现加法溢出

int divide(int dividend, int divisor) {
    int sign = 1, res = 0, x = 1073741823, sum = 0, res_tmp = 0;
    if (dividend == divisor) return 1;
    if (divisor == INT_MIN) return 0;
    if (dividend == INT_MIN) { //溢出判断
        dividend += abs(divisor);
        res = (divisor == -1) ? 0 : 1;
        if (divisor == 1) return INT_MIN;
    }
    if (dividend < 0 && divisor < 0) {//得到sign
        dividend = abs(dividend);
        divisor = abs(divisor);
    }
    else if (dividend >= 0 && divisor > 0);
    else {                            //得到sign
        dividend = abs(dividend);
        divisor = abs(divisor);
        sign = -1;
    }
    while (dividend >= divisor) {
        if (sum == 0) {
            sum = divisor; //减数
            res_tmp = 1; //商值
            res += res_tmp;
            dividend -= sum;
        }
        if (sum > x) break;//加法防溢出
        sum = sum + sum; //减数二倍累加
        res_tmp = res_tmp + res_tmp; //商值二倍累加
        if (dividend > sum) {
            res += res_tmp;
            dividend -= sum;
        }
        else sum = 0; //被减数 > 减数,从头开始
    }
    return sign == 1 ? res : -res;
}

 

上一篇:Python 3 快速入门 2 —— 流程控制与函数


下一篇:leetcode每周记录