LeetCode_29: Divide Two Integers

# 引言

题目链接：https://leetcode.com/problems/divide-two-integers/

# 题目大意

给定一个除数和被除数, 要求不使用除法、乘法以及取模操作计算。返回两个数做除法的商(结果取整数, 就相当于两个int做计算)

• Example

Input: dividend = 10, divisor = 3
Output: 3

Input: dividend = 7, divisor = -3
Output: -2

# 题解

题目规定了无法使用乘除法取模运算, 因此就只有考虑加减法和位运算了。

假设商为s, 余数为r, 则有$dividend=divisor*s+r$

一个比较朴素的想法就是一直用被除数(dividend)减去除数(divisor), 直到某一次结果小于除数的时候, 总共操作的减法次数就是商s的值。但是这样当被除数很大, 除数很小的时候, 进行减法操作次数会很多, 运算就会超时。

可行的方法就是减少做减法的次数, 有如下操作过程

$s=2^0+2^1+...2^k$

$dividend=divisor∗(2^0+2^1+...+2^k)+r$

每一次确定当前等式的$2^k$, $dividend$减去$dicisor*2^k$, $2^k$等于减去这个数等效的做减法次数, 至于求解$2^k$, 一个高效的方法可以通过位移运算实现, 即原等式与如下等式等价

$dividend=divisor<<0+divisor<<1+...+divisor<<k+r$

# 复杂度

时间复杂度 O((logn)^2), n等于被除数的位数

空间复杂度 O(1)

# AC代码

c++版本

class Solution
{
  public:
    int divide(int dividend, int divisor)
    {
        if (0 == divisor || (INT32_MIN == dividend && -1 == divisor))
        {
            return INT32_MAX;
        }
        if (1 == divisor)
        {
            return dividend;
        }
        bool negative = (dividend > 0) ^ (divisor > 0);
        int ret = 0;
        long ldividend = labs(dividend);
        long ldivisor = labs(divisor);
        while (ldividend >= ldivisor)
        {
            long k = ldivisor;
            long r = 1;
            while (ldividend >= (k << 1))
            {
                k <<= 1;
                r <<= 1;
            }
            ldividend -= k;
            ret += r;
        }
        return true == negative ? -ret : ret;
    }
};

go版本

const (
	INT32_MAX = int(^uint32(0) >> 1)
	INT32_MIN = ^INT32_MAX
)

func labs(x int64) int64 {
	if x < 0 {
		return -x
	}
	return x
}

func divide(dividend int, divisor int) int {
	if 0 == divisor || (INT32_MIN == dividend && divisor == -1) {
		return INT32_MAX
	} else if 1 == divisor {
		return dividend
	}
	ret := 0
	ldividend, ldivisor := labs(int64(dividend)), labs(int64(divisor))
	for ldividend >= ldivisor {
		k, r := ldivisor, 1
		for ldividend >= (k << 1) {
			k <<= 1
			r <<= 1
		}
		ret += r
		ldividend -= k
	}
	if (dividend >= 0 && divisor >= 0) || (dividend < 0 && divisor < 0) {
		return ret
	} else {
		return -ret
	}
}